深度遍历图,请问这个程序哪里出了问题呢?
//深度遍历搜索图#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 3
typedef enum {DG,DN,UDG,UDN} GraphKind;//图的类型
typedef int OtherInfo; //弧的信息,如权
typedef char VertexData;//图结点的内容为char
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
OtherInfo info;
}ArcNode;//弧结点
typedef struct VertexNode
{
VertexData data;
ArcNode *firstarc;
}VertexNode;//表头结点
typedef struct
{
VertexNode vertex[MAX_VERTEX_NUM];
int arcnum;
int vexnum;
GraphKind kind;
}AdjList;//邻接表(图)
int visited[MAX_VERTEX_NUM];//全局变量:访问标志数组
void CreateAdjList(AdjList *G);
int Locate(AdjList *G, char v);
void TraverseGraph(AdjList *G);
void DepthFirstSearch(AdjList*G,int v0);
void CreateAdjList(AdjList *G)//建立邻接表
{
char v1;char v2;//v1,v2为一条弧上的两个端点,一个为起始端点,一个为尾端点
ArcNode *s;
int i,j,k;
char ch;
printf(" 输入图结点:");
for(i=0;i<G->vexnum;i++)//表头结点初始化
{
scanf("%c",&ch);
G->vertex[i].data=ch;
G->vertex[i].firstarc=NULL;
fflush(stdin);
}
for(k=0;k<G->arcnum;k++)
{
printf("输入连接弧端点值,如“A,B”");
scanf("%c,%c",&v1 ,&v2 );
//v1=getchar();
//v2=getchar();
i=Locate(G,v1);printf("%d",i);//定位v1在表头结点里的数组下标,即第几个
j=Locate(G,v2);printf("#");
s=(ArcNode*)malloc(sizeof(ArcNode));
s->adjvex=j;
s->nextarc=G->vertex[i].firstarc;
G->vertex[i].firstarc=s;//头结点插入法
s=(ArcNode*)malloc(sizeof(ArcNode));
s->adjvex=i;
s->nextarc=G->vertex[j].firstarc;
G->vertex[j].firstarc=s;
}
}
//定位,查找v1,v2的相应数组下标
int Locate(AdjList *G,char v)
{
for(int i=0;i<G->vexnum;i++)
if(G->vertex[i].data==v)
return i;
else
return 0;
}
//深度优先搜索邻接表
void TraverseGraph(AdjList *G)
{
int vi=0;//没访问过的置0,访问过的置1;
for(vi=0;vi<G->vexnum;vi++)
visited[vi]=0;
for(vi=0;vi<G->vexnum;vi++)
if(visited[vi]==0)
DepthFirstSearch(G,vi);
}
void DepthFirstSearch(AdjList*G,int v0)//DFS
{
ArcNode*p;
printf("%c",v0);
visited[v0]=1;//访问过后标志数组置为1;
p=G->vertex[v0].firstarc;
while(p!=NULL)
{
if(visited[p->adjvex]==0)
DepthFirstSearch(G,p->adjvex);
p=p->nextarc;
}
}
int main()
{
AdjList * G;
G=(AdjList*)malloc(sizeof(AdjList));
printf("输入图结点数目,弧数目,如“4,3”\n");
scanf("%d,%d",&G->vexnum,&G->arcnum );
CreateAdjList(G);
TraverseGraph(G);
free(G);
return 0;
}