故事凌 今天

基本知識點

圖可說是所有數據結構里面知識點最豐富的一個, 自己笨的知識點如下:

• 階(oRDER), 度: 出度(out-Degree), 入度(in-Degree)
• 樹(Tree), 森林(Forest), 環(Loop)
• 有向圖(Directed Graph), 無向圖(Undirected Graph), 完全有向圖, 完全無向圖
• 連通圖(Connected Graph), 連通分量(Connnected Component)
• 存儲和表達式: 鄰接矩陣(Adjacency Matrix), 鄰接鏈表(Adjacency List)

圍繞圖的算法也是五花八門

• 圖的遍歷: 深度優先, 廣度優先
• 環的檢測: 有向圖, 無向圖
• 拓撲排序
• 最短路徑算法: Dijkstra, Bellman-Ford, Floyd Warshall
• 連通性相關算法: Kosaraju, Tarjan, 求解孤島的數量, 判斷是否為樹
• 圖的著色, 旅行商問題等

以上的知識點知識圖輪里的冰山一角, 對于算法面試而言, 完全不需要對每個知識點都一一掌握, 而應該有的放矢的準備

必會的知識點

以下的知識點必須充分掌握并反復練習

• 圖的存儲和表達式: 鄰接矩陣(Adjacency Matrix), 鄰接鏈表(Adjacency List)
• 圖的遍歷: 深度優先, 廣度優先
• 二部圖的檢測(Bipartite), 數的檢測, 環的檢測, 有向圖, 無向圖
• 拓撲排序
• 聯合-查找算法(Union-Find)
• 最短路徑Dijkstra, BellMan-Ford

其中, 環的檢測, 二部圖的檢測, 樹的檢測以及拓撲都是基于圖的遍歷, 尤其是深度優先方式的遍歷, 而遍歷可以在鄰接矩陣或者鄰接鏈表上進行, 所以掌握好圖的遍歷是重中之重, 因為它是所有其他圖論算法的基礎

至于對端路徑算法, 能區分它們的不同特點, 知道在什么情況下用哪種算法就很好了, 對于有充足時間準備的面試者, 能熟練掌握他們的寫法當然是很好的

我們來來看看數據結構中的圖到底是什么

1. 圖的定義

圖是由一些點(vertex)和這些點之間的連線(edge)所組成的, 其中, 點通常稱為頂點(vertex), 而點到點之間的連線通常稱之為邊或者弧(edge), 通常記為G = (V,E)

2. 圖的分類

圖通常分為有向圖和無向圖, 而其表示方式分為鄰接矩陣和鄰接鏈表, 具體表示如下圖.

對于無向圖，其所有的邊都不區分方向。G=(V,E)。其中，

1. V={1,2,3,4,5}。V表示有”1,2,3,4,5”幾個頂點組成的集合。

2. E={(1,2),(1,5),(2,1),(2,5),(2,4),(2,3),(3,2),(3,4),(4,3),(4,2),(4,5),(5,1),(5,2),(5,4)}。E就是表示所有邊組成的集合，如(1,2)表示由頂點1到頂點2連接成的邊。

對于有向圖，其所有的邊都是有方向的。G=(V,E)。其中，

1. V={1,2,3,4,5}。V表示有”1,2,3,4,5”幾個頂點組成的集合。
2. E={<1,2>,<2,5><5,4>,<4,2><3,5>,<3,6>,<6,6>}。E就是表示所有邊組成的集合，如<1,2>表示由頂點1到頂點2連接成的邊。注意有向圖邊和無向圖邊表示方法的不同，有向圖的邊是矢量，而無向圖只是普通的括號。

針對鄰接矩陣和鄰接鏈表兩種不同的表示方式，有如下優缺點：

1. 鄰接矩陣由于沒有相連的邊也占據空間，相對于鄰接鏈表，存在空間浪費的問題；

2. 但是在查找的時候，鄰接鏈表會比較耗時，對于鄰接矩陣來說，它的查找復雜度就是O(1)。

用鄰接表表示圖的代碼

#define MAX 100typedef?struct?ENode???//鄰接表中表對應的鏈表的頂點{? ?int?ivex; ? ? ? ? ?//該邊所指向的頂點的位置? ?int?weight; ? ? ??//該邊的權值? ?struct?ENode?*next_edge; ??//指向下一條邊的指針}ENode,*PENode;typedef?struct?VNode???//鄰接表中表的頂點{? ?char?data; ? ? ??//頂點的數據? ?struct?VNode?*first_edge; ?//指向第一條依附該頂點的邊}VNode;typedef?struct?LGraph??//鄰接表{? ?int?vexnum; ? ?//圖的頂點數? ?int?edgenum; ??//圖的邊數? ?VNode?vexs[MAX];}LGraph;

3. 度, 權, 連通圖等概念

對于無向圖來說，它的頂點的度就是指關聯于該頂點的邊的數目；而對于有向圖來說，分為入度和出度，所謂入度就是進入該頂點邊的數目，出度就是離開這個頂點邊的數目，有向圖的度就是入度加出度。

圖還被分為有權圖和無權圖，所謂有權圖就是每條邊都具有一定的權重，通常就是邊上的那個數字；而無權圖就是每條邊沒有權重，也可以理解為權重為。如下圖所示即為有權圖，(A,B)的權就是13。

如果一個無向圖中每個頂點到所有其他頂點都是可達的，則稱該圖是連通的；如果一個有向圖中任意兩個頂點互相可達，則該有向圖是強連通的。

如圖(b)中有3個連通分量：{1,2,5},{3,6},{4}。若一個無向圖只有一個連通分量，則該無向圖連通。

而圖(a)中有3個強連通分量：{1,2,4,5}，{3}，{6}。{1,2,4,5}中所有頂點對互相可達。而頂點2與6不能相互可達，所以不能構成一個強連通分量。

4. 深度優先搜索(Depth First Search DFS)

圖的深度優先算法有點類似于樹的前序遍歷，首先圖中的頂點均未被訪問，確定某一頂點，從該頂點出發，依次訪問未被訪問的鄰接點，直到某個鄰接點沒有未被訪問鄰接點時，則回溯父節點(此處我們將先被訪問的節點當做后被訪問節點的父節點，例如對于節點A、B，訪問順序是A ->B，則稱A為B的父節點)，找到父節點未被訪問的子節點；如此類推，直到所有的頂點都被訪問到。

注意，深度優先的存儲方式一般是以棧的方式存儲。

1. 無向圖的深度優先搜索

2. 有向圖的深度優先搜索

3. 深度優先搜索代碼

static?void?DFS(LGraph?G,?int?i,int?*visited){? ?Enode?*node;E? ?printf(“%c”,G.vexs[i].data);? ?node?=?G.vexs[i].first_edge;? ?while(node?!=?NULL)? {? ? ? ?if(!visited[node->ivex])? ? ? ? ? ?DFS(G,?node->ivex,?visited); ?//遞歸調用DFS? ? ? ?node?=?node->next_edge;? }}

5. 廣度優先搜索

從圖中的某個頂點出發，訪問它所有的未被訪問鄰接點，然后分別從這些鄰接點出發訪問它的鄰接點。說白了就是一層一層的訪問，“淺嘗輒止”！

注意，廣度優先搜索的存儲方式一般是以隊列的方式存儲。

1. 無向圖的廣度優先搜索

2. 有向圖的廣度優先搜索

3. 廣度優先所有代碼

void?BFS(LGraph?G){? ?int?head?=?0;? ?int?rear?=?0;? ?int?queue[MAX]; ??//輔助隊列? ?int?visited[MAX]; ??//頂點訪問標記? ?eNode?*node;? ?for(int?i?=?0;?i?ivex;? ? ? ? ? ? ? ?if(!visited[k])? ? ? ? ? ? ? {? ? ? ? ? ? ? ? ? ?visited[k]?=?1;? ? ? ? ? ? ? ? ? ?printf(“%c”,G.vesx[k].data);? ? ? ? ? ? ? ? ? ?queue[rear++]?=?k;? ? ? ? ? ? ? }? ? ? ? ? ? ? ?node?=?node->next_edge;? ? ? ? ? }? ? ? }? }? ?printf(“”);}

6.拓撲排序

拓撲排序(Topological Order)是指講一個有向無環圖(Directed Acyclic Graph,DAG)進行排序而得到一個有序的線性序列。

舉個例子，例如我們早上起床的穿衣順序，如下圖所示。穿衣的順序也是有個優先級的，有些衣服就必須優先穿上，例如領帶依賴于襯衣，所以領帶最終排在襯衣之后；對圖a中的元素進行合理的排序，就得到了圖b的次序圖。注意，該次序圖不是唯一的。

int?topological_sort(LGraph?G){? ?int?num?=?G.vexnum;? ?ENode?*node;? ?int?head?=?0; ? ??//輔助隊列的頭? ?int?rear?=?0; ? ??// 輔助隊列的尾? ?int?*ins?=?(int?*)malloc(num?*?sizeof(int)); ? ? ??//入度數組? ?char?*tops?=?(char?*)malloc(num?*?sizeof(char)); ?//拓撲排序結果數組，記錄每個節點排序后的序號? ?int?*queue?=?(int?*)malloc(num?*?sizeof(int)); ? ??//輔助隊列? ?assert(ins?!=?NULL?&&?tops?!=?NULL?&&?queue?!=?NULL)? ?memset(ins,?0,?num?*?sizeof(int));? ?memset(tops,?0,?num?*?sizeof(char));? ?memset(queue,?0,?num?*?sizeof(int));? ?for(int?i?=?0;?i?ivex]++;? ? ? ? ? ?node?=?node->next_edge;? ? ? }? }? ?for(int?i?=?0;?i?ivex]--; ? ?//將節點node關聯的節點的入度減1? ? ? ? ? ?if(ins[node->ivex]?==?0) ??//若節點的入度為0，則將其添加到隊列中? ? ? ? ? ? ? ?queue[rear++]?=?node->ivex;? ? ? ? ? ?node?=?node->next_edge;? ? ? }? }? ?if(index?!=?G.vexnum)? {? ? ? ?printf(“Graph?has?a?cycle!”);? ? ? ?free(queue);? ? ? ?free(ins);? ? ? ?free(tops);? ? ? ?return?1; ?//1表示失敗，該有向圖是有環的? }? ?printf(“==?TopSort:?”); ??//打印拓撲排序結果? ?for(int?i?=?0;?i?

7. 最小生成樹

所謂最小生成樹就是將圖中的頂點全部連接起來，此時這個邊的權重最小，并且連接起來的是一個無環的樹。很容易知道，若此時的頂點是n，則邊的數量為n-1。所以在一個圖中找最小生成樹就是找最小權值的邊，讓這些邊連成一棵樹。常用的算法有Prim算法和Kruskal算法。

7. 1Prim算法

該算法就是每次迭代選擇權值最小的邊對應的點，加入到最小生成樹中。具體實現如下所示。

第一步：選取頂點A，此時U={A}，V-U={B,C,D,E,F,G}。

第二步：選取與A點連接的權值最小的邊，此時就會選擇到B，U={A,B}，V-U={C,D,E,F,G}。

以上面的步驟類推，得到如上圖所示的結果，此時U={A,B,C,D,E,F}，V-U={G}。注意到C是此次加入的點，而G沒有加入，此時G點的邊應該如何選擇？

最終，得到如圖所示的最小生成樹，此時U={A,B,C,D,E,F,G}，V-U={}。

#define INF (~(0x1<<31)) ?//最大值(即0X7FFFFFFF)//返回ch在鄰接表中的位置static?int?get_position(LGraph?G,?char?ch){? ?for(int?i?=?0;?i?的權值；若start到end不連通，則返回無窮大? ?int?getWeight(LGraph?G,?int?start,?int?end)? {? ? ? ?ENode?*node;? ? ? ?if(start?==?end)? ? ? ? ? ?return?0;? ? ? ?node?=?G.vexs[start].first_edge;? ? ? ?while(node?!=?NULL)? ? ? {? ? ? ? ? ?if(end?==?node->ivex)? ? ? ? ? ? ? ?return?node->weight;? ? ? ?node?=?node->next_edge;? ? ? }? ? ? ?return?INF;? }? ?void?Prim(LGraph?G,int?start) ?//從圖中的第start個元素開始，生成最小樹? {? ? ? ?int?index?=?0; ? ?//prim最小樹的索引，即prims數組的索引? ? ? ?char?prims[MAX]; ?//prim最小樹的結果數組? ? ? ?int?wights[MAX]; ??//頂點間邊的權重? ? ? ?//prim最小生成樹中第一個數，即圖中的第start個數? ? ? ?prims[index++]?=?G.vexs[start].data;? ? ? ?for(int?i?=?0;?i?

7.2 Kruskal算法

該算法的核心就是對權值進行排序，然后從最小的權值開始，不斷增大權值，如何該權值的所在邊的兩個頂點沒有存在的路徑連在一起，則加入這條邊，否則，則舍棄這條邊，知道所有的點都在這顆樹中。

如下所示的一個圖，我們從中找出最小生成樹。

對于左邊所示的圖，對各個邊的權值排序之后，我們最先找到權值最小的邊，即AD。然后我們發現還有一個CE，于是CE也會被標記起來。

對于左邊所示的圖，對各個邊的權值排序之后，我們最先找到權值最小的邊，即AD。然后我們發現還有一個CE，于是CE也會被標記起來。

typedef?struct?edata??//邊的結構體{? ?char?start; ?//邊的起點? ?char?end; ??//邊的終點? ?int?weight; ?//邊的權重}EData;EData?*get_edges(LGraph?G){? ?int?index?=?0;? ?ENode?*node;? ?EData?*edges;? ?edges?=?(EData?*)malloc(G.edgnum?*?sizeof(EData));? ?for(int?i?=?0;?i?ivex?>?i)? ? ? ? ? {? ? ? ? ? ? ? ?edges[index].start?=?G.vexs[i].data;? ? ? ? ? ? ? ?edges[index].end?=?G.vexs[node->ivex].data;? ? ? ? ? ? ? ?edges[index].weight?=?node->weight;? ? ? ? ? ? ? ?index++;? ? ? ? ? }? ? ? ? ? ?node?=?node->next_edge;? ? ? }? }? ?return?edges;}void?Kruskal(LGraph?G){? ?int?index?=?0; ? ??//rets數組的索引? ?int?vends[MAX]?=?{0}; ? ?//用于保存“已有最小生成樹”中每個頂點在該最小樹中的終點? ?EData?rets[MAX]; ? ?//結果數組，保存kruskal最小生成樹的邊? ?EData?*edges; ? ??//圖對應的所有邊? ?edges?=?get_edges(G); ??//獲取圖中所有的邊? ?Sorted_edges(edges,?G.edgenum); ??//對邊按照權值進行排序? ?for(int?i?=?0;?i?

例題分析

785. 判斷二分圖

給定一個無向圖graph，當這個圖為二分圖時返回true。

如果我們能將一個圖的節點集合分割成兩個獨立的子集A和B，并使圖中的每一條邊的兩個節點一個來自A集合，一個來自B集合，我們就將這個圖稱為二分圖。

graph將會以鄰接表方式給出，graph[i]表示圖中與節點i相連的所有節點。每個節點都是一個在0到graph.length-1之間的整數。這圖中沒有自環和平行邊：graph[i] 中不存在i，并且graph[i]中沒有重復的值。

示例 1:輸入: [[1,3], [0,2], [1,3], [0,2]]輸出: true解釋:無向圖如下:0----1| ? || ? |3----2我們可以將節點分成兩組: {0, 2} 和 {1, 3}。

示例 2:輸入: [[1,2,3], [0,2], [0,1,3], [0,2]]輸出: false解釋:無向圖如下:0----1|  ||  |3----2我們不能將節點分割成兩個獨立的子集。

好了, 自己研究了半天, 題都沒有研究明白,我決定放棄了, 要是哪個大佬知道, 快來教教我吧, 我們今天把樹是個什么東西就好了!

graph 的長度范圍為 [1, 100]。graph[i] 中的元素的范圍為 [0, graph.length - 1]。graph[i] 不會包含 i 或者有重復的值。圖是無向的: 如果j 在 graph[i]里邊, 那么 i 也會在 graph[j]里邊。