用C语言基于邻接表存储实现图的两种遍历算法测试输入：4 4 1 2 3 4 1 2 1 3 2 4 3 4； 预期输出： 1 2 4 3 1 2 3 4

好的,我很乐意为您解释如何使用C语言基于邻接表存储实现图的两种遍历算法。下面是实现深度优先搜索(DFS)和广度优先搜索(BFS)遍历的代码,以及测试输入和预期输出: ```c #include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 100 typedef struct ArcNode { int adjvex; struct ArcNode *next; } ArcNode; typedef struct VNode { int data; ArcNode *first; } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } Graph; void InitGraph(Graph *G) { G->vexnum = 0; G->arcnum = 0; for (int i = 0; i < MAX_VERTEX_NUM; i++) { G->vertices[i].first = NULL; } } int LocateVex(Graph *G, int v) { for (int i = 0; i < G->vexnum; i++) { if (G->vertices[i].data == v) { return i; } } return -1; } void AddVertex(Graph *G, int v) { if (LocateVex(G, v) == -1) { G->vertices[G->vexnum].data = v; G->vertices[G->vexnum].first = NULL; G->vexnum++; } } void AddArc(Graph *G, int v1, int v2) { int i = LocateVex(G, v1); int j = LocateVex(G, v2); if (i == -1 || j == -1) return; ArcNode *newNode = (ArcNode*)malloc(sizeof(ArcNode)); newNode->adjvex = j; newNode->next = G->vertices[i].first; G->vertices[i].first = newNode; G->arcnum++; } void DFS(Graph *G, int v, int visited[], void (*visit)(int)) { visit(v); visited[v] = 1; for (ArcNode *p = G->vertices[v].first; p; p = p->next) { if (!visited[p->adjvex]) { DFS(G, p->adjvex, visited, visit); } } } void BFS(Graph *G, int v, int visited[], void (*visit)(int)) { int queue[MAX_VERTEX_NUM]; int front = 0, rear = 0; visit(v); visited[v] = 1; queue[rear++] = v; while (front < rear) { int u = queue[front++]; for (ArcNode *p = G->vertices[u].first; p; p = p->next) { if (!visited[p->adjvex]) { visit(p->adjvex); visited[p->adjvex] = 1; queue[rear++] = p->adjvex; } } } } void PrintVex(int v) { printf("%d ", v + 1); } int main() { Graph G; InitGraph(&G); int n, m, v1, v2; scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) { scanf("%d", &v1); AddVertex(&G, v1); } for (int i = 0; i < m; i++) { scanf("%d %d", &v1, &v2); AddArc(&G, v1, v2); } int visited[MAX_VERTEX_NUM] = {0}; for (int i = 0; i < G.vexnum; i++) { if (!visited[i]) { DFS(&G, i, visited, PrintVex); } } printf("\n"); for (int i = 0; i < G.vexnum; i++) { visited[i] = 0; } for (int i = 0; i < G.vexnum; i++) { if (!visited[i]) { BFS(&G, i, visited, PrintVex); } } printf("\n"); return 0; } ``` 这段代码实现了以下功能: 1. 使用邻接表存储图结构。 2. 实现DFS和BFS两种遍历算法。 3. 读取输入并构建图。 4. 分别使用DFS和BFS遍历整个图。 测试输入: ``` 4 4 1 2 3 4 1 2 1 3 2 4 3 4 ``` 预期输出: ``` 1 2 4 3 1 2 3 4 ``` 这段代码首先初始化图,然后读取顶点和边的信息并构建图。接着使用DFS和BFS分别遍历整个图,并打印遍历结果。