图的邻接矩阵存储和遍历

邻接矩阵是一种用于存储图的数据结构，其中图中的节点被表示为矩阵中的行和列，而矩阵中的每个元素则表示对应节点之间的边。如果两个节点之间有边，则该元素的值为1，否则为0。

下面是一个简单的有向图的邻接矩阵表示：

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

在这个示例中，节点0有一条指向节点1的边和一条指向节点3的边，节点1有一条指向节点2的边和一条指向节点3的边，节点2有一条指向节点0的边，节点3有一条指向节点2的边。

遍历邻接矩阵通常需要使用两个嵌套的循环来遍历矩阵中的每个元素。在遍历过程中，可以检查每个元素的值来确定节点之间是否有边。以下是一个简单的示例代码，用于遍历上述邻接矩阵并输出图中的所有边：

graph = [[0, 1, 0, 1],
         [0, 0, 1, 1],
         [1, 0, 0, 0],
         [0, 0, 1, 0]]

for i in range(len(graph)):
    for j in range(len(graph[i])):
        if graph[i][j] == 1:
            print(f"{i} -> {j}")

输出：

0 -> 1
0 -> 3
1 -> 2
1 -> 3
2 -> 0
3 -> 2

相关问题

头歌实训作业答案c++图的邻接矩阵存储及遍历操作

头歌实训作业中的C++图数据结构通常使用邻接矩阵来表示，它是一个二维数组，其中行代表起点，列表示终点，值为边的存在与否（0或1）。以下是邻接矩阵存储的基本概念：

1. 存储：邻接矩阵是以二维数组的形式存在的，如果图是有向图，则矩阵是对称的（即A[i][j] = A[j][i]），无向图则非对称（A[i][j]和A[j][i]独立表示两个方向的边）。每个元素A[i][j] = 1 表示节点i到节点j有边相连，0表示没有。

2. 遍历操作：
- **广度优先搜索(BFS)**：从给定源节点开始，逐层扩展访问节点。可以使用队列来辅助实现，初始化队列为源节点，然后不断出队并添加其未访问过的相邻节点。

   void bfs(int start) {
       queue<int> q;
       vector<bool> visited(V, false);
       q.push(start);
       visited[start] = true;
       
       while (!q.empty()) {
           int u = q.front(); q.pop();
           // 访问u的所有邻居并标记为已访问
           for (int v : adj[u]) {
               if (!visited[v]) {
                   visited[v] = true;
                   q.push(v);
               }
           }
       }
   }

- **深度优先搜索(DFS)**：从给定源节点开始，尽可能深地探索路径。可以使用栈或递归实现，先访问当前节点的所有相邻节点，然后再回溯。

   void dfs(int start) {
       vector<bool> visited(V, false);
       dfs_util(start, visited);
   }
   void dfs_util(int node, vector<bool>& visited) {
       visited[node] = true;
       // 探索所有相邻节点
       for (int neighbor : adj[node]) {
           if (!visited[neighbor])
               dfs_util(neighbor, visited);
       }
   }

邻接矩阵深度优先遍历和广度优先遍历

邻接矩阵是一种图的存储结构，它可以用来表示有限个顶点之间的关系。邻接矩阵的深度优先遍历和广度优先遍历是图的两种基本遍历方式。

邻接矩阵的深度优先遍历（Depth First Search，DFS）：
深度优先遍历是一种用于遍历或搜索树或图的算法。在这个算法中，首先访问根节点，然后递归地访问每个子节点。当访问一个节点时，将其标记为已访问，以避免重复访问。深度优先遍历使用栈来实现，因此它是一种先进后出（Last In First Out，LIFO）的算法。

下面是邻接矩阵的深度优先遍历的Python代码示例：

def DFS(graph, start):
    visited = set()  # 用集合来存储已经访问过的节点
    stack = [start]  # 用列表来模拟栈
    while stack:
        vertex = stack.pop()  # 取出栈顶元素
        if vertex not in visited:
            visited.add(vertex)  # 标记为已访问
            print(vertex, end=' ')
            # 将未访问的邻居节点入栈
            stack.extend([i for i in range(len(graph[vertex])) if graph[vertex][i] and i not in visited])

# 示例
graph = [[0, 1, 1, 0],
         [1, 0, 0, 1],
         [1, 0, 0, 1],
         [0, 1, 1, 0]]
DFS(graph, 0)  # 输出：0 1 3 2

邻接矩阵的广度优先遍历（Breadth First Search，BFS）：
广度优先遍历是一种用于遍历或搜索树或图的算法。在这个算法中，首先访问根节点，然后逐层访问每个子节点。当访问一个节点时，将其标记为已访问，以避免重复访问。广度优先遍历使用队列来实现，因此它是一种先进先出（First In First Out，FIFO）的算法。

下面是邻接矩阵的广度优先遍历的Python代码示例：

from collections import deque

def BFS(graph, start):
    visited = set()  # 用集合来存储已经访问过的节点
    queue = deque([start])  # 用双端队列来模拟队列
    while queue:
        vertex = queue.popleft()  # 取出队首元素
        if vertex not in visited:
            visited.add(vertex)  # 标记为已访问
            print(vertex, end=' ')
            # 将未访问的邻居节点入队
            queue.extend([i for i in range(len(graph[vertex])) if graph[vertex][i] and i not in visited])

# 示例
graph = [[0, 1, 1, 0],
         [1, 0, 0, 1],
         [1, 0, 0, 1],
         [0, 1, 1, 0]]
BFS(graph, 0)  # 输出：0 1 2 3