6-7 图的深度遍历-邻接表实现

6-7 图的深度遍历-邻接表实现

本题要求实现邻接表存储图的深度优先遍历。

函数接口定义：

void DFS(ALGraph *G,int i);
其中ALGraph是邻接表存储的图，定义如下：

#define MAX_VERTEX_NUM 10 /定义最大顶点数/
typedef int Vertex;
typedef struct ArcNode{ /表结点/
int adjvex; /邻接点域/
struct ArcNode *nextarc; /指向下一个表结点/
}ArcNode;
typedef struct VNode{ /头结点/
Vertex data; /顶点域/
ArcNode *firstarc; /指向第一个表结点/
}VNode,AdjList[MAX_VERTEX_NUM]; /AdjList是数组类型/
typedef struct {
AdjList vertices; /邻接表中数组定义/
int vexnum,arcnum; /图中当前顶点数和边数/
} ALGraph; /图类型/
裁判测试程序样例：

#include"stdio.h"
#include"stdlib.h"
#define MAX_VERTEX_NUM 10 /定义最大顶点数/
typedef int Vertex;
typedef struct ArcNode{ /表结点/
int adjvex; /邻接点域/
struct ArcNode *nextarc; /指向下一个表结点/
}ArcNode;
typedef struct VNode{ /头结点/
Vertex data; /顶点域/
ArcNode *firstarc; /指向第一个表结点/
}VNode,AdjList[MAX_VERTEX_NUM]; /AdjList是数组类型/
typedef struct {
AdjList vertices; /邻接表中数组定义/
int vexnum,arcnum; /图中当前顶点数和边数/
} ALGraph; /图类型/
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MAX_VERTEX_NUM];/定义标志向量，为全局变量/
void CreatALGraph(ALGraph G);/ 创建图并且将Visited初始化为false；裁判实现，细节不表 */
void DFS(ALGraph G,int v);
int main()
{
Vertex v;
ALGraph G;
CreatALGraph(&G);
scanf(“%d”, &v);
printf(“DFS from %d:”,v);
DFS(&G,v);
return 0;
}
/ 你的代码将被嵌在这里 */
对于给定图：

输入样例：
第一行给出图的顶点数n和边数e，随后e行，每行给出一条边的两个顶点编号，最后一行给出遍历的起始顶点编号。

7 9
0 2
0 3
0 4
1 3
1 5
2 3
2 5
4 5
5 6
5
输出样例：
DFS from 5: 5 6 4 0 3 2 1

代码：

void DFS(ALGraph *G, int i) {
    
	printf(" %d",i);
	visited[i] = 1;
	for (struct  ArcNode *  w= G->vertices[i].firstarc;w!=NULL;w=w->nextarc) {
    
		if (visited[w->adjvex] == 0)
			DFS(G, w->adjvex);
	}
}

202206201639一