数据结构-王道2017-第5章 图
1.圖的基本概念
? 1）圖的定義
? ? ?圖G由頂點集V和邊集E組成，記為G=(V,E),其中V(G)表示圖G中定點的有限非空集；E(G)表示圖G中頂點之間的關系（邊）集合。V={v1,v2,..,vn},用|V|表示圖G中頂點的個數，也稱為圖G的階，E={（u，v）| u ∈ V,v ∈ V},用|E|表示圖G中邊的條數。
? ?注意：線性表可以是空表，樹可以是空樹，但圖不可一世空圖。就是說圖中不能一個頂點也沒有，圖的頂點集一定非空，但邊集E可以為空，此時圖中只有頂點沒有邊
? ?2）簡單圖：不存在重復邊；不存在頂點到自身的邊，則稱圖G為簡單圖
? ? ? ? 多重圖：圖G中兩個結點之間的邊數多于一條，又允許頂點通過同一條邊與自己關聯，則G為多重圖。多重圖的定義和簡單圖是相對的。
? ? ? ?完全圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖，含有n個頂點的無向完全圖又n(n-1)/2條邊，含有n個頂點的有向完全圖有n(n-1)條有向邊
? ?3）連通：在無向圖中，若從頂點v到頂點w有路徑存在，則稱v和w是連通的，若圖G中任意兩個頂點都是連通的，則稱圖G為連通圖，否則稱為非連通圖
? ? ? ?無向圖中的極大連通子圖稱為連通分量，如果一個圖有n個頂點，并且有小于n-1條邊，那么此圖必是非連通圖。
? 注意：極大連通子圖要求該連通子圖包含其所有的邊；極小連通子圖是既要保持圖連通，又要使得邊數最少的子圖。
? 4）強連通圖、強連通分量
? ? ?在有向圖中，若從頂點v到頂點w和從頂點w到頂點v之間都有路徑，則稱這兩個頂點是強連通的。若圖中任何一對頂點都是強連通的，則稱該圖為強連通圖。有向圖的極大強連通子圖稱為有向圖的強連通分量。
? 5）生成樹、生成森林
? ? ? 連通圖的生成樹是包含圖中全部頂點的一個極小連通子圖。如果圖中定點數為n，則它的生成樹含有n-1條邊。對于生成樹而言，看去他的一條邊，則會變成非連通圖，若加上一條邊則會形成回路。在非連通圖中，連通分量的生成樹構成了非連通圖的生成森林。
? ? 注意：包含無向圖中全部頂點的極小連通子圖，只有生成樹滿足條件，因為砍去生成樹的任意一條邊，圖將不再連通。
? 6）定點的度、入度出度
? ? ? 每個頂點的度定義為以該頂點為一個端點的邊的數目
? ? ? 對于無向圖，頂點v的度是指依附于該頂點的邊的條數，記為TD(v)；無向圖的全部頂點的度之和等于邊數的兩倍，這是因為每條邊和兩個頂點相關聯。
? ? ? 對于有向圖，頂點v的度分為入度和出度，入度是以頂點v為終點的有向邊的數目，記為ID(v),出度是以頂點v為起點的有向邊的數目，記為OD(v)，頂點v的度等于出度和入度之和TD(v) = ID(v) +OD(v);
? ? ?有向圖的出度和入度之和相等并且等于邊數。
? ?7）邊的權和網
? ? ?在一個圖中，每條邊都可以標上具有某種含義的值，該數值稱為該邊的權值。這種邊上帶權值的圖稱為帶權圖，也稱為網。
? ?8）稠密圖、稀疏圖
? ?邊數很少的圖稱為稀疏圖，反之，稱之為稠密圖。一般當圖滿足|E|<|V|*log|V|時，可以看做稀疏圖
? ?9）路徑、路徑長度和回路
? ? ?頂點v1到v2的一條路徑指的是頂點序列，路徑上邊的數目稱為路徑長度。第一個頂點和最后一個頂點相同的路徑稱為環或回路。如果一個圖有n個頂點，并且有大于n-1條邊，這個圖一定有環。
? ?10）簡單路徑、簡單回路
? 在路徑序列中，頂點不重復出現的路徑稱為簡單路徑、除了第一個和最后一個頂點之外，其余頂點不重復出現的回路稱為簡單回路。
? ?11）距離
? 從頂點u出發到頂點v的最短路徑若存在，則此路徑的長度稱作從u到v的距離。若從u到v根本不存在路徑，則記該距離為無窮.
? ?12)有向樹：有一個頂點的入度為0，其余頂點的入度均為1的有向圖稱為有向樹。
? ? ?
2.圖的存儲及基本操作
? 所選存儲方式應該適合于欲求解的問題，無論是無向圖還是有向圖，主要的存儲方式都有兩種：鄰接矩陣和鄰接表。前者屬于圖的順序存儲結構，后者屬于圖的鏈接存儲結構。
? ?1）鄰接矩陣法??
? ? ?稠密圖適合使用鄰接矩陣的存儲表示
? ?2)鄰接表法
? ? ?當圖為稀疏圖時，使用鄰接矩陣會浪費大量的空間。而圖的鄰接表法結合了順序存儲和鏈式存儲方法，大大減少了這種不必要的浪費。
? ? ?對圖G中的每個頂點vi建立一個單鏈表，第i個單鏈表中的結點表示依附于頂點vi的邊（對于有向圖則是以頂點vi為尾的弧），這單鏈表稱為vi的邊表（對于有向圖，則稱為出邊表），在鄰接表中，存在兩種結點：頂點表結點和邊表結點。
#define MaxVertexNum 100typedef struct ArcNode{int adjvex; //弧指向的鄰接點的位置---頂點數組下標struct ArcNode * next; //指向下一條邊的指針//ElemType data; //網的邊權值 }ArcNode;typedef struct VNode{VertexType data; //頂點信息ArcNode * first; //指向邊表第一個結點 }VNode,AdjList[MaxVertexNum]; typedef struct {AdjList vertices; //鄰接表int vexnum,arcnum; //圖的頂點數和弧數 }ALGraph; //ALGraph是以鄰接表存儲的圖類型? ?a)鄰接表特點
? ? ? 如果G為無向圖，則所需存儲空間為O(|V|+2|E|);如果G為有向圖，則所需的存儲空間為O(|V|+|E|),無向圖中，每條邊會出現兩次
? ? ? 鄰接表中，給定一個頂點很容易查到它的所有鄰邊，在鄰接矩陣中需要掃描一行，時間為O(n),如果要確定給定的兩個頂點間是否存在邊，則在鄰接矩陣中可以立即查到，在鄰接表中則需要在相應結點中查找另一結點，效率較低。
? 3）十字鏈表
? ? ? 十字鏈表是有向圖的一種鏈式存儲結構，在十字鏈表中，對應于每條弧有一個結點，對應于每個頂點也有一個結點。
? ??
#define MaxV 100 //本質上也是鄰接表 typedef struct ArcNode{ //邊表結點int tailVex,headVex; //弧的頭尾結點struct ArcNode * hlink,*tlink; //分別指向弧頭相同和弧尾相同的結點 // ElemType data; //相關信息 }ArcNode;typedef struct VNode{VertexType data; //頂點信息ArcNode *firstin,*firstout; //指向第一條入弧和出弧 }VNode; typedef struct{ VNode xList[MaxV]; //十字鏈表int vexnum,arcnum; //圖的頂點數和邊數 }GLGraph; //以十字鏈表存儲的圖類型在十字鏈表中，極容易找到vi為尾的弧，也容易找到以vi為頭的弧，因而容易求出頂點的出度和入度。
?圖的十字鏈表是不唯一的，但一個十字鏈表表示確定一個圖。
4）鄰接多重表
? ?鄰接多重表是無向圖的另一種鏈式存儲結構，與十字鏈表類似，每一條邊用一個結點表示
? ? ? ? ? mark | ivex | ilink | jvex | jlink | info
? ?mark 為標志域，標記該條邊是否被搜索過;ivex和jvex分別表示該邊依附的兩個頂點，ilink指向下一條依附于ivex的邊，jlink指向下一條依附于頂點jvex的邊，info為指向和邊相關的各種信息的指針域。
?每一個頂點也用一個結點表示，由如下所示的兩個域組成
? ?data | firstedge
?每一條邊只有一個結點
#define MaxVertexNum 100 typedef struct ArcNode{bool mark; //訪問標記int ivex,jvex; //分別指向該弧的兩個結點struct ArcNode *ilink,*jlink; //分別指向兩個頂點的下一條邊//InfoType info; //相關信息 }ArcNode;typedef struct VNode{ //頂點表結點VertexType data; //頂點信息ArcNode * firstedge; //指向第一條依附在該頂點的邊 }VNode;typedef struct{VNode adjmuList[MaxVertexNum]; //鄰接表int vexnum,arcnum; //圖的頂點數和弧數 }AMLGraph;3.圖的遍歷
? ?圖的遍歷是指從圖中的某一頂點出發，按照某種搜索方法沿著圖中的邊對圖中的頂點訪問一次且僅訪問一次。注意到樹是一種特殊的圖，所以樹的遍歷也可以看做是一種特殊的圖的遍歷。兩種算法：廣度優先搜索和深度優先搜索。
? ?1)? 廣度優先搜索（Breadth-First-Search，BFS）
? ? ?類似于二叉樹的層序遍歷算法
?
#define MAX_N 100 bool visited[MAX_N];void BFSTraverse(Graph G,){for(int i = 0;i < G.vnum;i++)visited[i] = false;InitQueue(Q);for(int i = 0;i < G.vnum;i++)if(!visited[i])BFS(G,i); }void BFS(Graph G, int v){visit(v);visited[v] = true;EnQueue(Q,v);while(!Empty(Q)){DeQueue(Q,v); //頂點v出列for(w=neighbor(G,v);w>=0;w=nextNeighbor(G,v,w)){if(!visited[w]){
visit(w);visited[w] = true;EnQueue(Q,w);
} }}}
? 性能分析：無論是鄰接表還是鄰接矩陣的存儲方式，BFS算法都需要借助一個輔助隊列Q，n個頂點都需入隊一次，在最壞的情況下，空間復雜度為O(|V|)
? ?采用鄰接表存儲時，每個頂點均需搜索一次（或入隊一次），故時間復雜度為O(|V|),在搜索任一頂點的鄰接點時，每條邊至少訪問一次，故時間復雜度為O(|E|)，算法總的時間復雜度為O(|V|+|E|).當采用鄰接表存儲時，查找每個頂點的鄰接點所需時間為O(|V|),故算法總的時間復雜度為O(|V|^2)。
? 可以使用BFS算法求解單源最短路徑。
? ?給定圖的鄰接矩陣存儲表示是唯一的，故其廣度優先生成樹也是唯一的，但由于鄰接表存儲表示不唯一，故其廣度優先生成樹也是不唯一的。
? 2）深度優先搜索
? ? 類似于樹的先序遍歷
? ??
#define MAX_N 100 bool visited[MAX_N];void DFSTraverse(Graph G){for(int i = 0;i < G.vnum;i++){visited[i] = false;}for(int i =0;i < G.vnum;i++){ //對于每個連通分量進行遍歷if(!visited[i])DFS(G,i); } }void DFS(Graph G, int v){visit(v);visited[v] = true; //已經訪問for(w=neighbor(G,v);w >= 0;w=nextneighbor(G,v,w)){if(!visited[w]) //尚未訪問結點 DFS(G,w);} }?注意：同一個圖基于鄰接矩陣的遍歷所得到的DFS序列和BFS序列是唯一的，基于鄰接表的遍歷所得到的bfs和dfs是不唯一的（因為鄰接矩陣唯一，而鄰接表表示不唯一）
DFS算法的性能分析：
? ?是一個遞歸算法，需要借助遞歸工作棧，空間復雜度為O(|V|);遍歷圖的過程實質上是對每個頂點查找其鄰接點的過程，其耗費的時間取決于采用的存儲結構。以鄰接矩陣表示，查找每個頂點的鄰接點的所需時間為O(|V|),故總的時間復雜度為O(|V|^2).以鄰接表表示時，查找所有頂點的鄰接點所需時間為O(|E|),訪問頂點所需時間為O(|V|),總的時間復雜度為O(|V|+|E|);
?
? ??
?
轉載于:https://www.cnblogs.com/--CYH--/p/6790242.html
總結
以上是生活随笔為你收集整理的数据结构-王道2017-第5章 图的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： SQL基础--同义词
- 下一篇： poj 3485 区间选点