第6章 圖

本章中介紹下列主要內(nèi)容：
　　 1.圖的定義
　　 2.圖的存儲(chǔ)結(jié)構(gòu)
　　 3.圖的遍歷操作
　　 4.圖的幾個(gè)典型應(yīng)用問(wèn)題
課時(shí)分配：
1、2兩個(gè)學(xué)時(shí),，3兩個(gè)學(xué)時(shí),，4四個(gè)學(xué)時(shí),上機(jī)兩個(gè)學(xué)時(shí)
重點(diǎn)、難點(diǎn)：
圖的遍歷操作,、典型應(yīng)用問(wèn)題

第一節(jié) 圖的定義

1．定義
圖是由結(jié)點(diǎn)的有窮集合V和邊的集合E組成,。其中，為了與樹(shù)形結(jié)構(gòu)加以區(qū)別,，在圖結(jié)構(gòu)中常常將結(jié)點(diǎn)稱為頂點(diǎn),，邊是頂點(diǎn)的有序偶對(duì)，若兩個(gè)頂點(diǎn)之間存在一條邊，就表示這兩個(gè)頂點(diǎn)具有相鄰關(guān)系,。

在上面兩個(gè)圖結(jié)構(gòu)中,，一個(gè)是有向圖，即每條邊都有方向,，另一個(gè)是無(wú)向圖,，即每條邊都沒(méi)有方向。
在有向圖中,，通常將邊稱作弧,，含箭頭的一端稱為弧頭，另一端稱為弧尾,，記作<vi,vj>,，它表示從頂點(diǎn)vi到頂點(diǎn)vj有一條邊。
若有向圖中有n個(gè)頂點(diǎn),，則最多有n(n-1)條弧,，我們又將具有n(n-1)條弧的有向圖稱作有向完全圖。
以頂點(diǎn)v為弧尾的弧的數(shù)目稱作頂點(diǎn)v的出度,，以頂點(diǎn)v為弧頭的弧的數(shù)目稱作頂點(diǎn)v的入度,。
在無(wú)向圖中，邊記作(vi,vj),，它蘊(yùn)涵著存在< vi,vj>和<vj,vi>兩條弧,。若無(wú)向圖中有n個(gè)頂點(diǎn)，則最多有n(n-1)/2條邊,，我們又將具有n(n-1)/2條邊的無(wú)向圖稱作無(wú)向完全圖,。
與頂點(diǎn)v相關(guān)的邊的條數(shù)稱作頂點(diǎn)v的度。 路徑長(zhǎng)度是指路徑上邊或弧的數(shù)目,。
若第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同,，則這條路徑是一條回路。
若路徑中頂點(diǎn)沒(méi)有重復(fù)出現(xiàn),，則稱這條路徑為簡(jiǎn)單路徑,。
在無(wú)向圖中，如果從頂點(diǎn)vi到頂點(diǎn)vj有路徑,，則稱vi和vj連通,。如果圖中任意兩個(gè)頂點(diǎn)之間都連通，則稱該圖為連通圖,，否則,，將其中的極大連通子圖稱為連通分量。
在有向圖中,，如果對(duì)于每一對(duì)頂點(diǎn)vi和vj,，從vi到vj和從vj到vi都有路徑，則稱該圖為強(qiáng)連通圖；否則,，將其中的極大連通子圖稱為強(qiáng)連通分量,。
2．圖的基本操作
基本操作：
（1）創(chuàng)建一個(gè)圖結(jié)構(gòu) CreateGraph(G)
（2）檢索給定頂點(diǎn) LocateVex(G,elem)
（3）獲取圖中某個(gè)頂點(diǎn) GetVex(G,v)
（4）為圖中頂點(diǎn)賦值 PutVex(G,v,value)
（5）返回第一個(gè)鄰接點(diǎn) FirstAdjVex(G,v)
（6）返回下一個(gè)鄰接點(diǎn) NextAdjVex(G,v,w)
（7）插入一個(gè)頂點(diǎn) InsertVex(G,v)
（8）刪除一個(gè)頂點(diǎn) DeleteVex(G,v)
（9）插入一條邊 InsertEdge(G,v,w)
（10）刪除一條邊 DeleteEdge(G,v,w)
（11）遍歷圖 Traverse(G,v)

第二節(jié) 圖的存儲(chǔ)結(jié)構(gòu)

1．鄰接矩陣
1．1 有向圖的鄰接矩陣
具有n個(gè)頂點(diǎn)的有向圖可以用一個(gè)n×n的方形矩陣表示。假設(shè)該矩陣的名稱為M,，則當(dāng)<vi,vj>是該有向圖中的一條弧時(shí),，M[i,j]=1；否則M[i,j]=0,。第i個(gè)頂點(diǎn)的出度為矩陣中第i行中"1"的個(gè)數(shù),；入度為第i列中"1"的個(gè)數(shù),，并且有向圖弧的條數(shù)等于矩陣中"1"的個(gè)數(shù),。
1．2 無(wú)向圖的鄰接矩陣
具有n個(gè)頂點(diǎn)的無(wú)向圖也可以用一個(gè)n×n的方形矩陣表示。假設(shè)該矩陣的名稱為M,，則當(dāng)（vi,vj）是該無(wú)向圖中的一條邊時(shí),，M[i,j]=M[j,i]=1；否則,，M[i,j]=M[j,j]=0,。第i個(gè)頂點(diǎn)的度為矩陣中第i 行中"1"的個(gè)數(shù)或第i列中"1"的個(gè)數(shù)。圖中邊的數(shù)目等于矩陣中"1"的個(gè)數(shù)的一半,，這是因?yàn)槊織l邊在矩陣中描述了兩次

在C 語(yǔ)言中,，實(shí)現(xiàn)鄰接矩陣表示法的類型定義如下所示：
#define MAX_VERTEX_NUM 20
typedef struct graph{
Elemtype elem[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int n;
}Graph;
2． 鄰接表
邊結(jié)點(diǎn)的結(jié)構(gòu)為：

adjvex是該邊或弧依附的頂點(diǎn)在數(shù)組中的下標(biāo)，next是指向下一條邊或弧結(jié)點(diǎn)的指針 ,。

elem是頂點(diǎn)內(nèi)容,，firstedge是指向第一條邊或弧結(jié)點(diǎn)的指針。
在C語(yǔ)言中,，實(shí)現(xiàn)鄰接表表示法的類型定義如下所示：
#define MAX_VERTEX_NUM 30 //最大頂點(diǎn)個(gè)數(shù)
type struct EdgeLinklist{ //邊結(jié)點(diǎn)
int adjvex;
struct EdgeLinklist *next;
}EdgeLinklist;
typedef struct VexLinklist{ //頂點(diǎn)結(jié)點(diǎn)
Elemtype elem;
EdgeLinklist *firstedge;
}VexLinklist,AdjList[MAX_VERTEX_NUM];
創(chuàng)建有向圖和無(wú)向圖鄰接表的算法實(shí)現(xiàn)：
（1） 創(chuàng)建有向圖鄰接表
void Create_adj(AdjList adj, int n)
{
for (i=0;i<n;i++){ //初始化頂點(diǎn)數(shù)組
scanf(&adj[i].elem);
adj[i].firstedge=NULL;
}
scanf(&i,&j); //輸入弧
while (i) {
s=(EdgeLinklist*)malloc(sizeof(EdgeLinklist)); //創(chuàng)建新的弧結(jié)點(diǎn)
s->adgvex=j-1;
s->next=adj[i-1].firstedge; //將新的弧結(jié)點(diǎn)插入到相應(yīng)的位置
adj[i-1].firstegde=s;
scanf(&i,&j); //輸入下一條弧
}
}
（2）創(chuàng)建無(wú)向圖的鄰接表
void Create_adj(AdjList adj, int n)
{
for (i=0;i<n;i++){ //初始化鄰接表
scanf(&adj[i].elem);
adj[i].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);
}
}

第三節(jié) 圖的遍歷

常見(jiàn)的圖遍歷方式有兩種：深度優(yōu)先遍歷和廣度優(yōu)先遍歷,，這兩種遍歷方式對(duì)有向圖和無(wú)向圖均適用。
1． 深度優(yōu)先遍歷
深度優(yōu)先遍歷的思想類似于樹(shù)的先序遍歷,。其遍歷過(guò)程可以描述為：從圖中某個(gè)頂點(diǎn)v出發(fā),，訪問(wèn)該頂點(diǎn)，然后依次從v的未被訪問(wèn)的鄰接點(diǎn)出發(fā)繼續(xù)深度優(yōu)先遍歷圖中的其余頂點(diǎn),，直至圖中所有與v有路徑相通的頂點(diǎn)都被訪問(wèn)完為止,。
下面我們討論一下如何實(shí)現(xiàn)深度優(yōu)先算法。
為了便于在算法中區(qū)分頂點(diǎn)是否已被訪問(wèn)過(guò),，需要?jiǎng)?chuàng)建一個(gè)一維數(shù)組visited[0..n-1]（n是圖中頂點(diǎn)的數(shù)目）,，用來(lái)設(shè)置訪問(wèn)標(biāo)志，其初始值visited[i]（0≤i≤n-1）為"0",，表示鄰接表中下標(biāo)值為i的頂點(diǎn)沒(méi)有被訪問(wèn)過(guò),，一旦該頂點(diǎn)被訪問(wèn)，將visited[i]置成"1"。
int visited[0..n-1]={0,0,...0};
void DFS(AdjList adj,int v)
{//v是遍歷起始點(diǎn)的在鄰接表中的下標(biāo)值,，其下標(biāo)從0開(kāi)始
visited[v]=1; visite(adj[v].elem);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) DFS(adj,w->adjvex);
}
對(duì)于無(wú)向圖,，這個(gè)算法可以遍歷到v頂點(diǎn)所在的連通分量中的所有頂點(diǎn)，而與v頂點(diǎn)不在一個(gè)連通分量中的所有頂點(diǎn)遍歷不到,；而對(duì)于有向圖可以遍歷到起始頂點(diǎn)v能夠到達(dá)的所有頂點(diǎn),。若希望遍歷到圖中的所有頂點(diǎn)，就需要在上述深度優(yōu)先遍歷算法的基礎(chǔ)上,，增加對(duì)每個(gè)頂點(diǎn)訪問(wèn)狀態(tài)的檢測(cè)：
int visited[0..n-1]={0,0,...0};
void DFSTraverse(AdjList adj)
{
for (v=0;v<n;v++) if (!visited[v]) DFS(adj,v);
}
2．廣度優(yōu)先遍歷
對(duì)圖的廣度優(yōu)先遍歷方法描述為：從圖中某個(gè)頂點(diǎn)v出發(fā),，在訪問(wèn)該頂點(diǎn)v之后，依次訪問(wèn)v的所有未被訪問(wèn)過(guò)的鄰接點(diǎn),，然后再訪問(wèn)每個(gè)鄰接點(diǎn)的鄰接點(diǎn),，且訪問(wèn)順序應(yīng)保持先被訪問(wèn)的頂點(diǎn)其鄰接點(diǎn)也優(yōu)先被訪問(wèn)，直到圖中的所有頂點(diǎn)都被訪問(wèn)為止,。下面是對(duì)一個(gè)無(wú)向圖進(jìn)行廣度優(yōu)先遍歷的過(guò)程,。
下面我們討論一下實(shí)現(xiàn)廣度優(yōu)先遍歷算法需要考慮的幾個(gè)問(wèn)題：
（1）在廣度優(yōu)先遍歷中，要求先被訪問(wèn)的頂點(diǎn)其鄰接點(diǎn)也被優(yōu)先訪問(wèn),，因此,，必須對(duì)每個(gè)頂點(diǎn)的訪問(wèn)順序進(jìn)行記錄，以便后面按此順序訪問(wèn)各頂點(diǎn)的鄰接點(diǎn),。應(yīng)利用一個(gè)隊(duì)列結(jié)構(gòu)記錄頂點(diǎn)訪問(wèn)順序,，就可以利用隊(duì)列結(jié)構(gòu)的操作特點(diǎn)，將訪問(wèn)的每個(gè)頂點(diǎn)入隊(duì),，然后,，再依次出隊(duì)，并訪問(wèn)它們的鄰接點(diǎn),；
（2）在廣度優(yōu)先遍歷過(guò)程中同深度優(yōu)先遍歷一樣,，為了避免重復(fù)訪問(wèn)某個(gè)頂點(diǎn)，也需要?jiǎng)?chuàng)建一個(gè)一維數(shù)組visited[0..n-1]（n是圖中頂點(diǎn)的數(shù)目）,，用來(lái)記錄每個(gè)頂點(diǎn)是否已經(jīng)被訪問(wèn)過(guò),。
int visited[0..n-1]={0,0,...0};
void BFS(AdjList adj,int v)
{//v是遍歷起始點(diǎn)在鄰接表中的下標(biāo)，鄰接表中下標(biāo)從0開(kāi)始
InitQueue(Q); //Q是隊(duì)列
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); }
}
}

第四節(jié) 最小生成樹(shù)問(wèn)題

1．圖的生成樹(shù)和森林
對(duì)于一個(gè)擁有n個(gè)頂點(diǎn)的無(wú)向連通圖,，它的邊數(shù)一定多余n-1條,。若從中選擇n-1條邊，使得無(wú)向圖仍然連通,，則由n個(gè)頂點(diǎn)及這 n-1條邊（?。┙M成的圖被稱為原無(wú)向圖的生成樹(shù)。顯示了一個(gè)無(wú)向連通圖的生成樹(shù),，雙線圈表示的頂點(diǎn)為生成樹(shù)的根結(jié)點(diǎn),。

2．最小生成樹(shù)
在一個(gè)圖中,，每條邊或弧可以擁有一個(gè)與之相關(guān)的數(shù)值，我們將它稱為權(quán),。這些權(quán)可以具有一定的含義,，比如，表示一個(gè)頂點(diǎn)到達(dá)另一個(gè)頂點(diǎn)的距離,、所花費(fèi)的時(shí)間,、線路的造價(jià)等等。這種帶權(quán)的圖通常被稱作網(wǎng),。
圖或網(wǎng)的生成樹(shù)不是唯一的,，從不同的頂點(diǎn)出發(fā)可以生成不同的生成樹(shù)，但n個(gè)結(jié)點(diǎn)的生成樹(shù)一定有n-1條邊

下面我們計(jì)算一下上面兩棵生成樹(shù)的權(quán)值之和,。第一棵生成樹(shù)的權(quán)值總和是：16+11+5+6+18=56,；第二棵生成樹(shù)的權(quán)值是：16+19+33+18+6=92。通常我們將權(quán)值總和最小的生成樹(shù)稱為最小生成樹(shù),。
構(gòu)造最小生成樹(shù)的方法：最初生成樹(shù)為空,，即沒(méi)有一個(gè)結(jié)點(diǎn)和一條邊,，首先選擇一個(gè)頂點(diǎn)作為生成樹(shù)的根,，然后每次從不在生成樹(shù)中的邊中選擇一條權(quán)值盡可能小的邊，為了保證加入到生成樹(shù)中的邊不會(huì)造成回路,，與該邊鄰接的兩個(gè)頂點(diǎn)必須一個(gè)已經(jīng)在生成樹(shù)中,，一個(gè)則不在生成樹(shù)中，若網(wǎng)中有n個(gè)頂點(diǎn)（這里考慮的網(wǎng)是一個(gè)連通無(wú)向圖）,，則按這種條件選擇n-1邊就可以得到這個(gè)網(wǎng)的最小生成樹(shù)了,。詳細(xì)的過(guò)程可以描述為：設(shè)置2個(gè)集合，U集合中的元素是在生成樹(shù)中的結(jié)點(diǎn),，V-U集合中的元素是不在生成樹(shù)中的頂點(diǎn),。首先選擇一個(gè)作為生成樹(shù)根結(jié)點(diǎn)的頂點(diǎn)，并將它放入U集合,，然后在那些一端頂點(diǎn)在U集合中,，而另一端頂點(diǎn)在V-U集合中的邊中找一條權(quán)最小的邊，并把這條邊和那個(gè)不在U集合中的頂點(diǎn)加入到生成樹(shù)中,，即輸出這條邊,，然后將其頂點(diǎn)添加到U集合中，重復(fù)這個(gè)操作n-1次,。
下面我們考慮一下如何實(shí)現(xiàn)這個(gè)操作過(guò)程的算法,。
分析 ：（1）它主要有兩項(xiàng)操作：按條件選擇一條邊和將頂點(diǎn)加入到U集合中；（2）網(wǎng)中的每個(gè)頂點(diǎn)不是在U集合中,，就是在V-U集合中,。為了提高算法的時(shí)間,、空間效率，我們將為這個(gè)算法設(shè)計(jì)一個(gè)輔助數(shù)組closedge,，用來(lái)記錄從集合U到集合V-U具有最小權(quán)值的邊,。對(duì)每個(gè)屬于V-U集合的頂點(diǎn)，在輔助數(shù)組中存在一個(gè)相應(yīng)的分量closedge[i-1],，它包括兩個(gè)域,，一個(gè)域用來(lái)表示在該頂點(diǎn)與V-U集合中某些頂點(diǎn)構(gòu)成的邊中權(quán)最小的那條邊的權(quán)值，若該頂點(diǎn)進(jìn)入U集合,，則值為0,；另一個(gè)域表示這條最小權(quán)值的邊對(duì)應(yīng)的在V-U集合中的頂點(diǎn)下標(biāo)。其類型定義如下所示：
#define MAX_NUM 10
struct {
int adjvex;
float lowcist;
}closedge[MAX_NUM];
整個(gè)算法的執(zhí)行過(guò)程可以描述為：
{ 初始化closedge數(shù)組的內(nèi)容,；
選擇某個(gè)頂點(diǎn)k作為生成樹(shù)的根結(jié)點(diǎn),，并將它加入到U集合中；
重復(fù)下列操作n-1次：
①選擇一條滿足條件的邊,；
②輸出這條邊的兩個(gè)端點(diǎn),；
③修改V-U集合中的頂點(diǎn)信息，即與U集合中構(gòu)成最小權(quán)值的邊,。
}
假設(shè)該網(wǎng)以鄰接矩陣的形式給出,，則完整的算法為：
void Mini_SpanTree(Graph G,int k,int n)
{//G是網(wǎng)的鄰接矩陣，k是生成樹(shù)根結(jié)點(diǎn)的序號(hào),，n是網(wǎng)的頂點(diǎn)數(shù)目
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; //將頂點(diǎn)加入U集合中
for (j=0;j<n;j++)
if (closedge[i]&&G[k][j]<closedge[j].lowcost)
closedge[j]={k,G[k][j]};
}
}

第五節(jié) 拓?fù)渑判騿?wèn)題

拓?fù)渑判蚴怯邢驁D的一個(gè)重要操作,。在給定的有向圖G中，若頂點(diǎn)序列vi1,vi2,...,vin滿足下列條件：若在有向圖G中從頂點(diǎn)vi到頂點(diǎn)vj有一條路徑,，則在序列中頂點(diǎn)vi必在頂點(diǎn)vj之前,，便稱這個(gè)序列為一個(gè)拓?fù)湫蛄小Ｇ笠粋€(gè)有向圖拓?fù)湫蛄械倪^(guò)程稱為拓?fù)渑判颉?/SPAN>
舉例：計(jì)算機(jī)專業(yè)的學(xué)生應(yīng)該學(xué)習(xí)的部分課程及其每門(mén)課程所需要的先修課程,。

拓?fù)渑判虻姆椒ǎ?/SPAN>
（1）從圖中選擇一個(gè)入度為0的頂點(diǎn)且輸出之,；
（2）從圖中刪掉該頂點(diǎn)及其所有以該頂點(diǎn)為弧尾的弧,；
反復(fù)執(zhí)行這兩個(gè)步驟,，直到所有的頂點(diǎn)都被輸出，輸出的序列就是這個(gè)無(wú)環(huán)有向圖的拓?fù)湫蛄?。?xì)心的讀者可能會(huì)發(fā)現(xiàn)：在每一時(shí)刻,，可能同時(shí)存在多個(gè)入度為0的頂點(diǎn)，選擇注：表中c1~c9列表示的是每個(gè)頂點(diǎn)的入度,。
下面我們討論一下如何實(shí)現(xiàn)拓?fù)渑判虻乃惴?。假設(shè)有向圖以鄰接表的形式存儲(chǔ)。
下面給出算法實(shí)現(xiàn)的基本過(guò)程：
{ 將所有入度為0的頂點(diǎn)入棧,；
當(dāng)棧非空時(shí)重復(fù)執(zhí)行下列操作：
從棧中退出頂點(diǎn)k,；
（1）將k頂點(diǎn)的信息輸出,；
（2）將與k鄰接的所有頂點(diǎn)的入度減1。
}
#define MAX_VERTEX_NUM 30 //最大頂點(diǎn)個(gè)數(shù)
type struct EdgeLinklist{ //邊結(jié)點(diǎn)
int adjvex;
struct EdgeLinklist *next;
}EdgeLinklist;
typedef struct VexLinklist{ //頂點(diǎn)結(jié)點(diǎn)
Elemtype elem;
int indegree; //記錄頂點(diǎn)的入度
EdgeLinklist *firstedge;
}VexLinklist,AdjList[MAX_VERTEX_NUM];
下面是拓?fù)渑判虻耐暾惴ā?/SPAN>
Status TopologicalSort(AdjList adj)
{
InitStack(s);
for (i=0;i<MAX_VERTEX_NUM-1;i++)
if (adj[i].indegree==0) Push(s,i);
while (!StackEmpty(s)) {
Pop(s,i); printf(i);
for (p=adj[i].firstedge;p;p=p->next) {
adj[i].indegree-=1;
if (adj[i].indegree==0) Push(s,i);
}
}
}