struct ArcNode{ //定义边结点
int adjvex;
struct ArcNode *nextarc;
};
struct Vnode{ //定义顶点结点
int data;
struct ArcNode *firstarc;
};
struct Vnode AdjList[MAX];
int m,n,v,cord;
void main()//主函数
{
void CreatGraph(struct Vnode A[MAX]);
void DFS(struct Vnode A[MAX]);
CreatGraph(AdjList);
DFS(AdjList);
}
void CreatGraph(struct Vnode A[MAX])//无向图邻接链表的建立
{
int i,j,k;
struct ArcNode *p;
printf(\"输入图的边数和顶点数:\");
scanf(\"%d,%d\
for(k=0;k{A[k].data=k+1;
A[k].firstarc=NULL;
}
for(k=0;k{printf(\"输入和边关联的顶点号:\");
scanf(\"%d,%d\
p=(struct ArcNode*)malloc(sizeof(struct ArcNode));
p->adjvex=j;
p->nextarc=A[i-1].firstarc;
A[i-1].firstarc=p;
p=(struct ArcNode *)malloc(sizeof(struct ArcNode));
p->adjvex=i;
p->nextarc=A[j-1].firstarc;
A[j-1].firstarc=p;
}
printf(\"\\n\");
for(k=0;k{printf(\"%d \
p=A[k].firstarc;
while(p){
printf(\"%d \
p=p->nextarc;
}
printf(\"\\n\");
}
}
void DFS(struct Vnode A[MAX]) //深度优先遍历
{
struct ArcNode *p,*ar[MAX];
int x,i,y,top=-1;
int visited[MAX];
for(i=0;iprintf(\"\\n输入图遍历的始顶点的编号x:\");scanf(\"%d\
printf(\"%d\
visited[x-1]=1;
p=A[x-1].firstarc;
while((p)||(top>=0)){
if(!p){
p=ar[top];
top--;}
y=p->adjvex;
if(visited[y-1]==0)
{ visited[y-1]=1;
printf(\"->%d\
p=p->nextarc;
if(p){
top++; ar[top]=p;}
p=A[y-1].firstarc;
}
else p=p->nextarc;
}
printf(\"\\n\");
}
