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;
}
}
這裡的vertexIndex代表這個邊連接配接的第一個頂點下标，next代表下一個目前頂點的下一條邊
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
圖為