圖是表示一種多對多關系的資料結構
它包括無向圖，有向圖，帶權圖
無向圖：就是頂點之間的連線（邊）沒有方向箭頭
有向圖：就是頂點之間的連線（邊）有方向箭頭
帶權圖：就是頂點之間的連線（邊）表明了大小如上海到北京的距離，北京到天津的距離類似的導航地圖就是帶權圖
下圖就是一個無向圖：
字母所表示的是頂點，頂點間的連線叫做邊
按照A,B,C,D,E,F,G的順序添加節點，并添加對應的邊構成下圖
深度優先周遊：
從初始通路結點出發，我們知道初始通路結點可能有多個鄰接結點，深度優先周遊的政策就是首先通路第一個鄰接結點，然後再以這個被通路的鄰接結點作為初始結點，通路它的第一個鄰接結點。總結起來可以這樣說：每次都在通路完目前結點後首先通路目前結點的第一個鄰接結點。
具體算法表述如下：
1.通路初始結點v，并标記結點v為已通路。
2.查找結點v的第一個鄰接結點w。
3.若w存在，則繼續執行4，否則算法結束。
4.若w未被通路，對w進行深度優先周遊遞歸（即把w當做另一個v，然後進行步驟123）。
5.查找結點v的w鄰接結點的下一個鄰接結點，轉到步驟3。
按照上圖便利的順序應該是A->B->C->G->D->E->F->
廣度優先周遊：
類似于一個分層搜尋的過程，廣度優先周遊需要使用一個隊列以保持通路過的結點的順序，以便按這個順序來通路這些結點的鄰接結點。
具體算法表述如下：
1.通路初始結點v并标記結點v為已通路。
2.結點v入隊列
3.當隊列非空時，繼續執行，否則算法結束。
4.出隊列，取得隊頭結點u。
5.查找結點u的第一個鄰接結點w。
6.若結點u的鄰接結點w不存在，則轉到步驟3；否則循環執行以下三個步驟：
1). 若結點w尚未被通路，則通路結點w并标記為已通路。
2). 結點w入隊列
3). 查找結點u的繼w鄰接結點後的下一個鄰接結點w，轉到步驟6。
按照上圖便利的順序應該是A->B->C->D->E->G->F->
java代碼實作:
package com.yg.graph;/*
@date 2020/3/15 9:58
*/
import java.time.chrono.IsoChronology;
import java.util.*;
public class Graph {
//存放頂點
private List<String> vertexList;
//表示頂點之間是否相連 0不連通，1連通
private int[][] edges;
//表示邊的數量
private int numOfEdges = 0;
//表示周遊時是否已經通路過
private boolean[] isVisited;
public static void main(String[] args) {
//建構圖
//添加頂點
String[] vertexs = {"A", "B", "C", "D", "E","F","G"};
Graph graph = new Graph(vertexs.length);
for (String vertex : vertexs) {
graph.addVertex(vertex);
}
//添加邊
graph.addEdge(0, 1, 1);
graph.addEdge(0, 2, 1);
graph.addEdge(1, 2, 1);
graph.addEdge(1, 3, 1);
graph.addEdge(1, 4, 1);
graph.addEdge(3, 4, 1);
graph.addEdge(4, 5, 1);
graph.addEdge(2, 6, 1);
graph.showGraph();
//深度優先周遊
// graph.dfs(0);
//廣度優先周遊
graph.bfs(0);
}
public Graph(int n) {
vertexList = new ArrayList<>(n);
edges = new int[n][n];
numOfEdges = 0;
isVisited = new boolean[n];
}
//深度優先周遊,index目前周遊的頂點
private void dfs(int index) {
//列印目前頂點
System.out.print(vertexList.get(index)+"->");
isVisited[index]=true;
//得到第一個鄰接頂點
int w=getFristNeighbor(index);
//鄰接頂點存在
while (w != -1) {
if (!isVisited[w]) {
dfs(w);
}
w=getNextNeighbor(index,w);
}
}
//重載dfs
public void dfs() {
//這是為了預防有向圖中部分節點到不了的情況
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]) {
dfs(i);
}
}
}
//廣度優先周遊
private void bfs(int index) {
//記錄節點通路順序
Queue queue=new LinkedList();
System.out.print(vertexList.get(index)+"->");
isVisited[index]=true;
queue.add(index);
while (!queue.isEmpty()) {
//隊列頭節點下表
int vertexIndex= (int) queue.poll();
//得到第一個鄰接頂點的下标
int fristNeighbor = getFristNeighbor(vertexIndex);
//是否還有鄰近頂點
while (fristNeighbor != -1) {
//是否通路過
if (!isVisited[fristNeighbor]) {
System.out.print(vertexList.get(fristNeighbor)+"->");
isVisited[fristNeighbor]=true;
//入隊
queue.add(fristNeighbor);
}
fristNeighbor=getNextNeighbor(vertexIndex,fristNeighbor);
}
}
}
//重載bfs
public void bfs() {
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]) {
bfs(i);
}
}
}
//得到目前頂點的第一個鄰接頂點,index目前頂點的下标
public int getFristNeighbor(int index) {
for (int i = 0; i < vertexList.size(); i++) {
if (edges[index][i] > 0) {
return i;
}
}
return -1;
}
//得到目前頂點鄰接頂點的下一個頂點
public int getNextNeighbor(int index,int neighborIndex) {
for (int i =neighborIndex+1; i <vertexList.size() ; i++) {
if (edges[index][i]>0) {
return i;
}
}
return -1;
}
//添加頂點
public void addVertex(String vertex) {
vertexList.add(vertex);
}
//添加邊
/*
* @param val1 頂點的下标，第幾個添加的頂點，小标從0開始
* @param val2
* @param weight 權重，為1表明有邊，0表示沒邊
* @return : void
* @date : 2020/3/15 10:05
*/
public void addEdge(int val1, int val2, int weight) {
edges[val1][val2] = weight;
edges[val2][val1] = weight;
numOfEdges++;
}
//得到頂點數量
public int getNumOfVertex() {
return vertexList.size();
}
//得到邊的數量
public int getNumOfEdges() {
return numOfEdges;
}
//列印圖
public void showGraph() {
for (int[] vertex : edges) {
System.out.println(Arrays.toString(vertex));
}
}
}