1.无向图采用邻接矩阵进行存储，完成以下操作 (1) 建立无向图的邻接矩阵存储 (2) 输出邻接矩阵 (3) 基于图邻接矩阵的深度优先遍历 （4） 基于图邻接矩阵的广度优先遍历

无向图使用邻接矩阵存储时，它是一个二维数组，其中的行和列分别代表图中的顶点，矩阵的元素表示对应顶点之间的连接关系。如果两个顶点之间存在边，则对应位置的值为1或true；若不存在，则为0或false。 (1) **建立无向图的邻接矩阵存储**： 假设我们有一个无向图G，其顶点集合是V={v1, v2, ..., vn}。邻接矩阵A是一个n×n的矩阵，A[i][j]表示顶点vi到vj是否有边。初始时，所有元素都设为0，然后根据实际的边来填充： ``` A = [ [0, 0, ..., 0], [0, 0, ..., 0], ..., [0, 0, ..., 0] ] ``` 每添加一条边(vi, vj)，将A[i][j]和A[j][i]（因为无向图，边是双向的）置为1。 (2) **输出邻接矩阵**： 遍历并打印矩阵A，例如： ```plaintext for i in range(n): for j in range(n): if A[i][j]: print(f'({i+1}, {j+1}): 1', end='\t') print() ``` (3) **基于图邻接矩阵的深度优先遍历（DFS）**： DFS可以从任意顶点开始，利用栈数据结构实现： ```python def DFS(matrix, start, visited=None): if visited is None: visited = [False] * n visited[start] = True print(start + 1, end=' ') for neighbor in range(n): if matrix[start][neighbor] and not visited[neighbor]: DFS(matrix, neighbor, visited) ``` (4) **基于图邻接矩阵的广度优先遍历（BFS）**： BFS使用队列，从起始顶点开始逐层遍历： ```python from collections import deque def BFS(matrix, start): visited = [False] * n queue = deque([start]) visited[start] = True while queue: vertex = queue.popleft() print(vertex + 1, end=' ') for neighbor in range(n): if matrix[vertex][neighbor] and not visited[neighbor]: visited[neighbor] = True queue.append(neighbor) ```

对于无向图采用邻接矩阵进行存储，我们可以按照如下步骤进行操作： （1）建立无向图的邻接矩阵存储 邻接矩阵是一个二维数组，矩阵的行和列分别表示图中的顶点，数组中的值表示两个顶点之间是否有边相连。如果顶点i和顶点j之间有边相连，则邻接矩阵中第i行第j列和第j行第i列的元素都为1，否则为0。 具体实现可以参考以下代码： ```c #define MAX_VERTEX_NUM 20 // 最大顶点数 typedef struct { char vertex[MAX_VERTEX_NUM]; // 顶点数组 int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vertex_num; // 顶点数 int edge_num; // 边数 } Graph; void createGraph(Graph *G) { int i, j; printf("请输入顶点数和边数："); scanf("%d %d", &(G->vertex_num), &(G->edge_num)); getchar(); // 吸收回车符 printf("请输入顶点信息："); for (i = 0; i < G->vertex_num; i++) { scanf("%c", &(G->vertex[i])); getchar(); // 吸收回车符 } for (i = 0; i < G->vertex_num; i++) { for (j = 0; j < G->vertex_num; j++) { G->edge[i][j] = 0; // 初始化邻接矩阵 } } printf("请输入边信息：\n"); for (i = 0; i < G->edge_num; i++) { int v1, v2; printf("请输入第%d条边(v1, v2)的顶点序号：", i+1); scanf("%d %d", &v1, &v2); G->edge[v1][v2] = 1; G->edge[v2][v1] = 1; // 对称矩阵赋值 } } ``` （2）输出邻接矩阵 输出邻接矩阵只需要遍历二维数组即可。 ```c void printGraph(Graph G) { int i, j; printf("邻接矩阵为：\n"); for (i = 0; i < G.vertex_num; i++) { for (j = 0; j < G.vertex_num; j++) { printf("%d ", G.edge[i][j]); } printf("\n"); } } ``` （3）基于邻接矩阵的深度优先遍历 深度优先遍历需要借助栈来实现，遍历过程中需要标记已经访问过的节点。 ```c void DFS(Graph G, int v, int *visited) { printf("%c ", G.vertex[v]); visited[v] = 1; int i; for (i = 0; i < G.vertex_num; i++) { if (G.edge[v][i] == 1 && visited[i] == 0) { DFS(G, i, visited); } } } void DFSTraverse(Graph G) { int visited[MAX_VERTEX_NUM] = {0}; // 初始化所有节点未访问 int i; printf("深度优先遍历结果为："); for (i = 0; i < G.vertex_num; i++) { if (visited[i] == 0) { DFS(G, i, visited); } } } ``` （4）基于邻接矩阵的广度优先遍历 广度优先遍历需要借助队列来实现，同样需要标记已经访问过的节点。 ```c void BFS(Graph G, int v, int *visited) { Queue Q; initQueue(&Q); // 初始化队列 printf("%c ", G.vertex[v]); visited[v] = 1; enQueue(&Q, v); // 入队 while (!isQueueEmpty(Q)) { // 队列不为空时循环 int u = deQueue(&Q); // 出队 int i; for (i = 0; i < G.vertex_num; i++) { if (G.edge[u][i] == 1 && visited[i] == 0) { printf("%c ", G.vertex[i]); visited[i] = 1; enQueue(&Q, i); // 入队 } } } } void BFSTraverse(Graph G) { int visited[MAX_VERTEX_NUM] = {0}; // 初始化所有节点未访问 int i; printf("广度优先遍历结果为："); for (i = 0; i < G.vertex_num; i++) { if (visited[i] == 0) { BFS(G, i, visited); } } } ```