用C语言写出将一个无向图的邻接矩阵转换成邻接表的算法。通过对两种不同存储方法的图，输出其DFS序列一致性加以验证转换正确。

好的,我来为您解释一下如何使用C语言将一个无向图的邻接矩阵转换成邻接表,并验证转换的正确性。 首先,让我们定义数据结构: ```c #include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 100 // 邻接表中的边节点 typedef struct EdgeNode { int adjvex; struct EdgeNode *next; } EdgeNode; // 邻接表中的顶点节点 typedef struct VertexNode { int data; EdgeNode *firstedge; } VertexNode, AdjList[MAX_VERTEX_NUM]; // 图的邻接表表示 typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; // 栈结构用于DFS int stack[MAX_VERTEX_NUM]; int top = -1; void push(int value) { stack[++top] = value; } int pop() { return stack[top--]; } int isEmpty() { return top == -1; } ``` 接下来,我们实现邻接矩阵转邻接表的函数: ```c void MatToList(int mat[MAX_VERTEX_NUM][MAX_VERTEX_NUM], ALGraph *G) { G->vexnum = 0; G->arcnum = 0; // 初始化邻接表 for (int i = 0; i < MAX_VERTEX_NUM; i++) { G->vertices[i].firstedge = NULL; } // 填充邻接表 for (int i = 0; i < MAX_VERTEX_NUM; i++) { for (int j = 0; j < MAX_VERTEX_NUM; j++) { if (mat[i][j] != 0) { EdgeNode *edge = (EdgeNode *)malloc(sizeof(EdgeNode)); edge->adjvex = j; edge->next = G->vertices[i].firstedge; G->vertices[i].firstedge = edge; G->arcnum++; } } if (G->vertices[i].firstedge != NULL) { G->vexnum++; } } } ``` 然后,我们实现DFS算法: ```c void DFS(ALGraph G, int v, int visited[]) { visited[v] = 1; printf("%d ", v); EdgeNode *p = G.vertices[v].firstedge; while (p != NULL) { if (!visited[p->adjvex]) { DFS(G, p->adjvex, visited); } p = p->next; } } void DFSTraverse(ALGraph G) { int visited[MAX_VERTEX_NUM] = {0}; for (int i = 0; i < G.vexnum; i++) { if (!visited[i]) { DFS(G, i, visited); } } } ``` 最后,我们实现使用栈进行DFS的函数: ```c void DFS_Iterative(ALGraph G, int v, int visited[]) { push(v); while (!isEmpty()) { int current = pop(); if (!visited[current]) { visited[current] = 1; printf("%d ", current); EdgeNode *p = G.vertices[current].firstedge; while (p != NULL) { if (!visited[p->adjvex]) { push(p->adjvex); } p = p->next; } } } } void DFSTraverse_Iterative(ALGraph G) { int visited[MAX_VERTEX_NUM] = {0}; for (int i = 0; i < G.vexnum; i++) { if (!visited[i]) { DFS_Iterative(G, i, visited); } } } ``` 现在,让我们测试这个转换: ```c int main() { int mat[MAX_VERTEX_NUM][MAX_VERTEX_NUM] = { {0,1,1,0}, {1,0,1,1}, {1,1,0,1}, {0,1,1,0} }; ALGraph G; MatToList(mat, &G); printf("DFS using recursion: "); DFSTraverse(G); printf("\n"); printf("DFS using stack: "); DFSTraverse_Iterative(G); printf("\n"); return 0; } ``` 这段代码首先定义了一个图的邻接矩阵,然后将其转换为邻接表。之后,我们分别使用递归和栈两种方式进行了DFS遍历。 通过比较两种DFS序列,我们可以验证转换的正确性。如果两种序列一致,则说明转换是正确的。