注册 登录
编程论坛 → 数据结构与算法

判断图连通性的问题

不同认为 发布于 2015-12-27 23:42， 9714 次点击
#include <stdio.h>
#define MAX_VERTEX_NUM 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int VRType;   
typedef char VertexType;
typedef char InfoType;
typedef enum {DG,DN,UDG,UDN}GraphKind;
int visited[MAX_VERTEX_NUM];
typedef struct ArcCell
{
    VRType adj;
    InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
    VertexType vexs[MAX_VERTEX_NUM];
    AdjMatrix arcs;
    int vexnum,arcnum;
    GraphKind kind;
}MGraph;
void DFS(MGraph G,int i,int &a)
{
    int j;
    visited[i]=TRUE;
    a++;
    for(j=0;j<5;j++)
     if(G.arcs[i][j].adj==1&&!visited[j])
         DFS(G,j,a);
        
        
}

int DFSTraverse(MGraph G)
{
    int b=0;
    DFS(G,0,b);
    if(b==5)
        return OK;
    else
        return ERROR;

}
int main()
{
    MGraph G,G1;
    int i,n,j;
     G.arcs[4][4].adj=(0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0);
    G1.arcs[4][4].adj=(0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0);
    for(i=0;i<5;i++)
    visited[i]=0;
    n=DFSTraverse(G);
    j=DFSTraverse(G1);
    if(n==1)
        printf("yes\n");
    else
        printf("no\n");
    if(j==1)
       printf("yes\n");
    else
        printf("no\n");
    return 0;
}
只有本站会员才能查看附件，请 登录
结果应该是第一个是连通的 第二个不是  我调试了一下  for(j=0;j<5;j++)
     if(G.arcs[i][j].adj==1&&!visited[j])
         DFS(G,j,a);这句话一直没执行过   不知道为什么 是我二维数组的初始化错了么
17 回复
#2
azzbcc2015-12-28 09:11
G.arcs[4][4].adj=(0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0);

这初始化的方法是谁教你的？
#3
不同认为2015-12-28 10:08
回复 2楼 azzbcc
不是这样初始化的么  我用{}括起来会报错，用（）没事
#4
azzbcc2015-12-28 10:49
当然了，你初始化一个VRType变量用{}不行，用小括号解析成成逗号运算符就ok。

c99的初始化方法如下：
程序代码：
    MGraph G = { .arcs[0][1] = { 1 }, .arcs[0][3]= { 1 }, .arcs[1]= {
            [0] = { 1 }, [2] = { 1 }, [4] = { 1 } }, .arcs[2][1] = { 1 },
            .arcs[3][0] = { 1 }, .arcs[4][1] = { 1 } };
    MGraph G1 = { .arcs[0][3] = { 1 }, .arcs[1][2] = { 1 }, .arcs[1][4] = { 1 },
            .arcs[2][1] = { 1 }, .arcs[3][0] = { 1 }, .arcs[4][1] = { 1 } };


不过我建议你一一赋值吧。
#5
不同认为2015-12-28 10:54
为什么初始化一个VRType变量用{}不行  .arcs[1]= {[0] = { 1 }, [2] = { 1 }, [4] = { 1 } }，这个是什么意思  没学过这个  ，一个一个复制的话岂不是要写太多出来了
#6
azzbcc2015-12-28 11:00
你那一行代码的本质是这样的

//G.arcs[4][4].adj=(0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0);
//typedef int VRType;
int a=(0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0);


对一个整形变量使不能用{}赋值的
#7
不同认为2015-12-28 11:04
arcs[1]= {[0] = { 1 }, [2] = { 1 }, [4] = { 1 } }那这样的赋值是什么意思 没见过这种  我把你给我的那段代码复制到我原来的代码里会报错  还有为什么//G.arcs[4][4].adj=(0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0);
int a=(0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0);我那样赋值是相当于对一个整形变量赋值
#8
wmf20142015-12-28 11:04
弱弱地问哈，什么情况下算是连通呢？
#9
azzbcc2015-12-28 11:07
我写的是c99标准的初始化 指定初始化 方式，这里有详细介绍http://www.

你这个题目来说，一一赋值最清晰了。

MGraph G = { 0 };
G.arcs[][] = 1;
...


也就16行代码
#10
不同认为2015-12-28 11:11
是要这样写 G.arcs[][].adj= 1;
MGraph G = { 0 };G.arcs[][] = 1;还是你这样   MGraph G = { 0 }这句话是啥意思
#11
azzbcc2015-12-28 11:14
回复 8楼 wmf2014
任取两点，有路径可达

全部满足就是连通图了
#12
azzbcc2015-12-28 11:16
回复 10楼 不同认为
MGraph G = {0}

会默认把结构体内变量一一赋为0
程序代码：
MGraph G = {0};
G.arcs[0][1].adj = 1;
G.arcs[0][3].adj = 1;
G.arcs[1][0].adj = 1;
G.arcs[1][2].adj = 1;
G.arcs[1][4].adj = 1;
...


这样写

[此贴子已经被作者于2015-12-28 11:19编辑过]
#13
不同认为2016-01-01 20:08
回复 8楼 wmf2014
就是一个点进行深度优先遍历 看能不能遍历完所有的点  可以的话就连通
#14
wmf20142016-01-02 09:43
回复 13楼 不同认为
其实，还是不明白。楼主所举例的A1怎么就连通，A2就不通呢？要是有图例就好，估计算法是递归。
#15
不同认为2016-01-04 19:23
回复 12楼 azzbcc
#include<stdio.h>  
int visited[5];
typedef struct e
{
    int adj;
}e,A[30][30];
typedef struct
{
    A arcs;
}MGraph;
void DFS(MGraph G,int i,int &a)
{
    int j;
    visited[i]=1;
    a++;
    for(j=0;j<5;j++)
    if(G.arcs[i][j].adj==1&&!visited[j])
         DFS(G,j,a);
}
int DFSTraverse(MGraph G)
{
    int b=0;
    DFS(G,0,b);
    if(b==5)
        return 1;
    else
        return 0;
}
int main()
{
    int i,q,w;
    MGraph G={0};
    MGraph G1={0};
    G.arcs[0][1].adj=1;
    G.arcs[0][3].adj=1;
    G.arcs[1][0].adj=1;
    G.arcs[1][2].adj=1;
    G.arcs[1][4].adj=1;
    G.arcs[2][1].adj=1;
    G.arcs[3][1].adj=1;
    G.arcs[4][1].adj=1;
    G1.arcs[0][3].adj=1;
    G1.arcs[1][2].adj=1;
    G1.arcs[1][4].adj=1;
    G1.arcs[2][1].adj=1;
    G1.arcs[3][0].adj=1;
    G1.arcs[4][1].adj=1;
    for(i=0;i<5;i++)
    visited[i]=0;
    q=DFSTraverse(G);
    w=DFSTraverse(G1);
    if(q==1)
        printf("A1是连通图\n");
    else
        printf("A1不是连通图\n");
    if(w==1)
       printf("A2是连通图\n");
    else
        printf("A2不是连通图\n");
    return 0;
}










#include<stdio.h>  
int visited[5];
typedef struct
{
    int arcs[5][5];
}MGraph;
void DFS(MGraph G,int i,int &a)
{
    int j;
    visited[i]=1;
    a++;
    for(j=0;j<5;j++)
    if(G.arcs[i][j]==1&&!visited[j])
         DFS(G,j,a);
}
int DFSTraverse(MGraph G)
{
    int b=0;
    DFS(G,0,b);
    if(b==5)
        return 1;
    else
        return 0;
}
int main()
{
    int i,q,w;
    MGraph G={0};
    MGraph G1={0};
    G.arcs[0][1]=1;
    G.arcs[0][3]=1;
    G.arcs[1][0]=1;
    G.arcs[1][2]=1;
    G.arcs[1][4]=1;
    G.arcs[2][1]=1;
    G.arcs[3][1]=1;
    G.arcs[4][1]=1;
    G1.arcs[0][3]=1;
    G1.arcs[1][2]=1;
    G1.arcs[1][4]=1;
    G1.arcs[2][1]=1;
    G1.arcs[3][0]=1;
    G1.arcs[4][1]=1;
    for(i=0;i<5;i++)
    visited[i]=0;
    q=DFSTraverse(G);
    w=DFSTraverse(G1);
    if(q==1)
        printf("A1是连通图\n");
    else
        printf("A1不是连通图\n");
    if(w==1)
       printf("A2是连通图\n");
    else
        printf("A2不是连通图\n");
    return 0;
}


这两种写法是不是都可以
#16
azzbcc2016-01-05 09:37
回复 15楼 不同认为
对。

并没又区别啊
#17
不同认为2016-01-05 12:10
回复 16楼 azzbcc
感觉书上都定义两个结构体，就是第一个代码，我觉得直接定义一个就好了
#18
qiuzhenq2016-05-30 17:25
如果不使用领接矩阵，而就使用结点字母和边来表示，应该怎么设计程序？
1
©2025, BCCN.NET
电脑版