BFS 广度优先算法的笔记(python、C++)

时间:2020-7-28 作者:admin


欢迎各路大佬对小生的算法进行批判!

个人所学(持续进展中)

学习了图的BFS算法,教学为python,自己使用C++改写。

新的改变

  • 2020.7.27 新增了python、C++的BFS代码;
  • 未完待续……

程序简介

功能:通过以下代码,选取一个图、起始点,从起始点开始使用广度优先算法(BFS)遍历整个图,最后输出遍历过程。


  • BFS 广度优先算法的笔记(python、C++)

python代码及运行结果截图

#代码来源请详见文章末尾的“学习资源”

graph={
	'a':['b','c'],
	'b':['a','c','d'],
	'c':['a','b','d','e'],
	'd':['b','c','e','f'],
	'e':['c','d'],
	'f':['d']
}

def BFS(graph, s):
	queue = []
	queue.append(s)
	seen = set()
	seen.add(s)
	while(len(queue) > 0):
		v = queue.pop(0)
		nodes = graph[v]
		for w in nodes:
			if w not in seen:
				queue.append(w)
				seen.add(w)
		print(v)

BFS(graph, 'a')
  • 结果截图:
    BFS 广度优先算法的笔记(python、C++)

C++代码及运行结果截图

//
//  main.cpp
//  BFS
//
//  Created by Owen Zhang on 2020/7/27.
//  Copyright © 2020 OWEN. All rights reserved.
//  学习不易,如有引用,请标记来源!

#include "iostream"
#include "vector"
#include "queue"
#include "map"
#define MAX 6//定义宏为所有结点数
using namespace std;
void BFS(vector<vector<int>>map, char root){//BFS函数
    vector<char>seen;//已访问过的字符数组
    queue<char>queue;//BFS队列
    queue.push(root);
    seen.push_back(root);//加入根结点到queue和seen
    while(!queue.empty()){//若queue不为空
        char vertex = queue.front();
        queue.pop();//需要将队首结点弹出,否则将无限循环
        int w = vertex-65;//w为行数,使用ASCII码进行运算,如'A'对应第0行,'B'对应第1行……
        for(int i=0;i<map[w].size();i++){//查看邻接矩阵,i对应列数
            if(map[w][i]==1)
                if(find(seen.begin(),seen.end(),'A'+i)==seen.end()){
                //在seen中检查是否遍历过该字母,如果没有,则进行下列操作
                        queue.push('A'+i);
                        seen.push_back('A'+i);
                    };
        }
        cout<<vertex<<' ';//打印当前结点
    }
    cout<<endl;
}

int main() {
    vector<vector<int>> map(MAX);//邻接矩阵的初始化
    //为快速对vector二维数组赋值,初始化前使用了六个一维数组进行赋值
    int a[MAX]={0,1,1,0,0,0};
    int b[MAX]={1,0,1,1,0,0};
    int c[MAX]={1,1,0,1,1,0};
    int d[MAX]={0,1,1,0,1,1};
    int e[MAX]={0,0,1,1,0,0};
    int f[MAX]={0,0,0,1,0,0};
    map[0].insert(map[0].begin(), a, a+MAX);//此处使用insert方法对map的每一行进行初始化
    map[1].insert(map[1].begin(), b, b+MAX);
    map[2].insert(map[2].begin(), c, c+MAX);
    map[3].insert(map[3].begin(), d, d+MAX);
    map[4].insert(map[4].begin(), e, e+MAX);
    map[5].insert(map[5].begin(), f, f+MAX);
    for(int i=0;i<map.size();i++){//打印全部邻接矩阵,检查邻接矩阵是否正确
        for(int j=0;j<map[i].size();j++){
            cout<<map[i][j];
        }
        cout<<endl;
    }
    cout<<endl;
    BFS(map, 'A');
    return 0;
}
  • 结果截图:
    BFS 广度优先算法的笔记(python、C++)

备注

  • 初始化的方法较为粗鲁,后期看或想到更好的方法会修改,也欢迎各位读者推荐!

  • 结果可以有多种,不一定相同。得出结果后,可以根据结果按照图示走一遍,看看是否正确,则可以验证算法是否正确。

  • 学习不易,如有引用,请标记来源!

学习资源

B站up主:正月点灯笼
学习视频:[Python] BFS和DFS算法(第2讲)
链接:https://www.bilibili.com/video/BV1Ks411575U/?spm_id_from=333.788.videocard.1

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。