构造无向图的邻接矩阵

构造无向图的邻接矩阵需要进行以下步骤：

1. 确定图中顶点的数量。
2. 创建一个 n x n 的矩阵，其中 n 为顶点的数量。
3. 对于每条边 (i, j)，将矩阵中第 i 行第 j 列和第 j 行第 i 列的值都设为 1，表示顶点 i 和顶点 j 之间有一条边。
4. 对于没有边相连的顶点，矩阵中对应的位置为 0。

例如，假设有以下无向图：

     +-- 2
     |    
1 -- + -- 3
     |
     +-- 4

该图有 4 个顶点，因此邻接矩阵为 4 x 4 的矩阵。对于每条边，我们将矩阵中对应的位置的值设为 1，没有边相连的顶点对应的位置设为 0，得到如下邻接矩阵：

   1  2  3  4
1  0  1  0  0
2  1  0  1  0
3  0  1  0  1
4  0  0  1  0

其中第 i 行第 j 列和第 j 行第 i 列的值都为 1，表示顶点 i 和顶点 j 之间有一条边。

相关问题

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

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

在C语言中，我们可以使用二维数组或动态分配的二维指针结构来创建无向图的邻接矩阵存储。这里我会提供一个基本的示例，并解释如何执行上述操作：

1. **建立无向图的邻接矩阵存储**：

#define V 5 // 图中的顶点数
int graph[V][V]; // 初始化一个二维数组，用于存储邻接矩阵

// 添加边的功能
void addEdge(int src, int dest) {
    graph[src][dest] = 1; // 如果src到dest有边，将对应位置设置为1（无向图）
    graph[dest][src] = 1; // 对称地，dest到src也有边
}

2. **输出邻接矩阵**：

void printMatrix() {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

3. **基于图邻接矩阵的深度优先遍历（DFS）**：

void DFS(int start) {
    int visited[V] = {0}; // 初始化访问数组
    DFSUtil(start, visited, graph);
}

void DFSUtil(int v, int visited[], int graph[]) {
    visited[v] = 1;
    printf("%d ", v);

    // 访问v的所有未访问的邻居
    for (int i = 0; i < V; i++) {
        if (visited[i] == 0 && graph[v][i] == 1) {
            DFSUtil(i, visited, graph);
        }
    }
}

4. **基于图邻接矩阵的广度优先遍历（BFS）**：

void BFS(int start) {
    int queue[V]; // 用于BFS的队列
    int level[V] = {0}; // 记录每个节点的层级
    int front = -1, rear = -1;

    // 初始化
    queue[++rear] = start;
    level[start] = 0;

    while (front != rear) {
        int u = queue[++front]; // 取出队首节点
        printf("%d ", u);

        // 将u的所有未访问的邻居加入队列，并更新它们的层级
        for (int i = 0; i < V; i++) {
            if (graph[u][i] == 1 && level[i] == 0) {
                queue[++rear] = i;
                level[i] = level[u] + 1;
            }
        }
    }
}