基本介紹
- 中文名：圖
- 外文名：Graph
- 學科：數學
- 分類：有/無向圖等
定義,二元組的定義,三元組的定義,分類,有/無向圖,單圖,基本術語,圖的存儲表示,圖的基本操作,生成樹,圖的生成樹和森林,最小生成樹,存儲結構,圖的遍歷,深度優先遍歷,廣度優先遍歷,拓撲排序,重要的圖,基本概念,圖的遍歷,
定義
主要有以下兩種定義。
二元組的定義
圖G是一個有序二元組(V,E)，其中V稱為頂集(Vertices Set)，E稱為邊集(Edges set)，E與V不相交。它們亦可寫成V(G)和E(G)。
E的元素都是二元組，用(x,y)表示，其中x,y∈V。
三元組的定義
圖G是指一個三元組(V,E,I)，其中V稱為頂集，E稱為邊集，E與V不相交；I稱為關聯函式，I將E中的每一個元素映射到
。如果e被映射到(u,v)，那么稱邊e連線頂點u,v，而u,v則稱作e的端點，u,v此時關於e相鄰。同時，若兩條邊i,j有一個公共頂點u，則稱i,j關於u相鄰。
分類
有/無向圖
單圖
一個圖如果任意兩頂點之間只有一條邊（在有向圖中為兩頂點之間每個方向只有一條邊）；邊集中不含環，則稱為單圖。
基本術語
階（Order）：圖G中點集V的大小稱作圖G的階。
子圖（Sub-Graph）：當圖G'=(V',E')其中V‘包含於V，E’包含於E，則G'稱作圖G=(V,E)的子圖。每個圖都是本身的子圖。
生成子圖（Spanning Sub-Graph）：指滿足條件V(G') = V(G)的G的子圖G'。
導出子圖（Induced Subgraph）：以圖G的頂點集V的非空子集V1為頂點集，以兩端點均在V1中的全體邊為邊集的G的子圖，稱為V1導出的導出子圖；以圖G的邊集E的非空子集E1為邊集，以E1中邊關聯的頂點的全體為頂點集的G的子圖，稱為E1導出的導出子圖。
度（Degree）：一個頂點的度是指與該頂點相關聯的邊的條數，頂點v的度記作d(v)。
入度（In-degree）和出度（Out-degree）：對於有向圖來說，一個頂點的度可細分為入度和出度。一個頂點的入度是指與其關聯的各邊之中，以其為終點的邊數；出度則是相對的概念，指以該頂點為起點的邊數。
自環（Loop）：若一條邊的兩個頂點為同一頂點，則此邊稱作自環。
路徑（Path）：從u到v的一條路徑是指一個序列v0,e1,v1,e2,v2,...ek,vk，其中ei的頂點為vi及vi - 1，k稱作路徑的長度。如果它的起止頂點相同，該路徑是“閉”的，反之，則稱為“開”的。一條路徑稱為一簡單路徑(simple path)，如果路徑中除起始與終止頂點可以重合外，所有頂點兩兩不等。
行跡（Trace）：如果路徑P(u,v)中的邊各不相同，則該路徑稱為u到v的一條行跡。
軌道（Track）：如果路徑P(u,v)中的頂點各不相同，則該路徑稱為u到v的一條軌道。
閉的行跡稱作迴路（Circuit），閉的軌稱作圈（Cycle）。
（另一種定義是：walk對應上述的path，path對應上述的track。Trail對應trace。）
橋（Bridge）：若去掉一條邊，便會使得整個圖不連通，該邊稱為橋。
圖的存儲表示
數組（鄰接矩陣）存儲表示（有向或無向）
鄰接表存儲表示
無向圖的鄰接多重表存儲表示
一個不帶權圖中若兩點不相鄰，鄰接矩陣相應位置為0，對帶權圖(網)，相應位置為∞。一個圖的鄰接矩陣表示是唯一的，但其鄰接表表示不唯一。在鄰接表中，對圖中每個頂點建立一個單鍊表（並按建立的次序編號），第i個單鍊表中的結點表示依附於頂點vi的邊（對於有向圖是以頂點vi為尾的弧）。每個結點由兩個域組成：鄰接點域(adjvex)，用以指示與vi鄰接的點在圖中的位置，鏈域(nextarc)用以指向依附於頂點vi的下一條邊所對應的結點。如果用鄰接表存放網（帶權圖）的信息，則還需要在結點中增加一個存放權值的域（info）。每個頂點的單鍊表中結點的個數即為該頂點的出度(與該頂點連線的邊的總數)。無論是存儲圖或網，都需要在每個單鍊表前設一表頭結點，這些表頭結點的第一個域data用於存放結點vi的編號i，第二個域firstarc用於指向鍊表中第一個結點。
在有向圖中，通常將邊稱作弧，含箭頭的一端稱為弧頭，另一端稱為弧尾，記作<vi,vj>，它表示從頂點vi到頂點vj有一條邊。
若有向圖中有n個頂點，則最多有n(n-1)條弧，我們又將具有n(n-1)條弧的有向圖稱作有向完全圖。以頂點v為弧尾的弧的數目稱作頂點v的出度，以頂點v為弧頭的弧的數目稱作頂點v的入度。在無向圖中，邊記作(vi,vj)，它蘊涵著存在< vi,vj>和<vj,vi>兩條弧。若無向圖中有n個頂點，則最多有n(n-1)/2條弧，我們又將具有n(n-1)/2條弧的無向圖稱作無向完全圖。與頂點v相關的邊的條數稱作頂點v的度。
路徑長度是指路徑上邊或弧的數目。
若第一個頂點和最後一個頂點相同，則這條路徑是一條迴路。
若路徑中頂點沒有重複出現，則稱這條路徑為簡單路徑。
圖的基本操作
（1）創建一個圖結構 CreateGraph(G)
（2）檢索給定頂點 LocateVex(G,elem)
（3）獲取圖中某個頂點 GetVex(G,v)
（4）為圖中頂點賦值 PutVex(G,v,value)
（5）返回第一個鄰接點 FirstAdjVex(G,v)
（6）返回下一個鄰接點 NextAdjVex(G,v,w)
（7）插入一個頂點 InsertVex(G,v)
（8）刪除一個頂點 DeleteVex(G,v)
（9）插入一條邊 InsertEdge(G,v,w)
（10）刪除一條邊 DeleteEdge(G,v,w)
（11）遍歷圖 Traverse(G,v)
生成樹
圖的生成樹和森林
顯示了一個無向連通圖的生成樹，雙線圈表示的頂點為生成樹的根結點。
最小生成樹
在一個圖中，每條邊或弧可以擁有一個與之相關的數值，我們將它稱為權。這些權可以具有一定的含義，比如，表示一個頂點到達另一個頂點的距離、所花費的時間、線路的造價等等。這種帶權的圖通常被稱作網。
圖或網的生成樹不是唯一的，從不同的頂點出發可以生成不同的生成樹，但n個結點的生成樹一定有n-1條邊
下面我們計算一下上面兩棵生成樹的權值之和。第一棵生成樹的權值總和是：16+11+5+6+18=56；第二棵生成樹的權值是：16+19+33+18+6=92。通常我們將權值總和最小的生成樹稱為最小生成樹。
構造最小生成樹的方法：最初生成樹為空，即沒有一個結點和一條邊，首先選擇一個頂點作為生成樹的根，然後每次從不在生成樹中的邊中選擇一條權值儘可能小的邊，為了保證加入到生成樹中的邊不會造成迴路，與該邊鄰接的兩個頂點必須一個已經在生成樹中，一個則不在生成樹中，若網中有n個頂點（這裡考慮的網是一個連通無向圖），則按這種條件選擇n-1邊就可以得到這個網的最小生成樹了。詳細的過程可以描述為：設定2個集合，U集合中的元素是在生成樹中的結點，V-U集合中的元素是不在生成樹中的頂點。首先選擇一個作為生成樹根結點的頂點，並將它放入U集合，然後在那些一端頂點在U集合中，而另一端頂點在V-U集合中的邊中找一條權最小的邊，並把這條邊和那個不在U集合中的頂點加入到生成樹中，即輸出這條邊，然後將其頂點添加到U集合中，重複這個操作n-1次。
下面我們考慮一下如何實現這個操作過程的算法。
分析 ：（1）它主要有兩項操作：按條件選擇一條邊和將頂點加入到U集合中；（2）網中的每個頂點不是在U集合中，就是在V-U集合中。為了提高算法的時間、空間效率，我們將為這個算法設計一個輔助數組closedge，用來記錄從集合U到集合V-U具有最小權值的邊。對每個屬於V-U集合的頂點，在輔助數組中存在一個相應的分量closedge[i-1]，它包括兩個域，一個域用來表示在該頂點與V-U集合中某些頂點構成的邊中權最小的那條邊的權值，若該頂點進入U集合，則值為0；另一個域表示這條最小權值的邊對應的在V-U集合中的頂點下標。其類型定義如下所示：
#define MAX_NUM 10struct{int adjvex;float lowcist;}closedge[MAX_NUM];整個算法的執行過程可以描述為：
{初始化closedge數組的內容；選擇某個頂點k作為生成樹的根結點，並將它加入到U集合中；重複下列操作n-1次：l選擇一條滿足條件的邊；l輸出這條邊的兩個端點；l修改V-U集合中的頂點信息，即與U集合中構成最小權值的邊。}假設該網以鄰接矩陣的形式給出，則完整的算法為：
void Mini_SpanTree(GraphG,intk,intn){//G是網的鄰接矩陣，k是生成樹根結點的序號，n是網的頂點數目for(j=0;j<n;j++)if(j!=k)closedge[j]={k,G[k][j]};closedge[k].lowcost=0;for(i=1;i<n;i++){k=minmun(closedge);printf(k,closedge[k].adjvex);closedge[k].lowcost=0;//將頂點加入U集合中for(j=0;j<n;j++)if(closedge&&G[k][j]<closedge[j].lowcost)closedge[j]={k,G[k][j]};}}存儲結構
鄰接矩陣:
具有n個頂點的有向圖可以用一個n′n的方形矩陣表示。假設該矩陣的名稱為M，則當<vi,vj>是該有向圖中的一條弧時，M[i,j]=1；否則M[i,j]=0。第i個頂點的出度為矩陣中第i行中"1"的個數；入度為第i列中"1"的個數，並且有向圖弧的條數等於矩陣中"1"的個數。
無向圖的鄰接矩陣
具有n個頂點的無向圖也可以用一個n′n的方形矩陣表示。假設該矩陣的名稱為M，則當（vi,vj）是該無向圖中的一條邊時，M[i,j]=M[j,i]=1；否則，M[i,j]=M[j,j]=0。第i個頂點的度為矩陣中第i 行中"1"的個數或第i列中"1"的個數。圖中邊的數目等於矩陣中"1"的個數的一半，這是因為每條邊在矩陣中描述了兩次。
在C 語言中，實現鄰接矩陣表示法的類型定義如下所示：
#define MAX_VERTEX_NUM 20typedef struct graph{Elemtype elem[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int n;}Graph;邊結點的結構為：
elem是頂點內容，firstedge是指向第一條邊或弧結點的指針。
在C語言中，實現鄰接表表示法的類型定義如下所示：
#define MAX_VERTEX_NUM 30//最大頂點個數typedef struct EdgeLinklist{//邊結點int adjvex;struct EdgeLinklist*next;}EdgeLinklist;typedef struct VexLinklist{//頂點結點Elemtype elem;EdgeLinklist* firstedge;}VexLinklist,AdjList[MAX_VERTEX_NUM];（1） 創建有向圖鄰接表
void Create_adj(AdjListad j,int n){for(i=0;i<n;i++){//初始化頂點數組scanf(&adj.elem);adj.firstedge=NULL;}scanf(&i,&j);//輸入弧while(i){s=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));//創建新的弧結點s->adgvex=j-1;s->next=adj[i-1].firstedge;//將新的弧結點插入到相應的位置adj[i-1].firstegde=s;scanf(&i,&j);//輸入下一條弧}}void Create_adj(AdjListadj,intn){for(i=0;i<n;i++){//初始化鄰接表scanf(&adj.elem);adj.firstedge=NULL;}scanf(&i,&j);//輸入邊while(i){s1=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));s1->adgvex=j-1;s2=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));s2->adgvex=i-1;s1->next=adj[i-1].firstedge;adj[i-1].firstegde=s1;s2->next=adj[j-1].firstedge;adj[j-1].firstegde=s2;scanf(&i,&j);}}圖的遍歷
深度優先遍歷
深度優先遍歷的思想類似於樹的先序遍歷。其遍歷過程可以描述為：從圖中某個頂點v出發，訪問該頂點，然後依次從v的未被訪問的鄰接點出發繼續深度優先遍歷圖中的其餘頂點，直至圖中所有與v有路徑相通的頂點都被訪問完為止。
深度優先遍歷算法實現：
為了便於在算法中區分頂點是否已被訪問過，需要創建一個一維數組visited[0..n-1]（n是圖中頂點的數目），用來設定訪問標誌，其初始值visited（0≤i≤n-1）為"0"，表示鄰接表中下標值為i的頂點沒有被訪問過，一旦該頂點被訪問，將visited置成"1"。
int visited[0..n-1]={0,0,...0};
void DFS(AdjList adj,int v)
visited[v]=1; visited(adj[v].elem);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) DFS(adj,w->adjvex);
}
對於無向圖，這個算法可以遍歷到v頂點所在的連通分量中的所有頂點，而與v頂點不在一個連通分量中的所有頂點遍歷不到；而對於有向圖可以遍歷到起始頂點v能夠到達的所有頂點。若希望遍歷到圖中的所有頂點，就需要在上述深度優先遍歷算法的基礎上，增加對每個頂點訪問狀態的檢測：
int visited[0..n-1]={0,0,...0};void DFSTraverse(AdjListadj){for(v=0;v<n;v++)if(!visited[v])DFS(adj,v);}廣度優先遍歷
下面我們討論一下實現廣度優先遍歷算法需要考慮的幾個問題：
（1）在廣度優先遍歷中，要求先被訪問的頂點其鄰接點也被優先訪問，因此，必須對每個頂點的訪問順序進行記錄，以便後面按此順序訪問各頂點的鄰接點。應利用一個佇列結構記錄頂點訪問順序，就可以利用佇列結構的操作特點，將訪問的每個頂點入隊，然後，再依次出隊，並訪問它們的鄰接點；
int visited[0..n-1]={0,0,...0};
void BFS(AdjList adj,int v)
InitQueue(Q); //Q是佇列
visited[v]=1; visite(adj[v].elem); EnQueue(Q,v);
while (!QueueEmpty(Q)) {
DeQueue(Q,v);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) {
visited[w->adjvex]=1;
visite(adj[w->adjvex].elem);
EnQueue(Q,w->adjvex); }
}
}
拓撲排序
拓撲排序是有向圖的一個重要操作。在給定的有向圖G中，若頂點序列vi1,vi2,...,vin滿足下列條件：若在有向圖G中從頂點vi到頂點vj有一條路徑，則在序列中頂點vi必在頂點vj之前，便稱這個序列為一個拓撲序列。求一個有向圖拓撲序列的過程稱為拓撲排序。
舉例：計算機專業的學生應該學習的部分課程及其每門課程所需要的先修課程。
拓撲排序的方法：
（1）從圖中選擇一個入度為0的頂點且輸出之；
（2）從圖中刪掉該頂點及其所有以該頂點為弧尾的弧；
下面給出算法實現的基本過程：
{ 將所有入度為0的頂點入棧；
當棧非空時重複執行下列操作：
從棧中退出頂點k；
（1）將k頂點的信息輸出；
（2）將與k鄰接的所有頂點的入度減1。
}
#define MAX_VERTEX_NUM 30//最大頂點個數typedef struct EdgeLinklist{//邊結點int adjvex;struct EdgeLinklist*next;}EdgeLinklist;typedef struct VexLinklist{//頂點結點Elemtype elem;int indegree;//記錄頂點的入度EdgeLinklist* firstedge;}VexLinklist,AdjList[MAX_VERTEX_NUM];下面是拓撲排序的完整算法。
Status TopologicalSort(AdjListadj){InitStack(s);for(i=0;i<MAX_VERTEX_NUM-1;i++)if(adj.indegree==0)Push(s,i);while(!StackEmpty(s)){Pop(s,i);printf(i);for(p=adj.firstedge;p;p=p->next){adj.indegree-=1;if(adj.indegree==0)Push(s,i);}重要的圖
樹
完全圖：每一對不同頂點間都有邊相連的的圖，記作Kn。
二分圖：頂集，且每一條邊都有一個頂點在X中，而另一個頂點在Y中。
完全二分圖：二分圖G中若任意兩個X和Y中的頂點都有邊相連。若，則圖G記作Km,n。
正則圖：如果圖中所有頂點的度皆相等，則此圖稱為正則圖
基本概念
h圖是一個有序對<V，E>，V是結點集，E是邊集，當½V½,½E½有限時，<V,E>稱為有限圖；否則稱無限圖.
h無向邊, 與無序結點(v,u)相關聯的邊；有向邊，與有序結點<v,u>相關聯的邊.
h無向圖，每條邊都是無向邊的圖，記作G=<V,E>; 每條邊都是有向邊的圖，記作D=<V,E>.
h混合圖，既有有向邊，也有無向邊的圖.
h自迴路(環)，關聯於同一個結點的邊.
h無向平行邊，聯結相同兩個結點的多於1條的無向邊；有向平行邊，聯結兩個結點之間的多於1條且方向相同的有向邊.
h簡單圖，不含平行邊和自迴路的圖.
h在有向圖D=<V,E>中，以v(ÎV)為起點的邊之條數為出度deg+(v)；以v(ÎV)為終點的邊之條數為入度deg－(v)..
h最大度數，D(G)=max{d(v)½vÎV}；最小度數，d(G)=min{d(v)½vÎV}
h有n個結點的且每對結點都有邊相連無向簡單圖，無向完全圖Kn. 此時有 ；有n個結點的且每對結點之間都有兩條方向相反的邊相關連的有向簡單圖為有向完全圖，.此時有
h設G=<V,E>, V，E的子集V¢,E¢構成的圖G¢=<V¢,E¢>是圖G的子圖；若G¢ÍG且G¢¹G，(V¢ÌV或E¢ÌE)，G¢是G的真子圖.
h生成子圖，設圖G=<V,E>, 若E¢ÍE, 則圖<.V,E¢>是<V,E>的生成子圖. 即結點與原圖G相同的子圖，為生成子圖.
h補圖`G=<V,E¢>，設G=<V,E>, 以V為結點集，以使G成為完全圖所添加的邊為邊集E¢的圖，就是圖G的補圖G¢,.，即<V,EÈE¢>是完全圖, 其中EÇE¢=Æ.
h圖的同構，設G1=<V1,E1>和G2=<V2,E2>, 存在雙射f：V1®V2，"(vi,vj)ÎE1, 若且唯若 (f(vi),f(vj))ÎE2，且(vi,vj)與 (f(vi),f(vj))的重數相同. 則G1≌G2.
同構充分條件：建立兩個圖的對應關係，這個關係是雙射函式.
同構必要條件：①結點數相同；②邊數相同；③度數相同的結點個數相同.
圖的遍歷
深度優先搜尋法是樹的先根遍歷的推廣，它的基本思想是：從圖G的某個頂點v0齣發，訪問v0，然後選擇一個與v0相鄰且沒被訪問過的頂點vi訪問，再從vi出發選擇一個與vi相鄰且未被訪問的頂點vj進行訪問，依次繼續。如果當前被訪問過的頂點的所有鄰接頂點都已被訪問，則退回到已被訪問的頂點序列中最後一個擁有未被訪問的相鄰頂點的頂點w，從w出發按同樣的方法向前遍歷，直到圖中所有頂點都被訪問。其遞歸算法如下：
Boolean visited[MAX_VERTEX_NUM];//訪問標誌數組Status(*VisitFunc)(intv);//VisitFunc是訪問函式，對圖的每個頂點調用該函式void DFSTraverse(Graph G,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//訪問標誌數組初始化for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);//對尚未訪問的頂點調用DFS}void DFS(Graph G,int v){//從第v個頂點出發遞歸地深度優先遍歷圖Gvisited[v]=TRUE;VisitFunc(v);//訪問第v個頂點for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))//FirstAdjVex返回v的第一個鄰接頂點，若頂點在G中沒有鄰接頂點，則返回空(0)，//若w是v的鄰接頂點，NextAdjVex返回v的（相對於w的）下一個鄰接頂點。//若w是v的最後一個鄰接點，則返回空(0)。if(!visited[w])DFS(G,w);//對v的尚未訪問的鄰接頂點w調用DFS}圖的廣度優先搜尋是樹的按層次遍歷的推廣，它的基本思想是：首先訪問初始點vi，並將其標記為已訪問過，接著訪問vi的所有未被訪問過的鄰接點vi1,vi2, …, vi t，並均標記已訪問過，然後再按照vi1,vi2, …, vi t的次序，訪問每一個頂點的所有未被訪問過的鄰接點，並均標記為已訪問過，依次類推，直到圖中所有和初始點vi有路徑相通的頂點都被訪問過為止。其非遞歸算法如下：
Boolean visited[MAX_VERTEX_NUM];//訪問標誌數組Status(*VisitFunc)(intv);//VisitFunc是訪問函式，對圖的每個頂點調用該函式void BFSTraverse(Graph G,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;v<G.vexnum,++v)visited[v]=FALSE;initQueue(Q);//置空輔助佇列Qfor(v=0;v<G.vexnum;++v)if(!visited[v]){visited[v]=TRUE;VisitFunc(v);EnQueue(Q,v);//v入佇列while(!QueueEmpty(Q)){DeQueue(Q,u);//隊頭元素出隊並置為ufor(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))if(!Visited[w]){//w為u的尚未訪問的鄰接頂點Visited[w]=TRUE;VisitFunc(w);EnQueue(Q,w);}}}}