資料結構導論之第五章圖-有解無憂

一、圖的概念

圖的定義

1、圖 在樹形結構中，結點間具有層次關系，每一層結點只能和上一層中的至多一個結點相關，但可能和下一層的多個結點相關，而在圖結構中，任意兩個結點之間都可能相關，即結點之間的鄰接關系可以是任意的
圖G:是由集合V和E組成，記成G=(V,E)； V 是頂點集(非空)；E 是邊集（可空）;邊是頂點的有序對或無序對;（邊反映了兩頂點之間的關系）

2、有向圖：邊是頂點的有序對的圖（圖中每條邊都用箭頭指明了方向）一個具有 n 個頂點的有向完全圖的弧數為 n(n-1)
3、無向圖：邊是頂點的無序對的圖，一個具有 n 個頂點的無向完全圖的邊數為 n(n-1)/2，

4、權、帶權圖： 圖的邊附帶數值，這個數值叫權，權在實際應用中可表示從一個頂點到另一個頂點的距離、代價或耗費等，每條邊都帶權的圖稱為帶權圖，

5、頂點的度、入度、出度

無向圖中頂點 v 的度是與該頂點相關聯的邊的數目，記為 D(v)，
如果 G 是一個有向圖，則把以頂點 v 為終點的弧的數目稱為 v 的入度，記為 ID(v)；把以頂點 v 為始點的弧的數目稱為 v 的出度，記為 OD(v)，有向圖中頂點 v 的度等于入度與出度的和，即 D(v)=ID(v)+OD(v)，

6、子圖：設 G=(V，E)是一個圖，若 E'是 E 的子集，V'是 V 的子集，并且 E'中的邊僅與 V'中的頂點相關聯，則圖 G'=(V'，E')稱為圖 G 的子圖，
7、路徑、路徑長度：在無向圖 G= (V，E)中，從頂點 v 到頂點 v'的路徑是一個頂點序列：v，vi1，vi2，…， vim, v',其中(v, vi1)，（vi1，vi2)，…，（vim，v')為圖 G 中的邊，若 G 是有向圖，則要求這個頂點序列滿足：<v，vi1>, <vi1，vi2>，…，<vim，v'>為圖 G 中的弧，路徑上邊(或弧)的數目稱為路徑長度，

9、簡單路徑：除第一個和最后一個外，其余各頂點均不相同的路徑，
10、回路：第一個和最后一個頂點相同的路徑，也稱環；
11、簡單回路： 第一個和最后一個頂點相同的簡單路徑；注：回路中可以有多個圈，而簡單回路只能有一個圈，

生成樹：含有該連通圖的全部頂點的一個極小連通子圖，若連通圖G的頂點個數為n，則G的生成樹的邊數為n-1，
G的子圖G’邊數大于n-1,則G’中一定有環，
G的子圖G’邊數小于n-1,則G’中一定不連通，
生成森林——在非連通圖中，每個連通分量都可得到一個極小連通子圖，也就是生成樹，這些生成樹就組成了一個非連通圖的生成森林，

圖的運算：

?建立圖 GreateGraph(G,V,E)
?取頂點資訊 GetVex(G,u)
?取邊資訊 Getarc(G,u,v)
?查詢第一個鄰接點FirstVex(G,u)
?查詢下一個鄰接點NextVex(G,u,v)
?插入頂點 InsertVex(G,v)
?洗掉頂點 DeleteVex(G,v)
?插入邊 InsertArc(G,v,w)
?洗掉邊 DeleteArc(G,v,w)
?遍歷圖 Travers(G,tag)