您的位置: 首页  >  文章  >  图的遍历——dfs OR bfs

图的遍历——dfs OR bfs

分类: 文章 • 2024-11-11 12:51:40

1.什么是图的遍历？

从图的某一个顶点出发，沿图中的路径依次访问图中的所有顶点，并且使得图中所有顶点都恰好被访问一次，这一过程即为图的遍历。
注意：这里讨论的图特指连通图上进行遍历。

2.图的遍历——dfs(深度优先搜索)简介：

开始我们假设图上所有的顶点都未被访问，选择图中任一顶点，开始执行以下操作：
1.访问当前顶点v，并将该顶点标记为已访问。
2.遍历与顶点v相邻的所有顶点c，然后对顶点v所有尚未被访问的相邻顶点c，递归地去执行第一步操作。如果当前顶点已经没有被访问的相邻顶点了，则说明该分支搜索结束，沿通路回溯到顶点v。
3.此时如果还有相邻顶点没有被访问，则从该顶点继续开始深度优先搜索。直到所有的顶点都被访问。

从上述方法可以看出，深度优先搜索算法总是沿着图的某一深度进行遍历，尽可能深的搜索与当前相邻的顶点，如果相邻的顶点都已被访问则回溯到上一层，直至所有顶点都已被访问。
看一个动图：
图的遍历——dfs OR bfs

3.图的遍历——dfs模板代码实现：

对预算法的具体实现，因深度优先搜索的优先遍历深度更大的顶点，所以我们可以借助数据结构栈来实现：
1.将要访问的第一个顶点v入栈，然后首先对其进行访问。
2.将顶点v出栈，依次将与顶点v相邻且未被访问的顶点c压入栈中。
3.重复第一步操作，直至栈空。

Code：

#include <iostream>
#include <string.h>
using namespace std;

const int MAX_N = 100;
const int MAX_M = 10000;
struct edge
{
    int v, next;  
    int len;  //边的权值
} E[MAX_M];

int p[MAX_N], eid;

void init()
{
    memset(p, -1, sizeof(p));
    eid = 0;
}

void insert(int u, int v, int len)
{
    E[eid].v = v;
    E[eid].len = len;
    E[eid].next = p[u];
    p[u] = eid++;
}

bool vst[MAX_N];  //标记是否访问过

void dfs(int u)
{
    cout << "visiting " << u << endl;
    vst[u] = true;
    for (int i = p[u]; i + 1; i = E[i].next)
    {
        if (!vst[E[i].v])
        {
            dfs(E[i].v);
        }
    }
}

int main()
{
    init();
    insert(1, 2, 10);
    insert(1, 3, 5);
    insert(2, 3, 1);
    insert(3, 5, 10);
    insert(3, 4, 6);
    insert(5, 4, 11);
    memset(vst, false, sizeof(vst));
    dfs(1);
    return 0;
}

4.图的遍历——bfs简介：

图的遍历——dfs OR bfs
从遍历的过程中我们可以看到，广度优先搜索总是从某一起点出发逐层进行搜素，每一层的起点到顶点的边数都是一样的。这一过程正好解释了为什么广度优先搜索可以求出图中的一点到各点的最短距离，以及求出两点之间的最优路径等问题。
看一下动图：
图的遍历——dfs OR bfs

5.图的遍历——bfs模板Code：

结合队列先进先出的特性，我们可以借助队列来具体实现广度优先搜索：
1.任意选择一个顶点v作为起点，加入队列。
2.访问队首元素并标记，将其从队列中删除。
3.遍历与顶点v相邻且未被访问的所有顶点c1,c2,…,ck,并依次加入到队列中。
4.重复步骤2、3，直到队列为空。

Code:

#include <iostream>
#include <string.h>
using namespace std;

const int MAX_N = 100;
const int MAX_M = 10000;

struct edge
{
    int v, next;
    int len;
} E[MAX_M];

int p[MAX_N], eid;

void init()
{
    memset(p, -1, sizeof(p));
    eid = 0;
}

void insert(int u, int v, int len)
{
    E[eid].v = v;
    E[eid].len = len;
    E[eid].next = p[u];
    p[u] = eid++;
}

bool vst[MAX_N];
void bfs(int v)
{
    memset(vst, false, sizeof(vst));
    queue<int> q;
    q.push(v);
    vst[v] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        cout << "visiting " << u << endl;
        for (int i = p[u]; i + 1; i = E[i].next)
        {
            if (!vst[E[i].v])
            {
                vst[E[i].v] = 1;
                q.push(E[i].v);
            }
        }
    }
}

int main() {
    init();
    insert(1, 2, 10);
    insert(1, 3, 5);
    insert(2, 3, 1);
    insert(3, 5, 10);
    insert(3, 4, 6);
    insert(5, 4, 11);
    bfs(1);
    return 0;
}

欢迎关注ly’s blog

相关推荐