图遍历-邻接矩阵存储

图遍历是一种在图中访问所有顶点的过程，通常有深度优先搜索（DFS）和广度优先搜索（BFS）两种方法。邻接矩阵是图的一种常见数据结构，用于表示图中任意两个顶点之间是否存在边。在这个矩阵中，行代表起点，列表代表终点，每个元素的值通常是0（无边）或1（有边）。

具体到邻接矩阵存储，图的邻接矩阵是一个二维数组，其中：
- 对角线元素通常为0，因为不存在一个顶点与自身直接相连；
- 非对角线元素如果为1，则表示对应顶点之间存在一条边；
- 如果元素为0，则表示没有连接。

图遍历使用邻接矩阵时的操作如下：
1. **深度优先搜索 (DFS)**:
- 从给定起点开始，检查其相邻节点，标记并进入未访问节点。
- 对于每个相邻节点，递归地执行DFS直到遍历完整张矩阵。
- **广度优先搜索 (BFS)**:
- 用队列实现，先将起点放入队列，然后逐个取出节点，将其相邻节点（矩阵中的非对角线）加入队列，直到队列为空。

相关问题

图上的广度优先遍历-邻接矩阵存图

广度优先遍历是一种用于图的遍历的算法。在邻接矩阵存储图中，广度优先遍历通过逐层访问图中的顶点，先访问与起始顶点直接相邻的顶点，然后再访问与这些顶点直接相邻的顶点，以此类推，直到遍历完所有可达的顶点。具体实现广度优先遍历的算法如下：

1. 创建一个大小为顶点数的布尔类型的数组visited，用于标记顶点是否已被访问。
2. 创建一个队列queue，用于存储待访问的顶点。
3. 将起始顶点i标记为已访问，并将其入队。
4. 当队列不为空时，执行以下步骤：
- 出队一个顶点v，并输出该顶点。
- 遍历与顶点v直接相邻的顶点w，若顶点w未被访问，则将其标记为已访问，并将其入队。
5. 重复步骤4直到队列为空。

以上就是邻接矩阵存图上的广度优先遍历算法的具体步骤。

R6-1 邻接矩阵存储图的深度优先遍历

以下是邻接矩阵存储图的深度优先遍历的Python实现：

def DFS(MGraph, visited, v):
    visited[v] = True
    print(v, end=' ')
    for w in range(MGraph.Nv):
        if not visited[w] and MGraph.G[v][w] != 0:
            DFS(MGraph, visited, w)

def DFSTraverse(MGraph):
    visited = [False] * MGraph.Nv
    for v in range(MGraph.Nv):
        if not visited[v]:
            DFS(MGraph, visited, v)

其中，`MGraph`是邻接矩阵存储的图，`visited`是记录每个顶点是否被访问过的数组，`v`是当前访问的顶点。`DFS`函数是深度优先遍历的核心代码，它首先将当前顶点标记为已访问，并输出该顶点的编号。然后遍历该顶点的所有邻接点，如果邻接点未被访问过且与当前顶点有边相连，则递归访问该邻接点。`DFSTraverse`函数是深度优先遍历的入口，它遍历图中的所有连通块，对于每个连通块，从一个未被访问的顶点开始进行深度优先遍历。