C++实现广度优先遍历图

时间:2021-12-26 03:15:59

本文实例为大家分享了C++实现广度优先遍历图的具体代码,供大家参考,具体内容如下

广度优先遍历

C++实现广度优先遍历图

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void bfs(int start, int parent[], int dist[], int seen[], int visited[]) {
    std::queue <int> q;//建立数据队列q
    int v;
    
    q.push(start);    //让开始序列入栈
    parent[start] = start;      // 开始节点的父节点是开始节点
    dist[start] = 0;            // 初始化距离向量为-1
    seen[start] = 1;      
 
    while(!q.empty()) {         //如果队列非空
        v = q.front(); q.pop();   //令V是队列的最前端,并将其出栈
        if(visited[v])          // 如果visited[v]=1, continue.
            continue;
        visited[v] = 1;         //否则令visited[v]=1
        std::cout << v << '\n';//输出显示当前节点
 
        // 遍历v的所有相邻节点
        for(int i = 0; i < graph[v].size(); i++) {
            // 如果v的第i个相邻节点的i并没有访问过
            if(!visited[graph[v][i]]) {
 
                // 如果这个没有访问过的节点没有被看过
                if(!seen[graph[v][i]]) {
                //压入栈,距离+1,设置父节点
                    q.push(graph[v][i]);
                    dist[graph[v][i]] = 1 + dist[v];
                    parent[graph[v][i]] = v;
                    // 如果已经访问过,令seen=1.
                    seen[graph[v][i]] = 1;
                }
            }
            else {
 
                // 如果节点已经被访问了,选择距离最小的
                if(dist[v] + 1 < dist[graph[v][i]]) {
                    dist[graph[v][i]] = 1 + dist[graph[v][i]];
                    parent[graph[v][i]] = v;
                }
            }
        }
    }
}

主函数

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int main() {
 
    int n = 8;          // 图中的节点数
    graph = std::vector <std::vector <int> > (n);
    
    // 图的邻接表
    graph[0] = {1, 2};
    graph[1] = {0, 2, 3};
    graph[2] = {0, 1, 5, 6};
    graph[3] = {1, 2, 4};
    graph[4] = {3};
    graph[5] = {2};
    graph[6] = {2, 7};
    graph[7] = {6};
 
    /* - parent[i] = parent of 'i' in BFS traversal.
       - dist[i] = 从开始到I节点的最短距离shortest distance of 'i' from 'start'.
       - If seen[i] == 1, 节点i已经进入过队列'i' has entered the queue once
       - If visited[i] == 1, 节点i已经进入队列,并且所有相邻节点都已经进入过队列
    */
    int parent[n+1], dist[n+1], seen[n+1], visited[n+1];
    memset(parent, -1, sizeof(parent));//父节点初始化为-1
    memset(dist, -1, sizeof(dist));//距离向量初始化为-1
    memset(seen, 0, sizeof(seen));
    memset(visited, 0, sizeof(visited));//seen用于判断该节点是否访问过
 
    int start = 0;      // 开始节点
    bfs(start, parent, dist, seen, visited);
 
    return 0;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:https://blog.csdn.net/weixin_43591948/article/details/120316344