求求哪位大佬帮我看看这个图的深度遍历为啥不能将所有顶点全部输出?

小雨石兰 发布于 2018/10/04 17:18
阅读 113
收藏 0

//图---邻接矩阵加深度优先遍历
#include <stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
#define true 1
#define false 0
int visited[MAXSIZE];
typedef char VerTexType;
typedef int Status;
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *nextarc;   //下一条弧
}ArcNode;
typedef struct
{
    VerTexType data;
    ArcNode *firstarc;      //顶点
}AdjList[MAXSIZE];
typedef struct
{
   AdjList vertices;
   int vexnum,arcnum;
}ALGraph;
Status LocateVex(ALGraph *G,VerTexType v)
{
    int i;
    for(i=0;i<G->vexnum;i++)
    {
        if(G->vertices[i].data==v)
        {
            return i;
            break;
        }
    }
}

//创建图
Status CreateGraph(ALGraph *G)
{
    ArcNode *p;
    int i,k,m;
    VerTexType v1,v2;
    printf("请输入图的顶点数和弧数\n");
    scanf("%d%d",&(G->vexnum),&(G->arcnum));
    printf("请输入图的顶点\n");
    for(i=0;i<G->vexnum;i++)
    {
        scanf("%c",&(G->vertices[i].data));
        G->vertices[i].firstarc=NULL;
    }
    printf("请输入弧\n");
    fflush(stdin);
    for(i=0;i<G->arcnum;i++)
    {
        scanf(" %c%c",&v1,&v2);
        k=LocateVex(G,v1);
        m=LocateVex(G,v2);
        p=(ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex=m;
        p->nextarc=G->vertices[k].firstarc;
        G->vertices[k].firstarc=p;
    }
    return 0;
}

//深度遍历图
void DFS(ALGraph G,int v)
{
    ArcNode *p;
    printf("%c ",G.vertices[v].data);
    visited[v]=true;
    for(p=G.vertices[v].firstarc;p;p=p->nextarc)
    {
        if(visited[p->adjvex]==0)
        {
            DFS(G,p->adjvex);
        }
    }
}

void DFSTraverse(ALGraph G)
{
    int i;
    for(i=0;i<G.vexnum;i++)
    {
        visited[i]=false;
    }
    for(i=0;i<G.vexnum;i++)
    {
        if(!visited[i])
        {
            DFS(G,i);
        }
    }
}
int main()
{
    ALGraph G;
    CreateGraph(&G);
    DFSTraverse(G);
    return 0;

}
 

加载中
0
tcxu
tcxu

注意:

  1.  楼主的代码,用这不是 "邻接矩阵加深度优先遍历", 而是 "无向图的邻接表加深度优先遍历"。
  2. 为了消除与用户互动输入数据操作过程中残留的符号, 如回车、空格等,每次读进代码的后面,加上:fflush(stdin);, 以清空输入缓冲区。换句话,为了确保不影响后面的数据读取(例如在读完一个字符串后紧接着又要读取一个字符,此时应该先执行fflush(stdin);)
  3.  
if(G->vertices[i].data==v)
        {
            return i;
	    break; //多余,应当删除这一句。
        }

 

测试输出:

请输入图的顶点数和弧数
8 9
请输入图的顶点
ABCDEFGH
请输入弧
AB
BD
DH
BE
EH
AC
CF
CG
FG
A C G F B E H D

修改过的代码:

//图---邻接表加深度优先遍历
#include <stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
#define true 1
#define false 0
int visited[MAXSIZE];
typedef char VerTexType;
typedef int Status;
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *nextarc;   //下一条弧
}ArcNode;
typedef struct
{
    VerTexType data;
    ArcNode *firstarc;      //顶点
}AdjList[MAXSIZE];
typedef struct
{
   AdjList vertices;
   int vexnum,arcnum;
}ALGraph;
Status LocateVex(ALGraph *G,VerTexType v)
{
    int i;
    for(i=0;i<G->vexnum;i++)
    {
        if(G->vertices[i].data==v)
        {
            return i; //返回 i,函数调用结束
        }
    }
}

//创建图
Status CreateGraph(ALGraph *G)
{
    ArcNode *p;
    int i,k,m;
    VerTexType v1,v2;
    printf("请输入图的顶点数和弧数\n");
    scanf("%d%d",&(G->vexnum),&(G->arcnum));
    fflush(stdin); //清空输入缓冲区
    printf("请输入图的顶点\n");
    for(i=0;i<G->vexnum;i++)
    {
        scanf("%c",&(G->vertices[i].data));
        G->vertices[i].firstarc=NULL;
    }
    printf("请输入弧\n");
    fflush(stdin);//清空输入缓冲区
    for(i=0;i<G->arcnum;i++)
    {
        scanf(" %c%c",&v1,&v2);
        k=LocateVex(G,v1);
        m=LocateVex(G,v2);
        p=(ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex=m;
        p->nextarc=G->vertices[k].firstarc;
        G->vertices[k].firstarc=p;
    }
    return 0;
}

//深度遍历图
void DFS(ALGraph G,int v)
{
    ArcNode *p;
    printf("%c ",G.vertices[v].data);
    visited[v]=true;
    for(p=G.vertices[v].firstarc;p;p=p->nextarc)
    {
        if(visited[p->adjvex]==0)
        {
            DFS(G,p->adjvex);
        }
    }
}

void DFSTraverse(ALGraph G)
{
    int i;
    for(i=0;i<G.vexnum;i++)
    {
        visited[i]=false;
    }
    for(i=0;i<G.vexnum;i++)
    {
        if(!visited[i])
        {
            DFS(G,i);
        }
    }
}
int main()
{
    ALGraph G;
    CreateGraph(&G);
    DFSTraverse(G);
    return 0;

}

 

返回顶部
顶部