| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
跟大牛学C++学算法数据结构
共有 347 人关注过本帖
标题:关于图的邻接矩阵深度遍历求大神指教谢谢!
只看楼主 加入收藏
不要做咸鱼
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2018-3-5
结帖率:0
  问题点数:0  回复次数:0   
关于图的邻接矩阵深度遍历求大神指教谢谢!
代码太长了所以只放了无向图的创建和遍历,问题应该是出在DFS函数的for循环里,这个变成死循环了,循环条件我觉得应该是w<g.verxnum,书上的是>=0,但是两种都不对,希望大神帮我看一下谢谢!
#include <stdio.h>
#include <stdlib.h>
//#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
//typedef enum {DG=1,DN,UDG,UDN,NO} GraphKind;
typedef char VertexType;//顶点类型不一定是字母还有可能是汉字
typedef struct ArcCell{
    int 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;

int LocateVex(MGraph g,VertexType x)
{
    for(int i=0;i<g.vexnum;i++){
        if(x==g.vexs[i]){
            return i;
        }
    }
}
void CreateUDG(MGraph &g)//无向图
{
    char a,b;
    int  x,y;
    printf("enter the vexnum:");
    scanf("%d",&g.vexnum);
    printf("enter the arcnum:");
    scanf("%d",&g.arcnum);
    printf("enter the vertexs:");
    getchar();
    for(int i=0;i<g.vexnum;i++){//顶点向量
        g.vexs[i]=getchar();
    }
    for(int i=0;i<g.vexnum;i++){//初始化邻接矩阵
        for(int j=0;j<g.arcnum;j++){
            g.arcs[i][j].adj=0;
        }
    }
    printf("enter the arc's vertexs:\n");
    //getchar();
    for(int i=0;i<g.arcnum;i++){
        getchar();
        printf("enter the one:");
        a=getchar();
        getchar();
        printf("enter the other:");
        b=getchar();
        x=LocateVex(g,a);
        y=LocateVex(g,b);
        g.arcs[x][y].adj=1;
        g.arcs[y][x].adj=1;
    }
}
void Printf(MGraph &g)
{
    for(int i=0;i<g.vexnum;i++){
        for(int j=0;j<g.vexnum;j++){
            printf("%d ",g.arcs[i][j].adj);
        }
        printf("\n");
    }
}
int FirstAdjVex(MGraph &g,int i)
{
    int j=0;
    while(j<g.vexnum){
        if(g.arcs[i][j].adj>0){
            return j;
        }
        else
            j++;
    }
}
int NextAdjVex(MGraph &g,int i,int w)
{
    int j=w+1;
    while(j<g.vexnum){
        if(g.arcs[i][j].adj>0){
            return j;
        }
        else
            j++;
    }
}
void DFS(MGraph &g,int i,int visited[])
{
    int w;
    visited[i]=1;
    printf("%c ",g.vexs[i]);
    for(w=FirstAdjVex(g,i);w<g.vexnum;w=NextAdjVex(g,i,w)){//遍历arc[i][x]表***这个循环i是个定值
        if(!visited[w]){
            DFS(g,w,visited);
        }
    }
}
void DFSTraverse(MGraph &g)
{
    int i;
    int visited[MAX_VERTEX_NUM];
    for(i=0;i<g.vexnum;i++){//初始化标记数组
        visited[i]=0;
    }
    for(i=0;i<g.vexnum;i++){
        if(!visited[i]){
            DFS(g,i,visited);
        }
    }
}
int main()
{
    MGraph g;
    CreateUDG(g);
    printf("\nAdjacency Matrix:\n");
    Printf(g);
    printf("\nTraversing Graph:\n");
    DFSTraverse(g);
    return 0;
}
运行过程:
enter the vexnum:3
enter the arcnum:3
enter the vertexs:ABC
enter the arc's vertexs:
enter the one:A
enter the other:B
enter the one:A
enter the other:C
enter the one:B
enter the other:C

Adjacency Matrix:
0 1 1
1 0 1
1 1 0

Traversing Graph:
A B C
2018-11-11 13:22







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

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