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

无向图使用邻接矩阵存储时，每个顶点用一个行和一个列对应，矩阵中的元素表示两个顶点之间是否存在边。以下是基于邻接矩阵进行操作的详细介绍：

1. **建立无向图的邻接矩阵存储**:
- 对于无向图，邻接矩阵是对称的。如果顶点A和B之间有边，则矩阵A[i][j]和A[j][i]都为1；没有边则都是0。
- 初始化一个二维数组，大小为顶点数乘以顶点数，然后根据图中实际的边关系填充矩阵。

2. **输出邻接矩阵**:
- 遍历整个矩阵，打印每个元素。由于矩阵是对称的，你可以只遍历上三角或下三角，以避免重复输出。

3. **基于图邻接矩阵的深度优先遍历（DFS）**:
- 从任意一个起点开始，设该顶点为当前节点（标记为已访问）。
- 遍历矩阵中对应的行或列，找到所有未访问的邻接节点。
- 对每个邻接节点递归地执行DFS。
- 递归结束后，移除当前节点的标记，回到上一个邻接节点。

4. **基于图邻接矩阵的广度优先遍历（BFS）**:
- 从任意一个起点开始，将该顶点放入队列中（标记为已访问）。
- 取出队首节点，将其所有未访问的邻接节点加入队列并标记为已访问。
- 重复此过程，直到队列为空。
- 在遍历时，记录路径信息，以便输出结果。

相关问题

无向图采用邻接矩阵进行存储，完成以下操作 (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，例如：

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可以从任意顶点开始，利用栈数据结构实现：

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使用队列，从起始顶点开始逐层遍历：

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）建立无向图的邻接矩阵存储（2）输出邻接矩阵（3）基于邻接矩阵的深度优先遍历（4）基于邻接矩阵的广度优先遍历

对于无向图采用邻接矩阵进行存储，我们可以按照如下步骤进行操作：

（1）建立无向图的邻接矩阵存储

邻接矩阵是一个二维数组，矩阵的行和列分别表示图中的顶点，数组中的值表示两个顶点之间是否有边相连。如果顶点i和顶点j之间有边相连，则邻接矩阵中第i行第j列和第j行第i列的元素都为1，否则为0。

具体实现可以参考以下代码：

#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）输出邻接矩阵

输出邻接矩阵只需要遍历二维数组即可。

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）基于邻接矩阵的深度优先遍历

深度优先遍历需要借助栈来实现，遍历过程中需要标记已经访问过的节点。

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）基于邻接矩阵的广度优先遍历

广度优先遍历需要借助队列来实现，同样需要标记已经访问过的节点。

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);
        }
    }
}