无向图的两种遍历C++

无向图的两种遍历方法为深度优先搜索和广度优先搜索。

深度优先搜索（DFS）是一种先访问一个顶点，然后再依次访问这个顶点的每个邻接点，并且对于每个邻接点，重复以上过程的遍历方法。在遍历过程中，需要使用一个访问数组来记录每个顶点是否被访问过，以避免出现重复访问的情况。

广度优先搜索（BFS）是一种从起始顶点开始，先访问起始顶点的所有邻接点，再依次访问这些邻接点的邻接点，以此类推的遍历方法。在遍历过程中，同样需要使用一个访问数组来记录每个顶点是否被访问过，以避免出现重复访问的情况。BFS需要使用队列来实现，先将起始顶点入队，然后依次取出队头元素，访问其所有邻接点，并将未访问的邻接点入队，直到队列为空为止。

相关问题

无向图的遍历c++

无向图的遍历有两种方法：深度优先搜索（DFS）和广度优先搜索（BFS）。下面是两种方法的C++代码实现：

1.深度优先搜索（DFS）

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int h[N], e[N], ne[N], idx;
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    st[u] = true;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

int main()
{
    memset(h, -1, sizeof h);    int n, m;
    cin >> n >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
        if (!st[i])
        {
            cnt ++ ;
            dfs(i);
        }

    cout << cnt << endl;

    return 0;
}

2.广度优先搜索（BFS）

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int h[N], e[N], ne[N], idx;
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs(int u)
{
    queue<int> q;
    q.push(u);
    st[u] = true;

    while (q.size())
    {
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (!st[j])
            {
                st[j] = true;
                q.push(j);
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    int n, m;
    cin >> n >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
        if (!st[i])
        {
            cnt ++ ;
            bfs(i);
        }

    cout << cnt << endl;

    return 0;
}

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

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

无向图的邻接矩阵表示法可以用一个二维数组来表示，其中矩阵的行列数都等于图的顶点数，矩阵中的元素表示两个顶点之间是否有边相连，通常用 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;
}

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