1.為什么要有圖
前面我們學了線性表和樹
線性表局限于一個直接前驅和一個直接后繼的關系
樹也只能有一個直接前驅也就是父節(jié)點
當我們需要表示多對多的關系時， 這里我們就用到了圖妄均。
2. 圖的舉例說明
圖是一種數據結構，其中結點可以具有零個或多個相鄰元素拜鹤。兩個結點之間的連接稱為邊。 結點也可以稱為頂點洼怔。
3. 圖的常用概念
頂點(vertex)
邊(edge)
路徑
無向圖
有向圖
帶權圖
圖的表示方式有兩種：二維數組表示（鄰接矩陣）署惯；鏈表表示（鄰接表）。
4. 鄰接矩陣
鄰接矩陣是表示圖形中頂點之間相鄰關系的矩陣镣隶，對于 n 個頂點的圖而言极谊，矩陣是的 row 和 col 表示的是 1....n個點。
5. 鄰接表
鄰接矩陣需要為每個頂點都分配 n 個邊的空間安岂，其實有很多邊都是不存在,會造成空間的一定損失.
鄰接表的實現只關心存在的邊轻猖，不關心不存在的邊。因此沒有空間浪費域那，鄰接表由數組+鏈表組成
6. 實現下圖結構
(1) 存儲頂點 String 使用 ArrayList
(2) 保存矩陣 int[][] edges
public class Graph {
private ArrayList<String> vertexList; //存儲頂點集合
private int[][] edges; //存儲圖對應的鄰結矩陣
private int numOfEdges; //表示邊的數目
//定義給數組boolean[], 記錄某個結點是否被訪問
private boolean[] isVisited;
//插入結點
public void insertVertex(String vertex) {
vertexList.add(vertex);
}
/**
* 添加邊
* @param v1 表示點的下標即使第幾個頂點 "A"-"B" "A"->0 "B"->1
* @param v2 第二個頂點對應的下標
* @param weight 表示
*/
public void insertEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
}
7. 圖的深度優(yōu)先遍歷
所謂圖的遍歷咙边，即是對結點的訪問。一個圖有那么多個結點次员，如何遍歷這些結點败许，需要特定策略，
一般有兩種訪問策略:
- (1)深度優(yōu)先遍歷
- (2)廣度優(yōu)先遍歷
7.1 深度優(yōu)先遍歷基本思想
-
- 深度優(yōu)先遍歷淑蔚，從初始訪問結點出發(fā)市殷，初始訪問結點可能有多個鄰接結點，深度優(yōu)先遍歷的策略就是首先訪問
第一個鄰接結點刹衫，然后再以這個被訪問的鄰接結點作為初始結點醋寝，訪問它的第一個鄰接結點搞挣， 可以這樣理解：
每次都在訪問完當前結點后首先訪問當前結點的第一個鄰接結點。
- 我們可以看到音羞，這樣的訪問策略是優(yōu)先往縱向挖掘深入囱桨，而不是對一個結點的所有鄰接結點進行橫向訪問。
- 顯然嗅绰，深度優(yōu)先搜索是一個遞歸的過程
7.2 深度優(yōu)先遍歷算法步驟
訪問初始結點 v舍肠，并標記結點 v 為已訪問。
查找結點 v 的第一個鄰接結點 w办陷。
若 w 存在貌夕，則繼續(xù)執(zhí)行 4律歼，如果 w 不存在民镜，則回到第 1 步，將從 v 的下一個結點繼續(xù)险毁。
若 w 未被訪問制圈，對 w 進行深度優(yōu)先遍歷遞歸（即把 w 當做另一個 v，然后進行步驟 123）畔况。
查找結點 v 的 w 鄰接結點的下一個鄰接結點鲸鹦，轉到步驟 3。
7.3 代碼實現
//深度優(yōu)先遍歷算法
//i 第一次就是 0
private void dfs(boolean[] isVisited, int i) {
//首先我們訪問該結點,輸出
System.out.print(getValueByIndex(i) + "->");
//將結點設置為已經訪問
isVisited[i] = true;
//查找結點i的第一個鄰接結點w
int w = getFirstNeighbor(i);
while(w != -1) {//說明有
if(!isVisited[w]) {
dfs(isVisited, w);
}
//如果w結點已經被訪問過
w = getNextNeighbor(i, w);
}
}
//對dfs 進行一個重載, 遍歷我們所有的結點跷跪，并進行 dfs
public void dfs() {
isVisited = new boolean[vertexList.size()];
//遍歷所有的結點馋嗜，進行dfs[回溯]
for(int i = 0; i < getNumOfVertex(); i++) {
if(!isVisited[i]) {
dfs(isVisited, i);
}
}
}
//返回結點的個數
public int getNumOfVertex() {
return vertexList.size();
}
8. 圖的廣度優(yōu)先遍歷
8.1 廣度優(yōu)先遍歷基本思想
- 圖的廣度優(yōu)先搜索(Broad First Search) 。
- 類似于一個分層搜索的過程吵瞻，廣度優(yōu)先遍歷需要使用一個隊列以保持訪問過的結點的順序葛菇，以便按這個順序來訪問這些結點的鄰接結點
8.2 廣度優(yōu)先遍歷算法步驟
- 訪問初始結點 v 并標記結點 v 為已訪問。
- 結點 v 入隊列
- 當隊列非空時橡羞，繼續(xù)執(zhí)行眯停，否則算法結束。
- 出隊列卿泽，取得隊頭結點 u莺债。
- 查找結點 u 的第一個鄰接結點 w。
-
- 若結點 u 的鄰接結點 w 不存在签夭，則轉到步驟 3齐邦；否則循環(huán)執(zhí)行以下三個步驟：
6.1 若結點 w 尚未被訪問措拇，則訪問結點 w 并標記為已訪問宣羊。
6.2 結點 w 入隊列
6.3 查找結點 u 的繼 w 鄰接結點后的下一個鄰接結點 w仇冯，轉到步驟 6族操。
8.3 代碼實現
//對一個結點進行廣度優(yōu)先遍歷的方法
private void bfs(boolean[] isVisited, int i) {
int u ; // 表示隊列的頭結點對應下標
int w ; // 鄰接結點w
//隊列色难，記錄結點訪問的順序
LinkedList queue = new LinkedList();
//訪問結點，輸出結點信息
System.out.print(getValueByIndex(i) + "=>");
//標記為已訪問
isVisited[i] = true;
//將結點加入隊列
queue.addLast(i);
while( !queue.isEmpty()) {
//取出隊列的頭結點下標
u = (Integer)queue.removeFirst();
//得到第一個鄰接結點的下標 w
w = getFirstNeighbor(u);
while(w != -1) {//找到
//是否訪問過
if(!isVisited[w]) {
System.out.print(getValueByIndex(w) + "=>");
//標記已經訪問
isVisited[w] = true;
//入隊
queue.addLast(w);
}
//以u為前驅點娇昙，找w后面的下一個鄰結點
w = getNextNeighbor(u, w); //體現出我們的廣度優(yōu)先
}
}
}
//遍歷所有的結點，都進行廣度優(yōu)先搜索
public void bfs() {
isVisited = new boolean[vertexList.size()];
for(int i = 0; i < getNumOfVertex(); i++) {
if(!isVisited[i]) {
bfs(isVisited, i);
}
}
}
9.圖的深度優(yōu)先 VS 廣度優(yōu)先
