图的遍历 邻接表的遍历

图的遍历 邻接表的遍历

#include#include#define MAX_VERTEX_NUM 20bool visited[MAX_VERTEX_NUM];typedef struct ArcNode{ int adjvex; //该边所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条边的指针}ArcNode; typedef struct{ ArcNode * AdjList[MAX_VERTEX_NUM]; //指向第一条依附该顶点的边的指针 int vexnum, arcnum; //图的当前顶点和弧数}Graph;void CreateGraph(Graph &G){//构造邻接表结构的图G int i; int start,end; //记录弧尾、弧头信息，或边的两个邻接点信息 ArcNode *s; printf("请输入图的顶点数和边数:"); scanf("%d,%d",&G.vexnum,&G.arcnum); //输入图的顶点数和边数 for(i=1;i<=G.vexnum;i++) G.AdjList[i]=NULL; //初始化指针数组 printf("请输入各边, 格式：顶点,顶点\n"); for(i=1;i<=G.arcnum;i++) {scanf("%d,%d",&start,&end); //输入边的起点和终点 s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一个边结点 s->nextarc=G.AdjList[start]; //插入到邻接表中，注意此处为逆向插入到单链表中 s->adjvex=end; G.AdjList[start]=s; //无向图，注意是对称插入结点 s=(ArcNode *)malloc(sizeof(ArcNode)); s->nextarc=G.AdjList[end]; s->adjvex=start; G.AdjList[end]=s; }} int FirstAdjVex(Graph G, int v) { ArcNode *p; if(v>=1 && v<=G.vexnum) { p=G.AdjList[v]; if(p->nextarc==NULL) return 0; else return (p->nextarc->adjvex); } return -1; }int NextAdjVex(Graph G, int v, int w){//在图G中寻找第v个顶点的相对于w的下一个邻接顶点 ArcNode *p; if(v>=1 && v<=G.vexnum && w>=1 && w<=G.vexnum) { p=G.AdjList[v]; while(p->adjvex!=w) p=p->nextarc; //在顶点v的弧链中找到顶点w if(p->nextarc!=NULL) return 0; //若已是最后一个顶点，返回0 else return(p->nextarc->adjvex); //返回下一个邻接顶点的序号 } return -1;}void DFS(Graph G, int v) { int i,w; ArcNode *p; visited[v]=1; printf("%d ",v); //访问第v个顶点 p=G.AdjList[v]; while (p!=NULL) { w=p->adjvex; if(visited[w]==0) DFS(G,w); p=p->nextarc; }}void DFSTravel(Graph G){ int i,w,v=1; ArcNode *p; visited[v]=1; printf("%d ",v); //访问第v个顶点 p=G.AdjList[v]; while (p!=NULL) { w=p->adjvex; if(visited[w]==0) DFS(G,w); p=p->nextarc; }}void main(){ int i,v; Graph G; CreateGraph(G); printf("请输入深度优先遍历开始点的名："); scanf("%d",&v); for(i=1;i<=G.vexnum;i++) visited[i]=0; DFS(G,v); printf("\n"); for(i=1;i<=G.vexnum;i++) visited[i]=0; DFSTravel(G); printf("\n");}