首页 > 代码库 > 《图论》——广度优先遍历算法(BFS)
《图论》——广度优先遍历算法(BFS)
十大算法之广度优先遍历:
本文以实例形式讲述了基于Java的图的广度优先遍历算法实现方法,详细方法例如以下:
用邻接矩阵存储图方法:
1.确定图的顶点个数和边的个数
2.输入顶点信息存储在一维数组vet中
3.初始化邻接矩阵。
4.依次输入每条边存储在邻接矩阵array中
输入边依附的两个顶点的序号i,j。
将邻接矩阵的第i行第j列的元素值置为1;
将邻接矩阵的第j行第i列的元素值置为1;
广度优先遍历实现:
1.初始化队列Q
2.訪问顶点v;ifVisit[v]=1;顶点v入队Q;
3.while(队列Q非空)
v=队列Q的队头元素出队;
w=顶点v的第一个邻接点
while(w存在)
假设w未被訪问,则訪问顶点w;visited[w]=1;顶点w入队列Q
w=顶点v的下一个邻接点
例如以下代码參考此图完毕:
实现代码例如以下:
<script src="https://code.csdn.net/snippets/818855.js" type="text/javascript"></script>
《图论》——广度优先遍历算法(BFS)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。