图的邻接矩阵存储和遍历

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

相关问题

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

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

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

邻接矩阵深度优先遍历

邻接矩阵深度优先遍历的基本思想是从某个顶点开始，沿着一条未被访问过的边走到未访问过的顶点，直到该顶点没有未访问过的邻接点为止，然后回溯到前一个顶点，继续寻找其未访问过的邻接点，直到所有顶点都被访问过为止。

具体实现时，我们可以使用一个栈来存储当前正在访问的顶点，每次从栈顶取出一个顶点进行处理，将其未访问过的邻接点入栈，直到栈为空为止。

以下是邻接矩阵深度优先遍历的伪代码：

DFS(v)
    visited[v] = true // 标记当前顶点已被访问
    for i = 1 to n do
        if graph[v][i] = 1 and visited[i] = false then // 如果当前顶点与顶点i之间有边且i未被访问
            DFS(i) // 递归访问顶点i

其中，`graph`为邻接矩阵，`visited`为记录顶点是否被访问过的数组，`n`为顶点个数，`v`为当前正在访问的顶点。