| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 9653 人关注过本帖
标题:判断图连通性的问题
只看楼主 加入收藏
不同认为
Rank: 1
等 级:新手上路
帖 子:93
专家分:3
注 册:2015-11-25
结帖率:57.14%
收藏
已结贴  问题点数:20 回复次数:17 
判断图连通性的问题
#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);这句话一直没执行过   不知道为什么 是我二维数组的初始化错了么
搜索更多相关主题的帖子: include 
2015-12-27 23:42
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:20 
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);

这初始化的方法是谁教你的?



[fly]存在即是合理[/fly]
2015-12-28 09:11
不同认为
Rank: 1
等 级:新手上路
帖 子:93
专家分:3
注 册:2015-11-25
收藏
得分:0 
回复 2楼 azzbcc
不是这样初始化的么  我用{}括起来会报错,用()没事
2015-12-28 10:08
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
当然了,你初始化一个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 } };


不过我建议你一一赋值吧。



[fly]存在即是合理[/fly]
2015-12-28 10:49
不同认为
Rank: 1
等 级:新手上路
帖 子:93
专家分:3
注 册:2015-11-25
收藏
得分:0 
为什么初始化一个VRType变量用{}不行  .arcs[1]= {[0] = { 1 }, [2] = { 1 }, [4] = { 1 } },这个是什么意思  没学过这个  ,一个一个复制的话岂不是要写太多出来了
2015-12-28 10:54
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
你那一行代码的本质是这样的

//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);


对一个整形变量使不能用{}赋值的


[fly]存在即是合理[/fly]
2015-12-28 11:00
不同认为
Rank: 1
等 级:新手上路
帖 子:93
专家分:3
注 册:2015-11-25
收藏
得分:0 
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);我那样赋值是相当于对一个整形变量赋值
2015-12-28 11:04
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
弱弱地问哈,什么情况下算是连通呢?

能编个毛线衣吗?
2015-12-28 11:04
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
我写的是c99标准的初始化 指定初始化 方式,这里有详细介绍http://www.

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

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


也就16行代码


[fly]存在即是合理[/fly]
2015-12-28 11:07
不同认为
Rank: 1
等 级:新手上路
帖 子:93
专家分:3
注 册:2015-11-25
收藏
得分:0 
是要这样写 G.arcs[][].adj= 1;
MGraph G = { 0 };G.arcs[][] = 1;还是你这样   MGraph G = { 0 }这句话是啥意思
2015-12-28 11:11
快速回复:判断图连通性的问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.072057 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved