1、圖相關的專業術語
1）<v,w>：從v到w的一潭訓，v表示弧尾，w表示弧頭，有向弧，
2）(v,w)：無向弧，
3）有向圖：有向邊的有限集合，
4）無向圖：無向邊的有限集合，
5）簡單圖：不存在重復邊，不存在頂點到自身的邊，
6）多重圖：圖中某兩個結點之間的邊數多余一條，又允許頂點通過同一條邊和自己關聯，
7）無向完全圖：在無向圖中，任意兩個頂點之間都存在邊，含有n個頂點的無向完全圖有n(n-1)/2條邊，
8）有向完全圖：在有向圖中，任意兩個頂點之間都存在方向相反的兩潭訓，含有n個頂點的有向完全圖有n(n-1)條有向邊，
9）生成子圖：子圖的頂點的集合和圖的頂點集合相同，
10）連通圖：無向圖中任意兩個頂點都是連通的，
11）連通分量：無向圖中的極大連通子圖，
12）強連通圖：有向圖中任意兩個頂點都是強連通的，即從頂點v到頂點w以及從頂點v到頂點w之間都有路徑，
13）強連通分量：有向圖中的極大強連通子圖，
14）連通圖的生成樹：包含圖中全部頂點的一個極小連通子圖，圖中頂點數為n，則生成樹含有n-1條邊，對于生成樹而言，少一條邊則變成非連通圖，加一條邊則形成回路，
15）無向圖的度：依附于該頂點的邊的條數，無向圖的全部頂點的度的和等于邊數的2倍，
16）有向圖的度：入度和出度之和，有向圖的全部頂點的入度之和等于出度之和等于邊數，
17）回路或環：第一個頂點和最后一個頂點相同的路徑，一個圖有n個頂點，有大于n-1條邊，則此圖一定有環，
18）簡單路徑：頂點不重復出現的路徑，
19）簡單回路：除第一個頂點和最后一個頂點外，其余頂點不重復出現的回路，
20）有向樹：一個頂點的入度為0，其余頂點的入度均為1的有向圖，
21）關節點：在刪去頂點v以及和v相關聯的各邊之后，將圖的一個連通分量分割成兩個或兩個以上的連通分量，則頂點v為關節點（割點），
22）重連通圖：一個沒有關節點的連通圖，
2、圖的存盤
1）鄰接矩陣法
（1）鄰接矩陣存盤：指用一個一維陣列存盤圖中頂點資訊，用一個二維陣列存盤圖中邊的資訊，存盤頂點之間鄰接關系的二維陣列稱為鄰接矩陣，
（2）鄰接矩陣表示法的空間復雜度為O(n2)，n為頂點數，
（3）特點：無向圖的鄰接矩陣是對稱矩陣（并且唯一），
對于無向圖，鄰接矩陣的第i行（或第i列）非零元素的個數正好是第i個頂點的度，
對于有向圖，鄰接矩陣的第i行（或第i列）非零元素的個數正好是第i個頂點的出度（或入度），
稠密圖使用鄰接矩陣的存盤表示，
（4）圖的鄰接矩陣存盤結構
#define maxvertexnum 100
typedef struct {
char vex[maxvertexnum];
int edge[maxvertexnum][maxvertexnum];
int vexnum, arcnum;
}MGraph;
2）鄰接表法
（1）鄰接表：指對圖中的每個頂點建立一個單鏈表，
第i個單鏈表中的結點表示依附于頂點的邊（對于有向圖則以頂點為尾的弧），這個單鏈表就稱為頂點的邊表（對于有向圖則稱為出邊表），
邊表的頭指標和頂點的資料資訊采用順序存盤（稱為頂點表），
（2）鄰接表中的結點：頂點表結點和邊表結點，
頂點表
| data（頂點域） | firstarc（邊表頭指標） |
邊表
| adjvex（鄰接點域） | nextarc（指標域） |
（3）特點：若為無向圖，則所需存盤空間為O(|V|+2|E|)；若為有向圖，則所需存盤空間為O(|V|+|E|)，
稀疏圖采用鄰接表存盤，
方便找出一頂點的鄰邊，
有向圖的鄰接表表示中，求一個給定頂點的出度只需計算其鄰接表中的結點個數，求入度需要遍歷全部的鄰接表，
圖的鄰接表表示不唯一，
（4）圖的鄰接表存盤結構
typedef struct ArcNode{
int adjvex;
struct ArcNode * next;
}ArcNode;
typedef struct VNode {
char data;
ArcNode * first;
}VNode,AdjList[maxvertexnum];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
3）十字鏈表法：有向圖的一種鏈式存盤結構，
（1）十字鏈表中的結點：弧結點和頂點結點，
弧結點
| tailvex（尾域） | headvex（頭域） | hlink（鏈域，指向弧頭相同的下一潭訓） | tlink（鏈域，指向弧尾相同的下一潭訓） | info（指向弧的相關資訊） |
頂點結點
| data（存放頂點相關的資料資訊） | firstin（指向該頂點為弧頭的第一個弧結點） | firstout（指向該頂點為弧尾的第一個弧結點） |
（2）特點：圖的十字鏈表表示不唯一，但一個十字鏈表表示確定一個圖，
（3）圖的十字鏈表存盤結構
typedef struct ArcNode {
int tailvex, headvex;
struct ArcNode *hlink, *tlink;
}AreNode;
typedef struct VNode {
char data;
ArcNode *firstin, *firstout;
}VNode;
typedef struct {
VNode xlink[maxvertexnum];
int vexnum, arcnum;
}GLGraph;
4）鄰接多重表法：無向圖的一種鏈式存盤結構，
（1）鄰接多重表的結點：存盤邊和頂點的結點，
存盤邊的結點
| mark（標志域，可用于標記邊是否被搜索過） | ivex（該邊依附的其中一個頂點的位置） | ilink（指向下一條依附于頂點ivex的邊） | jvex（該邊依附的其中另一個頂點的位置） | jlink（指向下一條依附于頂點jvex的邊） | info（指向和邊相關的各種資訊的指標域） |
存盤頂點的結點
| data（存盤該頂點的相關資訊） | firstedge（指示第一條依附于該頂點的邊） |
（2）圖的鄰接多重表存盤結構
typedef struct ArcNode {
bool mark;
int ivex, jvex;
struct ArcNode *ilink, *jlink;
}AreNode;
typedef struct VNode {
char data;
ArcNode *firstdege;
}VNode;
typedef struct {
VNode adjmulist[maxvertexnum];
int vexnum, arcnum;
}AMLGraph;
3、圖的遍歷
1）廣度優先搜索：優先考慮最早被發現的頂點，類似于二叉樹的層序遍歷，
（1）BFS演算法：需要借助佇列，空間復雜度O(|V|)，采用鄰接表存盤方式時，時間復雜度O(|V|+|E|)；采用鄰接矩陣存盤方式時，時間復雜度O(|V|2)，
（2）廣度優先生成樹：廣度遍歷得到的遍歷樹，給定圖的鄰接矩陣存盤表示是唯一的，其廣度優先生成樹也是唯一的，由于鄰接表存盤表示不唯一，廣度優先生成樹不唯一，
2）深度優先搜索：優先考慮最后被發現的頂點，類似于樹的先序遍歷，
（1）DFS演算法：需要借助堆疊，空間復雜度O(|V|)，采用鄰接表存盤方式時，時間復雜度O(|V|+|E|)；采用鄰接矩陣存盤方式時，時間復雜度O(|V|2)，
（2）深度優先生成樹：深度優先生成樹不唯一，
4、圖的應用
1）最小生成樹(MST)：生成樹中權值最小的生成樹，
（1）一個連通圖的生成樹是圖的極小連通子圖，
（2）性質：最小生成樹不唯一，即最小生成樹的樹形不唯一，
當圖中各邊權值互不相等時，最小生成樹唯一，
最小生成樹的邊的權值之和是唯一的，而且是最小的，
最小生成樹的邊數為頂點數減1，
（3）Prim演算法：從頂點開始擴展最小生成樹，
時間復雜度為O(|V|2)，
適用于求解邊稠密的圖的最小生成樹，
（4）Kruskal演算法：按權值的遞增次序選擇合適的邊來構造最小生成樹的方法，
時間復雜度為O(|E|log|E|)，
適用于邊稀疏而頂點較多的圖，
2）最短路徑：帶權路徑長度最短的路徑，
（1）Dijkstra演算法：求單源最短路徑，即求圖中某一頂點到其他各頂點的最短路徑，
使用鄰接矩陣表示時，時間復雜度為O(|V|2)；采用帶權的鄰接表表示時，時間復雜度為O(|V|2)，找出所有結點對之間的最短距離，時間復雜度為O(|V|3)
（2）Floyd演算法：求每對頂點間的最短路徑，
3）拓撲排序
（1）有向無環圖(DAG)：一個有向圖中不存在環，
（2）拓撲排序：由一個有向無環圖的頂點組成的序列，且滿足以下條件：
每個頂點出現且只出現一次，
若頂點A在序列中排在頂點B的前面，則圖中不存在從頂點B到頂點A的路徑，
（3）時間復雜度為O(|V|+|E|)，
4）關鍵路徑
（1）AOE網：在帶權有向無環圖中，以頂點表示時間，以有向邊表示活動，以邊上的權值表示完成該活動的開銷，則稱這種有向圖為用邊表示活動的網路，
（2）開始頂點（源點）：在AOE網中僅有一個入度為0的頂點，表示工程的開始，
（3）結束頂點（匯點）：在AOE網中僅有一個出度為0的頂點，表示工程的結束，
（4）關鍵路徑：從源點到匯點的所有路徑中，具有最大路徑長度的路徑，
關鍵路徑上的活動稱為關鍵活動，
（5）最短時間：整個工程的關鍵路徑的長度，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/55346.html
標籤：其他