基于Java实现的图的广度优先遍历算法
作者:shichen2014 发布时间:2021-06-02 06:51:20
标签:Java,图,算法
本文以实例形式讲述了基于Java的图的广度优先遍历算法实现方法,具体方法如下:
用邻接矩阵存储图方法:
1.确定图的顶点个数和边的个数
2.输入顶点信息存储在一维数组vertex中
3.初始化邻接矩阵;
4.依次输入每条边存储在邻接矩阵arc中
输入边依附的两个顶点的序号i,j;
将邻接矩阵的第i行第j列的元素值置为1;
将邻接矩阵的第j行第i列的元素值置为1;
广度优先遍历实现:
1.初始化队列Q
2.访问顶点v;visited[v]=1;顶点v入队Q;
3.while(队列Q非空)
v=队列Q的队头元素出队;
w=顶点v的第一个邻接点
while(w存在)
如果w未被访问,则访问顶点w;visited[w]=1;顶点w入队列Q
w=顶点v的下一个邻接点
实现代码如下:
package com.teradata.lsw.sort;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class BFS {
// 存储节点信息
private Object[] vertices;
// 存储边的信息数组
private int[][] arcs;
// 边的条数
private int vexnum;
// 记录第i个节点是否被访问过
private boolean[] visited;
//构建一个临时链表存已经遍历过的节点
private List<Object> temp = new ArrayList<Object>();
/**
* @param args
*
* @author TD_LSW
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BFS g = new BFS(8);
Character[] vertices = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
g.addVertex(vertices);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);
g.addEdge(2, 6);
g.addEdge(2, 7);
System.out.println("图的广度优先遍历:");
g.bfs();
}
// 广度优先遍历实现
private void bfs() {
// TODO Auto-generated method stub
for (int i = 0; i < vexnum; i++) {
visited[i] = false;
}
Queue<Integer> q = new LinkedList<Integer>();
for (int i = 0; i < vexnum; i++) {
if (!visited[i]) {
visited[i] = true;
visit(i);
q.add(i);
while (!q.isEmpty()) {
int j = (Integer) q.remove().intValue();
//判断如果全部遍历完了就不需要循环了
if (temp.size() == vexnum) {
q.removeAll(q);
return;
}
for (int k = this.firstAdjVex(j); k >= 0; k = this
.nextAdjVex(j, k)) {
if (!visited[k]) {
q.add(k);
visited[k] = true;
visit(k);
}
}
}
}
}
}
// 查找下一个节点
public int firstAdjVex(int i) {
for (int j = 0; j < vexnum; j++) {
if (arcs[i][j] > 0)
return j;
}
return -1;
}
public int nextAdjVex(int i, int k) {
for (int j = k + 1; j < vexnum; j++) {
if (arcs[i][j] > 0)
return j;
}
return -1;
}
// 初始化图的边
private void addEdge(int i, int j) {
// TODO Auto-generated method stub
if (i == j)
return;
arcs[i][j] = 1;
arcs[j][i] = 1;
}
// 初始化图的节点
private void addVertex(Object[] object) {
// TODO Auto-generated method stub
this.vertices = object;
}
// 图的初始化
public BFS(int n) {
// TODO Auto-generated constructor stub
vexnum = n;
vertices = new Object[n];
arcs = new int[n][n];
visited = new boolean[n];
for (int i = 0; i < vexnum; i++) {
for (int j = 0; j < vexnum; j++) {
arcs[i][j] = 0;
}
}
}
private void visit(int i) {
// TODO Auto-generated method stub
temp.add(vertices[i]);
System.out.print(vertices[i] + " ");
}
}
0
投稿
猜你喜欢
- 在平时的开发过程中,会有很多场景需要实时监听文件的变化,如下:1、通过实时监控 mysql 的 binlog 日志实现数据同步2、修改配置文
- Map接口存储特点以键(key)值(value)对的形式存储键无序、无下标、元素不可重复值无序、无下标、元素可以重复常用实现类HashMap
- 一、简单介绍翻看Spring的源码时,发现@Bean注解的源码上标注了Since: 3.0,也就是说,@Bean注解是Spring从3.0版
- 需要用到 java 写一个 ftp 的工具,因为只有一点点 java 基础,但是由于好几年不用,几乎算是不会了,只好一点点来搞,还好能捡起来
- ThreadGroup的作用及方法ThreadGroup线程组,java对这个类的描述呢就是“线程组表示一组线程。此外,线程组还可以包括其他
- 多线程可以说是面试官最喜欢拿来问的题目之一了,可谓是老生之常谈,不管你是新手还是老司机,我相信你一定会在面试过程中遇到过有关多线程的一些问题
- 环境:VS2019+Qt5.121. CLR库安装 &nb
- 前言本文准确来讲是探讨如何用 Jackson 来序列化 Apache avro 对象,因为简单用 Jackson 来序列化 Apache a
- 测试spring cloud 使用consul注册服务的时候,出现critical,如下:怎么解决这个问题,现在只能看到health che
- 问题项目是springcloud项目,在maven install某一个项目时报错:程序包com.example.commons.appli
- springboot上传文件大小的配置我这里记录两种,一种是设置在配置文件里只有两行代码,一种是加个Bean首先第一种:applicatio
- WebFilter.javapackage com.hongyuan.route;import java.io.File;import ja
- 这几天自己研究了关于地手机上面开发安卓地图的问题,发现百度官方示例demo讲解百度持续定位方面还是讲解的有些不清楚,本人研究了几次之后将其弄
- MyBatis-Plus不使用数据库默认值的问题有时候我们在设计数据表时希望某些字段使用默认值,比如create_time、和update_
- 需求:有些时候,我们需要连接多个数据库,但是,在方法调用前并不知道到底是调用哪个。即同时保持多个数据库的连接,在方法中根据传入的参数来确定。
- Feign调用中的两种Header传参方式在Spring Cloud Netflix栈中,各个微服务都是以HTTP接口的形式暴露自身服务的,
- Spring Cache设置缓存条件原理从Spring3.1开始,Spring框架提供了对Cache的支持,提供了一个对缓存使用的抽象,通过
- 先扯再说最近一直在研究某个国产开源的MySQL数据库中间件,拉下其最新版的代码到eclipse后,启动起来,然后做各种测试和代码追踪;用完想
- 一、概述在微服务架构中,我们将系统拆分成了很多服务单元,各单元的应用间通过服务注册与订阅的方式互相依赖。由于每个单元都在不同的进程中运行,依
- 一、说明Boost.MPI 提供了 MPI 标准(消息传递接口)的接口。该标准简化了并发执行任务的程序的开发。您可以使用线程或通过共享内存或