深度優先搜尋(DFS: Depth-First Search)：
* 深度優先遍歷，從初始訪問點出發，初始訪問點可能有多個鄰接結點，
* 深度優先的遍歷的策略是首先訪問第一個鄰接點，
* 然後再以這個被訪問的鄰接結點作為初始訪問結點，
* 訪問它的第一個鄰接結點，
* 即每一次訪問完當前節點都會首先訪問當前節點的第一個鄰節點。類似迷宮回溯算法。
* 深度是盡可能找下一層的結點 廣度優先搜尋(Breadth-First Search)：
* 廣度是盡可能的找同一層的結點package utitled;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class GraphDemo {
public static void main(String[] args) {
// 宣告所有頂點
String[] vertexArr = {"A", "B", "C", "D", "E"};
// 創建圖
Graph graph = new Graph(vertexArr.length);
// 新增頂點
for (int i = 0; i < vertexArr.length; i++) {
graph.addVertex(vertexArr[i]);
}
// 新增邊 AB AC BC BD BE
// 無向圖 - 邊的關係是雙向的
graph.addEdge(0, 1, 1);
graph.addEdge(1, 0, 1);
graph.addEdge(0, 2, 1);
graph.addEdge(2, 0, 1);
graph.addEdge(1, 2, 1);
graph.addEdge(2, 1, 1);
graph.addEdge(1, 3, 1);
graph.addEdge(3, 1, 1);
graph.addEdge(1, 4, 1);
graph.addEdge(4, 1, 1);
System.out.println("graph.getNumOfVertex() = " + graph.getNumOfVertex());
System.out.println("graph.getNumOfEdge() = " + graph.getNumOfEdge());
// 顯示圖
graph.showGraph();
// graph.dfs();
graph.bfs();
}
}
class Graph {
/**
* 用來存放頂點(vertex)
*/
private List<String> vertexs;
/**
* 用來存放邊
*/
private int[][] edges;
/**
* 頂點的數量
*/
private int numOfVertex;
/**
* 邊的數量
*/
private int numOfEdge;
/**
* 紀錄頂點是否被訪問過
*/
private boolean[] isVisitedArr;
public Graph(int numOfVertex) {
this.vertexs = new ArrayList<>(numOfVertex);
this.numOfVertex = this.vertexs.size();
this.edges = new int[numOfVertex][numOfVertex];
this.numOfEdge = 0;
this.isVisitedArr = new boolean[numOfVertex];
}
public int getNumOfVertex() {
return numOfVertex;
}
public int getNumOfEdge() {
return numOfEdge;
}
public String getVertexValue(int index) {
return vertexs.get(index);
}
/**
* 取得當前頂點的第一個鄰居頂點索引
* @param currentInx
* @return
*/
public int getFirstNeighborIndex(int currentInx) {
for (int i = 0; i < vertexs.size(); i++) {
if (edges[currentInx][i] == 1) {
// 找到current vertex 連接的鄰居頂點
return i;
}
}
return -1;
}
/**
* 取得當前頂點的第一個鄰居頂點的隔壁的頂點
* @param currentInx
* @param firstNeighborInx
* @return
*/
public int getFirstNeighborNextInx(int currentInx, int firstNeighborInx) {
for (int i = firstNeighborInx + 1; i < vertexs.size(); i++) {
if (edges[currentInx][i] == 1) {
return i;
}
}
return -1;
}
/**
* 深度優先搜尋(DFS: Depth-First Search)：
* 深度優先遍歷，從初始訪問點出發，初始訪問點可能有多個鄰接結點，
* 深度優先的遍歷的策略是首先訪問第一個鄰接點，
* 然後再以這個被訪問的鄰接結點作為初始訪問結點，
* 訪問它的第一個鄰接結點，
* 即每一次訪問完當前節點都會首先訪問當前節點的第一個鄰節點。類似迷宮回溯算法。
* 深度是盡可能找下一層的結點
* @param isVisitedArr
* @param currentInx
*/
private void dfs(boolean[] isVisitedArr, int currentInx) {
System.out.print(getVertexValue(currentInx) + "->");
// 將當前頂點設定被訪問過
isVisitedArr[currentInx] = true;
// 取得當前頂點的第一個鄰接頂點索引w
int w = getFirstNeighborIndex(currentInx);
while(w != -1) {
// 代表頂點索引w與當前頂點有連接
if (!isVisitedArr[w]) {
// 頂點索引w沒有被訪問過，進行dfs
dfs(isVisitedArr, w);
}
// 若頂點w已被訪問過，就找第一個鄰接頂點的隔壁
w = getFirstNeighborNextInx(currentInx, w);
}
// 若當前頂點與頂點w沒有連接，離開
}
/**
* 第一次循環是以第一個鄰接點作為基準點，
* 就已經訪問完所有的與第一個結點相關聯的點，
* 完整遍歷是為了訪問與第一個結點不關聯的結點
*/
public void dfs() {
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisitedArr[i]) {
// 當前頂點沒被訪問過
dfs(isVisitedArr, i);
}
}
}
public void bfs() {
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisitedArr[i]) {
// 當前頂點沒被訪問過
bfs(isVisitedArr, i);
}
}
}
/**
* 廣度優先搜尋(Breadth-First Search)：
* 廣度是盡可能的找同一層的結點
* @param isVisitedArr
* @param currentInx
*/
private void bfs(boolean[] isVisitedArr, int currentInx) {
// 紀錄頂點訪問的順序
List<Integer> queue = new LinkedList<>();
// 輸出當前頂點索引
System.out.print(getVertexValue(currentInx) + "->");
// 當前索引標註已訪問
isVisitedArr[currentInx] = true;
// 已訪問過的頂點加入Queue
queue.add(currentInx);
while (!queue.isEmpty()) {
// 佇列不為空
// pop出佇列頭索引(先進先出)
int queueHeadInx = queue.remove(currentInx);
// 鄰接頂點索引
int w = getFirstNeighborIndex(queueHeadInx);
while (w != -1) {
// 搜尋佇列頭的第一個鄰接頂點有連接 && 未訪問過
if (!isVisitedArr[w]) {
System.out.print(getVertexValue(w) + "->");
// 鄰接頂點標註已訪問
isVisitedArr[w] = true;
// 入queue
queue.add(w);
}
w = getFirstNeighborNextInx(queueHeadInx, w);
}
}
}
/**
* 新增頂點
* @param vertex
*/
public void addVertex(String vertex) {
vertexs.add(vertex);
numOfVertex++;
}
/**
* AB AC BC BD BE
* 新增有連接關係(=1)的頂點
* 無連接為0
* @param v1 頂點1索引
* @param v2 頂點2索引
* @param weight 權值
*/
public void addEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
// edges[v2][v1] = weight;
// 邊的數量+1
numOfEdge++;
}
/**
* 顯示圖
*/
public void showGraph() {
for (int[] edge: edges) {
System.out.println("Arrays.toString(edge) = " + Arrays.toString(edge));
}
}
}如有敘述錯誤，還請不吝嗇留言指教，thanks!
