如果使用邻接矩阵 那么应该如何遍历图

如果使用邻接矩阵来存储图，那么可以使用两种方式来遍历图：深度优先遍历（DFS）和广度优先遍历（BFS）。

对于无向图和有向图，DFS 和 BFS 的遍历方式基本相同，只是在遍历顺序上有所区别。以下以无向图为例，介绍如何使用邻接矩阵进行 DFS 和 BFS 的遍历。

DFS 遍历：

1. 从任意一个节点开始遍历，标记该节点为已访问。
2. 遍历该节点的所有邻接节点，如果某个邻接节点未被访问，则以该邻接节点为起点进行 DFS 遍历。
3. 重复步骤 2，直到所有节点都被访问。

BFS 遍历：

1. 从任意一个节点开始遍历，标记该节点为已访问，并将该节点入队。
2. 取出队首节点，遍历该节点的所有邻接节点，如果某个邻接节点未被访问，则将该节点标记为已访问，并将其入队。
3. 重复步骤 2，直到队列为空。

相关问题

无向图邻接矩阵深度优先遍历

好的，我可以为您解答这个问题。

无向图的邻接矩阵表示法可以用一个二维数组来表示，其中矩阵的行列数都等于图的顶点数，矩阵中的元素表示两个顶点之间是否有边相连，通常用 0 或 1 来表示。

深度优先遍历（Depth First Search，DFS）是一种常用的图遍历算法，主要思想是从某个顶点开始，沿着一条路径遍历直到不能继续为止，然后返回到前一级顶点，继续沿着另一条路径遍历，直到所有的顶点都被访问过。

无向图邻接矩阵深度优先遍历的步骤如下：

1. 访问起始顶点，并将其标记为已访问；
2. 从起始顶点出发，依次遍历它的邻接点；
3. 对于每个邻接点，如果它未被访问，则递归访问它，并将其标记为已访问；
4. 重复步骤 2 和步骤 3，直到所有顶点都被访问过。

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

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 100;

int n; // 顶点数
int G[MAXN][MAXN]; // 邻接矩阵
bool visited[MAXN]; // 标记数组

void dfs(int v) {
    visited[v] = true; // 标记当前顶点已访问
    cout << v << " "; // 输出当前顶点

    for (int i = 0; i < n; i++) {
        if (G[v][i] && !visited[i]) { // 如果有边相连且未访问过
            dfs(i); // 递归访问邻接点
        }
    }
}

int main() {
    memset(G, 0, sizeof(G)); // 初始化邻接矩阵
    memset(visited, false, sizeof(visited)); // 初始化标记数组

    // 读入无向图的顶点数和边数
    int m;
    cin >> n >> m;

    // 读入边的信息，建立邻接矩阵
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u][v] = G[v][u] = 1; // 无向图的边是双向的
    }

    // 从顶点 0 开始深度优先遍历
    dfs(0);

    return 0;
}

以上代码实现了无向图邻接矩阵深度优先遍历，并输出了遍历结果。

图的邻接矩阵存储和遍历

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