一、圖引入
相信很多同學都聽說過六度空間理論(SixDegress of Separation):只要通過6個人的關系網,你就能夠認識全世界所有的人。這個理論和我們接下來要講的圖非常相似。
從上圖中,我們可以看出,如果你認識6個人,是很有可能認識其他所有人的。
但是,對于全球的30億的互聯網人來說,你真的可以全部認識嗎?大多數同學此刻一定是定神一想,這還用問?你是傻子嗎?這一定不可能呀。但是對于這個問題,我們可以用我們未來學習的圖的知識解決!
除了上述問題,對于下圖,我再來提出兩個問題:
- 從陳家莊到張家村,怎么走最快呢?
- 怎么修公路使得村村通的花費最少呢?
有些同學說了,這還不簡單,讓我用我的火眼金睛數一數。但是對于下述這張圖呢?
算了,我還是街邊喊666(溜)吧!!!
二、什么是圖(Graph)
對于上述提出的幾個問題,只要你耐下性子和我修習“圖法”,相信不久之后,你就不是路邊那個只會喊“666”的同志,而是揮手說“同志們好”。那么到底什么是圖呢?記住nick心法:圖就是下面我講的這個小東西。廢話~,還不如看下圖——我(靈魂畫師)手繪圖:
以前我們學習的鏈表表示的是一對一的關系;學的樹表示一對多的關系;而我們此次的主角,冠勇三軍的圖卻是大有來頭,從上圖可以看出,圖表示的是多對多的關系,通常,它包含如下“小弟”:
- 一組頂點:通常用V(Vertex)表示頂點集合
- 一組邊:通常用E(Edge)表示邊的集合
- 邊是頂點對:即 (v,w)∈E
- (v,w)∈E,其中v,w∈V
- v,w∈V
- 無向邊(v,w)
- (v,w)表示從v指向w的邊,無箭頭,如下圖所示:
- 有向邊<v,w>
- <v,w>也表示從v指向w的邊(單行線),但是它有個該死的箭頭,如下圖所示:
- 牢記:圖的邊不考慮重邊和自回路,記不住現場扇自己兩巴掌,沒人看的見,如下圖所示是錯誤的:
三、抽象數據類型定義
我也知道枯燥,但是你逼著自己讀一遍都做不到,大江大河等著你逛?
- 類型名稱:圖(Graph)
- 數據對象集:G(V, E),由一個非空的有限頂點集合V和一個有限邊集合E組成。
- 操作集:對于任意圖G∈Graph
- G∈Graph,以及v∈V,e∈E
- v∈V,e∈E
- Graph Create():建立并返回空圖;
- Graph InsertVertex(Graph G, Vertex v):將v插入G
- Graph InsertEdge(Graph G, Edge e):將e插入G;
- Void DFS(Graph G, Vertex v):從頂點v出發深度優先(別好奇,繼續往下看)遍歷圖G;
- Void BFS(Graph G, Vertex v):從頂點v出發寬度優先遍歷圖G;
- Void ShortestPath(Graph G, Vertex v, int Dist[]):計算圖G中頂點v到任意其他頂點的最短距離;
- Void MST(Graph G):計算圖G的最小生成樹;
- ……,以后都會講到的,別急,現在不想弄死你,否則你醉生夢死(禿頭)走不動了怎么辦???
四、常見術語
你隨便找一本圖論的書,圖的常見術語隨隨便便幾十頁,為了再次不讓你醉生夢死,我就例舉出幾個,你看著記下就好了:
對,你沒有看錯,就這幾個,還有很多!
五、怎么在程序中表示一個圖
理論這東西怎么能符合我大nick的智商,那就來一點實踐的吧!
逼逼叨叨一大堆,你倒是講講我們怎么在程序中表示一個圖呀?
既然你選擇了死亡,那我就告訴你吧。在程序中,我們一般有以下兩種方式表示圖(這并不意味著只有兩個,多著呢!),分別為鄰接矩陣和鄰接表,下面重點戲來了,你個戲精,不是你想要來點實踐的嗎?
六、鄰接矩陣
別聽到矩陣就慌了陣腳,有我這個冠勇三軍的大nick在,怕啥怕,來吧!
你可以把鄰接矩陣看成一個正方形,也可以看成一個二維平面直角坐標軸,也可以混在一起看。我們先來看看它長啥挫樣:
不可否認的是,這張圖是有點難理解的,但是你要重視接下來我講的這兩句話:
- 鄰接矩陣G[N][N]——N個頂點從0到N-1編號
對于上圖的鄰接矩陣,其實存在一個很大的bug,上圖的鄰接矩陣是沿紅線對稱的,也就是說,我們是否可以做到如下圖所示,只要紅色區域的部分呢?這樣就可以節省一半空間了。
6.1 鄰接矩陣的優點
上面逼逼了一大堆鄰接矩陣的理論,實在讓人痛苦,那么使用鄰接矩陣有啥好處呢?好處大大的有,有以下四點好處:
- 直觀、簡單、好理解,這難道不是優點嗎?
- 方便檢查任意一對頂間是否存在邊
- 方便找任一頂點的所有鄰接點(有邊直接相連的頂點)
- 方便計算任一頂點的度(從該點觸發的邊數為出度,指向該點的邊數為入度)
- 無向圖:對應行(或列)非0元素的個數(出度就是入度呀!!!)
- 有向圖:對應行非0元素的個數是出度;對應列非0元素的個數是入度
6.2 鄰接矩陣的缺點
作為一個一個冠勇三軍的大nick,不能總鼓勵,也得給點打壓!
那么鄰接矩陣有什么缺點呢?缺點其實不多,就以下兩點:
- 浪費空間——存稀疏圖(點很多而便很少,其實就是0很多的意思,有大量無效元素)
- 對稠密圖(特別是完全圖 )
6.3 鄰接矩陣的代碼表示
直接上代碼吧!c和Python版本我都給你準備好了,但是我推薦你先看完理論再去研究代碼。
6.3.1 c表示
/* C語言實現 */ /* 圖的鄰接矩陣表示法 */ #define MaxVertexNum 100 /* 最大頂點數設為100 */ #define INFINITY 65535 /* ∞設為雙字節無符號整數的最大值65535*/ typedef int Vertex; /* 用頂點下標表示頂點,為整型 */ typedef int WeightType; /* 邊的權值設為整型 */ typedef char DataType; /* 頂點存儲的數據類型設為字符型 */ /* 邊的定義 */ typedef struct ENode *PtrToENode; struct ENode{ Vertex V1, V2; /* 有向邊<V1, V2> */ WeightType Weight; /* 權重 */ }; typedef PtrToENode Edge; /* 圖結點的定義 */ typedef struct GNode *PtrToGNode; struct GNode{ int Nv; /* 頂點數 */ int Ne; /* 邊數 */ WeightType G[MaxVertexNum][MaxVertexNum]; /* 鄰接矩陣 */ DataType Data[MaxVertexNum]; /* 存頂點的數據 */ /* 注意:很多情況下,頂點無數據,此時Data[]可以不用出現 */ }; typedef PtrToGNode MGraph; /* 以鄰接矩陣存儲的圖類型 */ MGraph CreateGraph( int VertexNum ) { /* 初始化一個有VertexNum個頂點但沒有邊的圖 */ Vertex V, W; MGraph Graph; Graph = (MGraph)malloc(sizeof(struct GNode)); /* 建立圖 */ Graph->Nv = VertexNum; Graph->Ne = 0; /* 初始化鄰接矩陣 */ /* 注意:這里默認頂點編號從0開始,到(Graph->Nv - 1) */ for (V=0; V<Graph->Nv; V++) for (W=0; W<Graph->Nv; W++) Graph->G[V][W] = INFINITY; return Graph; } void InsertEdge( MGraph Graph, Edge E ) { /* 插入邊 <V1, V2> */ Graph->G[E->V1][E->V2] = E->Weight; /* 若是無向圖,還要插入邊<V2, V1> */ Graph->G[E->V2][E->V1] = E->Weight; } MGraph BuildGraph() { MGraph Graph; Edge E; Vertex V; int Nv, i; scanf("%d", &Nv); /* 讀入頂點個數 */ Graph = CreateGraph(Nv); /* 初始化有Nv個頂點但沒有邊的圖 */ scanf("%d", &(Graph->Ne)); /* 讀入邊數 */ if ( Graph->Ne != 0 ) { /* 如果有邊 */ E = (Edge)malloc(sizeof(struct ENode)); /* 建立邊結點 */ /* 讀入邊,格式為"起點 終點 權重",插入鄰接矩陣 */ for (i=0; i<Graph->Ne; i++) { scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); /* 注意:如果權重不是整型,Weight的讀入格式要改 */ InsertEdge( Graph, E ); } } /* 如果頂點有數據的話,讀入數據 */ for (V=0; V<Graph->Nv; V++) scanf(" %c", &(Graph->Data[V])); return Graph; }
6.3.2 Python表示
# python語言實現 # python閉門造車版本,沒有一定實力,你就別為難自己了 class Graph_Matrix: """ Adjacency Matrix """ def __init__(self, vertices=[], matrix=[]): """ :param vertices:a dict with vertex id and index of matrix , such as {vertex:index} :param matrix: a matrix """ self.matrix = matrix self.edges_dict = {} # {(tail, head):weight} self.edges_array = [] # (tail, head, weight) self.vertices = vertices self.num_edges = 0 # if provide adjacency matrix then create the edges list if len(matrix) > 0: if len(vertices) != len(matrix): raise IndexError self.edges = self.getAllEdges() self.num_edges = len(self.edges) # if do not provide a adjacency matrix, but provide the vertices list, build a matrix with 0 elif len(vertices) > 0: self.matrix = [[0 for col in range(len(vertices))] for row in range(len(vertices))] self.num_vertices = len(self.matrix) def isOutRange(self, x): try: if x >= self.num_vertices or x <= 0: raise IndexError except IndexError: print("節點下標出界") def isEmpty(self): if self.num_vertices == 0: self.num_vertices = len(self.matrix) return self.num_vertices == 0 def add_vertex(self, key): if key not in self.vertices: self.vertices[key] = len(self.vertices) + 1 # add a vertex mean add a row and a column # add a column for every row for i in range(self.getVerticesNumbers()): self.matrix[i].Append(0) self.num_vertices += 1 nRow = [0] * self.num_vertices self.matrix.append(nRow) def getVertex(self, key): pass def add_edges_from_list(self, edges_list): # edges_list : [(tail, head, weight),()] for i in range(len(edges_list)): self.add_edge(edges_list[i][0], edges_list[i][1], edges_list[i][2], ) def add_edge(self, tail, head, cost=0): # if self.vertices.index(tail) >= 0: # self.addVertex(tail) if tail not in self.vertices: self.add_vertex(tail) # if self.vertices.index(head) >= 0: # self.addVertex(head) if head not in self.vertices: self.add_vertex(head) # for directory matrix self.matrix[self.vertices.index(tail)][self.vertices.index(head)] = cost # for non-directory matrix # self.matrix[self.vertices.index(fromV)][self.vertices.index(toV)] = # self.matrix[self.vertices.index(toV)][self.vertices.index(fromV)] = cost self.edges_dict[(tail, head)] = cost self.edges_array.append((tail, head, cost)) self.num_edges = len(self.edges_dict) def getEdges(self, V): pass def getVerticesNumbers(self): if self.num_vertices == 0: self.num_vertices = len(self.matrix) return self.num_vertices def getAllVertices(self): return self.vertices def getAllEdges(self): for i in range(len(self.matrix)): for j in range(len(self.matrix)): if 0 < self.matrix[i][j] < float('inf'): self.edges_dict[self.vertices[i], self.vertices[j]] = self.matrix[i][j] self.edges_array.append([self.vertices[i], self.vertices[j], self.matrix[i][j]]) return self.edges_array def __repr__(self): return str(''.join(str(i) for i in self.matrix)) def to_do_vertex(self, i): print('vertex: %s' % (self.vertices[i])) def to_do_edge(self, w, k): print('edge tail: %s, edge head: %s, weight: %s' % (self.vertices[w], self.vertices[k], str(self.matrix[w][k]))) import networkx as nx import matplotlib.pyplot as plt def draw_undircted_graph(my_graph): G = nx.Graph() # 建立一個空的無向圖G for node in my_graph.vertices: G.add_node(str(node)) for edge in my_graph.edges: G.add_edge(str(edge[0]), str(edge[1])) print("nodes:", G.nodes()) # 輸出全部的節點: [1, 2, 3] print("edges:", G.edges()) # 輸出全部的邊:[(2, 3)] print("number of edges:", G.number_of_edges()) # 輸出邊的數量:1 nx.draw(G, with_labels=True) plt.savefig("undirected_graph.png") plt.show()
# python語言實現 # python導入模塊 import networkx as nx import matplotlib.pyplot as plt import numpy as np G = nx.Graph() Matrix = np.array( [ [0, 1, 1, 1, 1, 1, 0, 0], # a [0, 0, 1, 0, 1, 0, 0, 0], # b [0, 0, 0, 1, 0, 0, 0, 0], # c [0, 0, 0, 0, 1, 0, 0, 0], # d [0, 0, 0, 0, 0, 1, 0, 0], # e [0, 0, 1, 0, 0, 0, 1, 1], # f [0, 0, 0, 0, 0, 1, 0, 1], # g [0, 0, 0, 0, 0, 1, 1, 0] # h ] ) # 建立一個空的無向圖 for i in range(len(Matrix)): for j in range(len(Matrix)): G.add_edge(i, j) nx.draw(G) plt.show()
七、鄰接表
可以來第二個鄰接表了,如下圖所示:
對于上圖的鄰接表,其中G[N]為指針數組,對應矩陣每行一個鏈表只存非0元素,對于有權重的網絡(以后就知道了),結構中增加關于權重的域(多一個權重相關的值)。
但是一定要注意:圖中的頂點之間(鄰接矩陣)一定要足夠稀疏才合算呀!
7.1 鄰接表的優點
好了,長話短說,鄰接表就以下四個優點:
- 方便找任一頂點的所有鄰接點
- 節約稀疏圖的空間
- 需要N個頭指針 + 2E個結點(每個結點至少兩個域,頭指針5,結點9;也有可能頭指針9,結點5)
- 方便計算任一頂點的度
- 無向圖:是的
- 有向圖:只能計算出度;需要構造逆鄰接表(存指向自己的邊)來方便計算入度
7.2 鄰接表的缺點
就一點,不廢話,自己考慮為什么:
- 不方便檢查任意一對頂點間是否存在邊
7.3 鄰接表的代碼表示
直接上代碼吧。
7.2.1 c表示
/* c語言實現 */ /* 圖的鄰接表表示法 */ #define MaxVertexNum 100 /* 最大頂點數設為100 */ typedef int Vertex; /* 用頂點下標表示頂點,為整型 */ typedef int WeightType; /* 邊的權值設為整型 */ typedef char DataType; /* 頂點存儲的數據類型設為字符型 */ /* 邊的定義 */ typedef struct ENode *PtrToENode; struct ENode{ Vertex V1, V2; /* 有向邊<V1, V2> */ WeightType Weight; /* 權重 */ }; typedef PtrToENode Edge; /* 鄰接點的定義 */ typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{ Vertex AdjV; /* 鄰接點下標 */ WeightType Weight; /* 邊權重 */ PtrToAdjVNode Next; /* 指向下一個鄰接點的指針 */ }; /* 頂點表頭結點的定義 */ typedef struct Vnode{ PtrToAdjVNode FirstEdge;/* 邊表頭指針 */ DataType Data; /* 存頂點的數據 */ /* 注意:很多情況下,頂點無數據,此時Data可以不用出現 */ } AdjList[MaxVertexNum]; /* AdjList是鄰接表類型 */ /* 圖結點的定義 */ typedef struct GNode *PtrToGNode; struct GNode{ int Nv; /* 頂點數 */ int Ne; /* 邊數 */ AdjList G; /* 鄰接表 */ }; typedef PtrToGNode LGraph; /* 以鄰接表方式存儲的圖類型 */ LGraph CreateGraph( int VertexNum ) { /* 初始化一個有VertexNum個頂點但沒有邊的圖 */ Vertex V; LGraph Graph; Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立圖 */ Graph->Nv = VertexNum; Graph->Ne = 0; /* 初始化鄰接表頭指針 */ /* 注意:這里默認頂點編號從0開始,到(Graph->Nv - 1) */ for (V=0; V<Graph->Nv; V++) Graph->G[V].FirstEdge = NULL; return Graph; } void InsertEdge( LGraph Graph, Edge E ) { PtrToAdjVNode NewNode; /* 插入邊 <V1, V2> */ /* 為V2建立新的鄰接點 */ NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode)); NewNode->AdjV = E->V2; NewNode->Weight = E->Weight; /* 將V2插入V1的表頭 */ NewNode->Next = Graph->G[E->V1].FirstEdge; Graph->G[E->V1].FirstEdge = NewNode; /* 若是無向圖,還要插入邊 <V2, V1> */ /* 為V1建立新的鄰接點 */ NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode)); NewNode->AdjV = E->V1; NewNode->Weight = E->Weight; /* 將V1插入V2的表頭 */ NewNode->Next = Graph->G[E->V2].FirstEdge; Graph->G[E->V2].FirstEdge = NewNode; } LGraph BuildGraph() { LGraph Graph; Edge E; Vertex V; int Nv, i; scanf("%d", &Nv); /* 讀入頂點個數 */ Graph = CreateGraph(Nv); /* 初始化有Nv個頂點但沒有邊的圖 */ scanf("%d", &(Graph->Ne)); /* 讀入邊數 */ if ( Graph->Ne != 0 ) { /* 如果有邊 */ E = (Edge)malloc( sizeof(struct ENode) ); /* 建立邊結點 */ /* 讀入邊,格式為"起點 終點 權重",插入鄰接矩陣 */ for (i=0; i<Graph->Ne; i++) { scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); /* 注意:如果權重不是整型,Weight的讀入格式要改 */ InsertEdge( Graph, E ); } } /* 如果頂點有數據的話,讀入數據 */ for (V=0; V<Graph->Nv; V++) scanf(" %c", &(Graph->G[V].Data)); return Graph; }
7.3.2 Python表示
# python語言實現 class Vertex(object): # 初始化頂點 def __init__(self, key): self.id = key # 初始化頂點的鍵 self.connectedTo = {} # 初始化頂點的值 # 添加鄰居頂點,參數nbr是鄰居頂點的鍵,默認權重為0 def addNeighbor(self, nbr, weight=0): self.connectedTo[nbr] = weight def __str__(self): return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo]) # 獲取該頂點所有鄰居頂點的鍵 def getConnections(self): return self.connectedTo.keys() # 獲取頂點的鍵 def getId(self): return self.id # 獲取到某鄰居頂點的權重 def getWeight(self, nbr): return self.connectedTo[nbr] # 自定義圖類 class Graph(object): # 初始化圖 def __init__(self): self.vertList = {} # 初始化鄰接表 self.numVertices = 0 # 初始化頂點數 # 添加頂點 def addVertex(self, key): newVertex = Vertex(key) # 創建頂點 self.vertList[key] = newVertex # 將新頂點添加到鄰接表中 self.numVertices = self.numVertices + 1 # 鄰接表中頂點數+1 return newVertex # 獲取頂點 def getVertex(self, n): if n in self.vertList: # 若待查詢頂點在鄰接表中,則 return self.vertList[n] # 返回該頂點 else: return None # 使之可用in方法 def __contains__(self, n): return n in self.vertList # 添加邊,參數f為起始頂點的鍵,t為目標頂點的鍵,cost為權重 def addEdge(self, f, t, cost=0): if f not in self.vertList: # 起始頂點不在鄰接表中,則 self.addVertex(f) # 添加起始頂點 if t not in self.vertList: # 目標頂點不在鄰接表中,則 self.addVertex(t) # 添加目標頂點 self.vertList[f].addNeighbor(self.vertList[t], cost) # 在鄰接表中添加起始點的目標點及權重 # 獲取鄰接表中所有頂點的鍵 def getVertices(self): return self.vertList.keys() # 迭代顯示鄰接表的每個頂點的鄰居節點 def __iter__(self): return iter(self.vertList.values()) if __name__ == '__main__': g = Graph() # 實例化圖類 for i in range(6): g.addVertex(i) # 給鄰接表添加節點 print(g.vertList) # 打印鄰接表 g.addEdge(0, 1, 5) # 給鄰接表添加邊及權重 g.addEdge(0, 5, 2) g.addEdge(1, 2, 4) g.addEdge(2, 3, 9) g.addEdge(3, 4, 7) g.addEdge(3, 5, 3) g.addEdge(4, 0, 1) g.addEdge(5, 4, 8) g.addEdge(5, 2, 1) for v in g: # 循環每個頂點 for w in v.getConnections(): # 循環每個頂點的所有鄰居節點 print("(%s, %s)" % (v.getId(), w.getId())) # 打印頂點和其鄰居節點的鍵