• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

算法学习-图的广度优先遍历(BFS)(C++)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

广度优先遍历是非经常见和普遍的一种图的遍历方法了,除了BFS还有DFS也就是深度优先遍历方法。我在我下一篇博客里面会写。

遍历过程

相信每一个看这篇博客的人,都能看懂邻接链表存储图。
不懂的人。请先学下图的存储方法。在我的之前博客里。
传送门:图表示方法

然后我们如果有一个图例如以下:

节点1->3->NULL
节点2->NULL
节点3->2->4->NULL
节点4->1->2->NULL

这样我们已经知道这是一个什么图了。

如果我们从节点1開始遍历。
首先把节点1变成灰色,然后增加到队列(queue)中,然后把全部与节点1的点变成灰色同一时候增加到队列中。

输出并弹出队首元素节点1并把节点1的颜色变为黑色。

然后再把队首元素的相邻节点增加到队列中。然后继续输出并弹出队首元素依次类推。到队列空为止。

代码实现

以下是我写的代码实现。比較简单。

我有写一部分凝视。

//
//  main.cpp
//  BFS
//
//  Created by Alps on 15/3/30.
//  Copyright (c) 2015年 chen. All rights reserved.
//

#include <iostream>
#include <queue>

#ifndef Vertex
#define Vertex int
#endif

#ifndef NumVertex
#define NumVertex 4
#endif

#define WHITE 0
#define GRAY 1
#define BLACK 2

using namespace std;

struct node{
    int val;
    int weight;
    node* next;
    node(int v, int w): val(v), weight(w), next(NULL){}
};

typedef node* VList;

struct TableEntery{
    VList header;
    Vertex color;
};

typedef TableEntery Table[NumVertex+1];

void InitTableEntry(Vertex start, Table T){ //init the Graph
    Vertex OutDegree = 0;
    VList temp = NULL;

    for (int i = 1; i <= NumVertex; i++) {
        scanf("%d",&OutDegree); // input the out degree of vertex
        T[i].header = NULL;
        T[i].color = WHITE;
        for (int j = 0; j < OutDegree; j++) {
            temp = (VList)malloc(sizeof(struct node));
            scanf("%d %d",&temp->val, &temp->weight);
            temp->next = T[i].header;
            T[i].header = temp;
        }
    }

    T[start].color = GRAY; //init the start vertex color to gray
}

void BFS(Vertex start, Table T){
    queue<Vertex> Q;
    Q.push(start);
    VList temp = NULL;
    while (!Q.empty()) { //if queue is not empty, then the bfs is not over
        temp = T[Q.front()].header; //find the front of the queue
        while (temp) { //if the front vertex has next vertex
            if (T[temp->val].color == WHITE) {
                Q.push(temp->val); //push the white vertex to queue
                T[temp->val].color = GRAY; //change the color to gray
            }
            temp = temp->next;
        }
        printf("%d ",Q.front()); //output the vertex
        T[Q.front()].color = BLACK; //then change color
        Q.pop();
    }
}

int main(int argc, const char * argv[]) {
    Table T;
    InitTableEntry(1, T);
    BFS(1, T);
    return 0;
}

上面的代码就是BFS了。事实上还有非常多其它实现方法。

都能够。


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
《C与指针》读后感发布时间:2022-07-14
下一篇:
C++两个类相互包含引用的问题发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap