图的广度优先遍历(邻接表)
程序员文章站
2022-06-12 10:21:13
...
1.广度优先遍历
图的广度优先遍历类似于数的层序遍历，它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域。
以上便是广度优先遍历的一次过程（没循环）
for 循环存放顶点的数组
如果当前顶点值未被访问过
访问它并且将它对应的判断数组变为true
将它入队
while 队列不为空
出队一个元素
循环 出队元素的可以到达的顶点（就是当前顶点所有的边）将没被访问过的顶点入队
并且访它们如何将判断数组变成true
邻接表由2个部分构成，顶点是由一个数组构成，边是由链表组成，以下给出实现
其中data表示顶点的数据frist表示顶点指向的第一条边
package graph;
/**
* 邻接表的顶点
* @author 798603812
*
*/
public class Vertex<T> {
private T date;
private Edge frist;
public T getDate() {
return date;
}
public void setDate(T date) {
this.date = date;
}
public Edge getFrist() {
return frist;
}
public void setFrist(Edge frist) {
this.frist = frist;
}
}
weigth是针对网图的权值。
package graph;
/**
* 邻接表的边
* @author 798603812
*
*/
public class Edge {
private int vertexIndex;
private Edge next;
private int weigth;
public int getWeigth() {
return weigth;
}
public void setWeigth(int weigth) {
this.weigth = weigth;
}
public int getVertexIndex() {
return vertexIndex;
}
public void setVertexIndex(int vertexIndex) {
this.vertexIndex = vertexIndex;
}
public Edge getNext() {
//System.out.println(next);
if(next==null){
return null;
}
return next;
}
public void setNext(Edge next) {
this.next = next;
}
}
实现的代码
package graph;
import java.util.ArrayList;
import java.util.List;
/**
* 宽度优先遍历 2017-12-21
* @author 798603812
*
*/
public class Bfs {
private static Queue<Vertex<String>> q = new Queue<Vertex<String>>();
/**
* 宽度优先遍历
* @param arr 邻接表
*/
public static void bfs(Vertex[] arr) {
boolean[] b = new boolean[arr.length];
for (int i = 0, len = arr.length; i < len; i++) {
//如果该顶点没被访问过
if (!b[i]) {
System.out.print(arr[i].getDate()+"\t");
b[i] = true;
//将该顶点入队列
q.push(arr[i]);
//如果队列不是空
while (!q.isEmpty()) {
//v等于出队的顶点
Vertex<String>v= q.pop();
//e等于v的第一条连接的边
Edge e = v.getFrist();
//如果e不是空
while (e != null) {
//如果e所连接的顶点没被访问过
if(!b[e.getVertexIndex()]){
//该顶点入队
q.push(arr[e.getVertexIndex()]);
//输出该顶点的值
System.out.print(arr[e.getVertexIndex()].getDate()+"\t");
b[e.getVertexIndex()]=true;
}
//寻找改顶点的下一条边
e=e.getNext();
}
}
}
}
System.out.println();
}
}
/**
* 队列
*
* @author 798603812
*
*/
class Queue<T> {
List<T> queue = new ArrayList<T>();
public void push(T i) {
queue.add(i);
}
public void displayAll() {
System.out.println(queue);
}
public T returnStart() {
if (queue.isEmpty()) {
return null;
}
return queue.get(0);
}
public T returnEnd() {
if (queue.isEmpty()) {
return null;
}
return queue.get(queue.size() - 1);
}
public T pop() {
T obj = null;
if (!queue.isEmpty()) {
obj = queue.get(0);
queue.remove(0);
}
return obj;
}
public boolean isEmpty() {
if (queue.isEmpty()) {
return true;
}
return false;
}
}
测试
快速生成邻接表的方法:
package graph;
import java.util.Scanner;
/**
* 初始化邻接表
* @author 798603812
*
*/
public class Set {
/**
* 只针对无权图
* @param x 顶点的个数
* @param y 边的个数
* @return 邻接表
*/
public static Vertex[] set(int x,int y){
//参考输入数据 1 2 3 4 5
//1 3 1 2 1 4 1 5 2 5 2 4
Scanner sc=new Scanner(System.in);
Vertex[]arr=new Vertex[x];
Vertex<String> v=null;
System.out.println("请依次输入顶点的信息空格分开");
for(int i=0;i<x;i++){
String str=sc.next();
v=new Vertex<String>();
v.setDate(str);
v.setFrist(null);
arr[i]=v;
}
System.out.println("请依次输入边的信息空格分开 (根据你输入的顶点信息来)");
Edge e=null;
int str1,str2;
//System.out.println(y);
for(int j=0;j<y;j++){
str1=sc.nextInt();
str2=sc.nextInt();
//System.out.println("str1:"+str1+"str2:"+str2);
e=new Edge();
e.setVertexIndex(str2-1);
if(arr[str1-1].getFrist()==null){
arr[str1-1].setFrist(e);
}else{
Edge e2=arr[str1-1].getFrist();
while(e2.getNext()!=null){
e2=e2.getNext();
}
//System.out.println(e.getVertexIndex());
e2.setNext(e);
}
}
return arr;
}
/**
* 针对网图
* @param x 顶点的个数
* @param y 边的个数
* @return 邻接表
*/
public static Vertex[] net(int x,int y){
//参考输入数据 1 2 3 4 5
//1 3 1 2 1 4 1 5 2 5 2 4
Scanner sc=new Scanner(System.in);
Vertex[]arr=new Vertex[x];
Vertex<String> v=null;
System.out.println("请依次输入顶点的信息空格分开");
for(int i=0;i<x;i++){
String str=sc.next();
v=new Vertex<String>();
v.setDate(str);
v.setFrist(null);
arr[i]=v;
}
System.out.println("请依次输入边的信息空格分开 (根据你输入的顶点信息来) 然后输入权值");
Edge e=null;
int str1,str2,weigth;
//System.out.println(y);
for(int j=0;j<y;j++){
str1=sc.nextInt();
str2=sc.nextInt();
weigth=sc.nextInt();
//System.out.println("str1:"+str1+"str2:"+str2);
e=new Edge();
e.setWeigth(weigth);
e.setVertexIndex(str2);
if(arr[str1].getFrist()==null){
arr[str1].setFrist(e);
}else{
Edge e2=arr[str1].getFrist();
while(e2.getNext()!=null){
e2=e2.getNext();
}
e2.setNext(e);
}
}
return arr;
}
}
Test方法
package graph;
import java.util.Scanner;
public class Test {
public static void main(String[] args) {
Test t=new Test();
Vertex<Integer>[]arr=Set.set(6, 6);
// Search s=new Search();
// s.shortest(arr, 0);
// System.out.println("迪杰斯特拉算法");
// for(int i=0;i<s.dis.length;i++){
// System.out.print(s.dis[i]+"\t");
// }
System.out.println();
System.out.println("深度优先遍历");
Dfs.dfs(arr);
System.out.println("宽度优先遍历");
Bfs.bfs(arr);
// Floyd f=new Floyd();
// System.out.println("弗洛伊德算法");
// f.floyd(arr);
//Prim p=new Prim();
//System.out.println("普里姆算法");
//p.prim(arr, 1);
/**
请依次输入顶点的信息空格分开
1 2 3 4 5 6 7 8
请依次输入边的信息空格分开 (根据你输入的顶点信息来)
1 5 1 3 2 1 3 2 3 5 4 2 7 5 6 7 7 6
*
*/
}
}
输入:
请依次输入顶点的信息空格分开
1 2 3 4 5 6
请依次输入边的信息空格分开 (根据你输入的顶点信息来)
1 2 1 3 4 3 2 5 3 6 2 6
输出结果
1 2 3 5 6 4
图为