《图论》——广度优先遍历算法(BFS)-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

《图论》——广度优先遍历算法(BFS)

简介: 十大算法之广度优先遍历: 本文以实例形式讲述了基于Java的图的广度优先遍历算法实现方法,具体方法如下: 用邻接矩阵存储图方法: 1.确定图的顶点个数和边的个数 2.输入顶点信息存储在一维数组vet中 3.

十大算法之广度优先遍历:


本文以实例形式讲述了基于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的下一个邻接点

如下代码参考此图完成:


实现代码如下:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BFS {
 
	private Object[] vet;     //定义vet数组用来存放顶点信息
	private int[][] array;    //定义邻接矩阵存放图的顶点信息
	private int vexnum;       //存储边的条数
	private boolean[] ifVisit;//存放结点是否被访问过
	private List

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章