第7章 數(shù)據(jù)結(jié)構(gòu)（Ｃ＋＋版）2圖

第7章圖第2講第6章樹與二叉樹1本章分為（4～5）講第1講

7.1

圖的基本概念

7.2

圖的存儲結(jié)構(gòu)-7.2.1第3講

7.4圖的最小生成樹7.5最短路徑第2講

7.4圖的存儲結(jié)構(gòu)-7.2.2,7.2.3,7.2.4

7.3圖的遍歷與連通性

第4講7.6拓?fù)渑判蚺c關(guān)鍵路徑題小結(jié)

供教師參考27.2.2圖的鄰接鏈表（AdjacencyList）

鄰接鏈表由表頭向量和邊鏈表兩部分組成。也稱鄰接表。

邊鏈表：每一頂點都建立一單鏈表。將同一頂點發(fā)出的邊結(jié)點鏈接成一個單鏈表。每個結(jié)點表示依附該頂點的一條邊。

表頭向量：是一個順序結(jié)構(gòu)，每個數(shù)據(jù)元素對應(yīng)一個頂點的信息。每個數(shù)據(jù)元素的結(jié)點就是每一單鏈表的頭結(jié)點。它存放頂點信息data和依附于它的某邊結(jié)點地址adj?？梢噪S機訪問任一頂點的邊鏈表。3圖的鄰接鏈表4無向圖的鄰接鏈表

由于該圖的邊上不帶權(quán)值，因此邊結(jié)點的weight域空閑。第一行的鏈表有3個邊結(jié)點，表示從v1分別到v2、v3和v4有3條邊，其邊結(jié)點個數(shù)是頂點v1的度數(shù)。鄰接鏈表中邊結(jié)點的數(shù)等于總邊數(shù)的兩倍。5有向圖的鄰接鏈表

每行是代表弧的鏈表。第一行的鏈表有2個弧結(jié)點，表示從v1分別到v2、v3有2條弧，弧結(jié)點個數(shù)是頂點v1的出度數(shù)。鄰接鏈表中弧結(jié)點的數(shù)目等于圖中弧的總條數(shù)。該結(jié)構(gòu)圖沒有直接反映出頂點的入度。這是有向圖的正鄰接鏈表，還可畫出有向圖的逆鄰接鏈表。6constint

MaxVertices=100;typedef

int

VerT; typedef

int

DistT;structitem

{VerTdata; //頂點數(shù)據(jù)

Edge*adj;//鄰接表針指

};itemVertices[MaxVertices];//表頭向量頭結(jié)點（頂點信息）結(jié)構(gòu)和表頭向量：7構(gòu)成鏈表的邊結(jié)點結(jié)構(gòu)：structEdge{int

dest; //鄰接頂點下標(biāo)

DistTweight; //邊的權(quán)值，或更多

Edge*next; //指針

};

為了突出基本原理，邊結(jié)點信息比較簡單：鄰接頂點的編號；出發(fā)點到本頂點的邊的權(quán)值；指向下一條邊結(jié)點（有共同出發(fā)頂點的邊）的指針域。87.2.4圖的鄰接鏈表類

表頭向量用一維數(shù)組Vertices[]來表示。每個數(shù)組元素除了包含頂點的信息data外，還包含一個指針域adj。用adj

連接以該頂點發(fā)出的邊結(jié)點，形成一條鏈表。邊（或弧）信息在邊結(jié)點中，鏈表中的每個結(jié)點表示一條依附該頂點的邊（或?。?。

一個表頭向量和各個頂點的外接鏈表共同構(gòu)成圖的鄰接鏈表。9classAdjTWGraph //鄰接表圖類定義

{private:itemVertices[MaxVertices]; //表頭向量

int

numV; //當(dāng)前頂點個數(shù)

int

numE; //當(dāng)前邊的條數(shù)

public:AdjTWGraph(); //構(gòu)造函數(shù)～AdjTWGraph(); //析構(gòu)函數(shù)

voidCreatG(int

n,inte);//輸入建立鄰接表

voidPrintOut(); //輸出數(shù)據(jù)信息

voidDepthFirst() //調(diào)用深度優(yōu)先遍歷

{//…….}voidBroadFirst() //調(diào)用廣度優(yōu)先遍歷

{//……}10private://對連通圖從頂點v開始深度優(yōu)先遍歷，

//visit為訪問標(biāo)記

voidDepthFirst(intv,intvisited[]);//對連通圖從頂點v開始廣度優(yōu)先遍歷，

//visit為訪問標(biāo)記

voidBroadFirst(intv,intvisited[]);};11（1）構(gòu)造函數(shù)AdjTWGraph::AdjTWGraph()//初始化空圖

{for(inti=0;i<MaxVertices;i++){Vertices[i].data=0;

Vertices[i].adj=NULL; //指針域置空

}

numV=0;

numE=0;}12用來釋放動態(tài)建立的邊鏈表存儲空間。AdjTWGraph::～AdjTWGraph(void){for(inti=0;i<numV;i++){Edge*p=Vertices[i].adj,*q;while(p!=NULL){q=p->next;deletep;p=q;}

Vertices[i].adj=NULL;}}（2）析構(gòu)函數(shù)13voidAdjTWGraph::CreatG(int

n,inte){int

vi,vj;DistTw;

numE=e;numV=n;

cout<<"\n輸入頂點的信息（整型）：";for(inti=0;i<numV;i++){cout<<"\n"<<i+1<<":";

cin>>Vertices[i].data;}………;

（3）建立圖的鄰接表函數(shù)教師結(jié)合教材閱讀本函數(shù)，目的是學(xué)生會用。14（4）輸出圖的鄰接表信息voidAdjTWGraph::PrintOut(){Edge*pre,*curr;for(inti=0;i<numV;i++){cout<<"\n頂點編號、它的鄰接點編號和邊的權(quán)值：";

cout<<""<<i+1<<""<<Vertices[i].data;

curr=Vertices[i].adj; //找頂點vi的鄰接邊

while(curr!=NULL){cout<<"v"<<curr->dest<<"w"<<curr->weight;

curr=curr->next;}

cout<<endl;}//for}15有向圖的正鄰接表在無向圖的鄰接表中，求頂點v的度比較方便，只要遍歷第v條鏈表，統(tǒng)計該鏈表中邊結(jié)點的個數(shù)便可得到頂點v的度。有向圖的正鄰接表中，第v條鏈表是由以頂點v為弧尾的若干條弧的弧結(jié)點組成，每個弧結(jié)點的dest域是該條弧的弧頭結(jié)點在圖中的位置（頂點在數(shù)組中的下標(biāo)）。第v條鏈表中弧結(jié)點的個數(shù)就是頂點v的出度。16有向圖的逆鄰接表

為了便于確定頂點v的入度或以v為頭的弧的條數(shù)，可建立圖的逆鄰接表。單鏈表中弧結(jié)點代表以v為頭的若干條弧，弧結(jié)點中的dest域存放該條弧的弧尾結(jié)點在圖中的位置（頂點在數(shù)組中的下標(biāo)）。第v條鏈表中弧結(jié)點的個數(shù)就是頂點v的入度。177.3圖的遍歷與圖的連通性圖的遍歷（GraphTraversal）是圖問題中最基本和最重要的操作。該操作，是訪問圖中的每一個頂點且每個頂點僅被訪問一次。圖的遍歷方法有兩種：一種是深度優(yōu)先搜索遍歷，簡稱DFS（DepthFirstSearch）算法；另一種是廣度優(yōu)先搜索遍歷，簡稱BFS（BroadFirstSearch）算法。圖的深度優(yōu)先搜索遍歷類同于樹的先根遍歷，而圖的廣度優(yōu)先遍歷類同于樹的層序遍歷。187.3圖的遍歷與圖的連通性圖的遍歷算法設(shè)計需要考慮3個問題。（1）圖的頂點沒有首尾之分，所以算法的參數(shù)要指定訪問的第一個頂點。（2）對圖的遍歷路徑有可能構(gòu)成一個回路，從而造成死循環(huán)，所以算法設(shè)計要考慮遍歷路徑可能的回路問題。（3）一個頂點可能和若干個頂點都是相鄰頂點，要使一個頂點的所有相鄰頂點按照某種次序被訪問。197.3圖的遍歷與圖的連通性對于連通圖，從初始頂點出發(fā)一定存在路徑和圖中的所有其他頂點相連，所以從初始頂點出發(fā)一定可以遍歷該圖。對于非連通圖，從某一初始頂點出發(fā)只能訪問到該頂點所屬的連通子圖的所有頂點。如果要對整個非連通圖實現(xiàn)遍歷，還需找未被訪問過的其他頂點繼續(xù)處理，直至所有頂點全被訪問到為止。207.3.1圖的深度優(yōu)先遍歷圖的深度優(yōu)先遍歷DFS算法是沿著某初始頂點出發(fā)的一條路徑，盡可能深入地前進(jìn)，即每次在訪問完當(dāng)前頂點后，首先訪問當(dāng)前頂點的一個未被訪問過的鄰接頂點，然后去訪問這個鄰接點的一個未被訪問過的鄰接點，這是一個遞歸算法。21對于連通圖的深度優(yōu)先遍歷DFS思想如下：（1）訪問初始頂點v并標(biāo)記頂點v已訪問。（2）查找頂點v的第一個鄰接頂點w。（3）若v的鄰接頂點w存在，則繼續(xù)向下執(zhí)行；否則回朔到v，再找v的另一個未被訪問過的鄰接點。（4）若頂點w未被訪問，則訪問頂點w并標(biāo)記頂點w為已訪問。（5）繼續(xù)查找頂點w的下一個鄰接頂點wi，讓v取值w再讓w取值wi轉(zhuǎn)到步驟（3）。直到圖中所有頂點全部訪問過為止。22圖的深度優(yōu)先遍歷示例假定v1是出發(fā)頂點，首先訪問v1。然后依次v2、v4、v8、v5。由于與v5相鄰的頂點均已被訪問過，搜索回退到v8。連續(xù)退回到v4、v2最后退回到v1。選擇v1的未被訪問過的鄰接點v3，繼續(xù)往下搜索，依次訪問v3、v6、v7。

由于v7的所有鄰接點被訪問過，所以連續(xù)地退回到v7、v6、v3最后退回到v1。這時v1的所有鄰接點全被訪問過，從而遍歷了圖中全部頂點。頂點的訪問序列為：

V1→V2→V4→V8→V5→V3→V6→V7遍歷圖的過程實質(zhì)上是對每個頂點搜索其鄰接點的過程。教師應(yīng)該對圖細(xì)講，少播放文字。231．圖的鄰接矩陣的深度優(yōu)先遍歷-算法7.1voidAdjMWGraph::Depth(int

v,intvisited[]){cout<<"\n頂點"<<v+1<<"權(quán)值："<<Vertices[v]; //訪問頂點v

visited[v]=1; //標(biāo)記頂點v已訪問

for(int

col=0;col<numV;col++){if(Edge[v][col]==0||Edge[v][col]==MaxWeight)continue; //找v一個鄰接點colif(!visited[col])Depth(col,visited);//調(diào)用深度遞歸遍歷

}}

算法搜索一個頂點的所有鄰接點花費時間約為O(n)。從n個頂點出發(fā)搜索的時間為O(n2)，DFS算法時間復(fù)雜度是O(n2)。242．圖的鄰接表的深度優(yōu)先遍歷-算法7.2voidAdjTWGraph::DepthFirst(intv,intvisited[]){int

vj;Edge*p;

cout<<Vertices[v].data<<""; //訪問頂點v

visited[v]=1;p=Vertices[v].adj;//取v的鄰接邊結(jié)點

while(p!=NULL){vj=p->dest;//取v的鄰接點編號

if(visited[vj]==0)DepthFirst(vj,visited);//遞歸調(diào)用

p=p->next;//取下一個鄰接邊結(jié)點

}}25深度優(yōu)先遍歷的算法分析：

以鄰接矩陣為存儲結(jié)構(gòu)的DFS算法，搜索一個頂點的所有鄰接點花費時間約為O(n)。從n個頂點出發(fā)搜索的時間為O(n2)，時間復(fù)雜度是O(n2)。以鄰接鏈表為存儲結(jié)構(gòu)的DFS算法，訪問表頭向量時間為O(n)。而外接的邊結(jié)點無向圖為2e（e為圖的邊數(shù)）個，有向圖為e個，時間消耗約為O(e)。算法的時間復(fù)雜度為O(n+e)。邊數(shù)很少的圖適合采用鄰接表存儲結(jié)構(gòu)。267.3.2圖的廣度優(yōu)先遍歷

BFS算法是一個按層搜索的過程，和樹的按層遍歷算法類似，它也需要一個隊列以保持遍歷時已訪問過的頂點的順序，以便按出隊的順序再去訪問這些頂點的鄰接頂點。27圖的廣度優(yōu)先遍歷BFS思想如下：（1）始發(fā)頂點v入隊列。（2）當(dāng)隊列非空則繼續(xù)向下執(zhí)行，否則算法結(jié)束。（3）出隊列得頂點v，訪問頂點v并設(shè)訪問標(biāo)志。（4）查找頂點v的第一個鄰接頂點col。（5）若v的鄰接頂點col未被訪問過，則col入隊列。（6）繼續(xù)查找頂點v的另一個新的鄰接頂點col，轉(zhuǎn)到步驟（5），直到頂點v的所有未被訪問過的鄰接點處理完。然后轉(zhuǎn)到步驟（2）。28圖的深度優(yōu)先遍歷示例

首先從起點v1出發(fā)，訪問v1。得到的頂點訪問序列為：

V1→V2→V4→V5→V6→V7→V8

在廣度過優(yōu)先搜索中，若對x的訪問先于y，則對x鄰接點的訪問也先于對y鄰接點的訪問。因此，可采用隊列來暫存那些剛出隊被訪問過的頂點的未被訪問過的鄰接點。教師應(yīng)該對圖細(xì)講，少播放文字。291．圖的鄰接矩陣的廣度優(yōu)先遍歷-算法7.3voidAdjMWGraph::Broad(int

v,intvisited[]){SqQueue<int>q; //聲明隊列對象q

cout<<endl<<"\n頂點"<<v+1<<"權(quán)值："<<Vertices[v]; //訪問頂點v

visited[v]=1; //標(biāo)記v已訪問

q.EnQueue(v); //頂點v進(jìn)隊

while(!q.IsEmpty()) //隊列非空時循環(huán)

{v=q.DeQueue(); //出隊得頂點v

30

for(int

col=0;col<numV;col++) //找v的鄰接點

if(Edge[v][col]>0&&Edge[v][col]<MaxWeight&&visited[col]==0){cout<<endl<<"\n頂點"<<col+1<<"權(quán)值：“

<<Vertices[col];//訪問頂點col

visited[col]=1; //標(biāo)記col

已訪問

q.EnQueue(col); //滿足條件的鄰接點col

進(jìn)隊

}}//whileq

cout<<"\nend!"<<endl;}

分析上述過程，每個頂點都會進(jìn)一次隊列，所以算法BFS的外循環(huán)次數(shù)為n次、而內(nèi)循環(huán)次數(shù)平均均為n次，故上述BFS算法的時間復(fù)雜度為O(n2)。312．圖的鄰接表的廣度優(yōu)先遍歷-算法7.4voidAdjTWGraph::BroadFirst(intv,intvisited[]){int

vj;Edge*p;

SqQueue<int>Q;

cout<<Vertices[v].data<<"";visited[v]=1; //訪問且標(biāo)記v

Q.EnQueue(v); //v入隊

while(!Q.IsEmpty()) //隊列不空，循環(huán)

{v=Q.DeQueue(); //出隊并且訪問頂點vp=Vertices[v].adj; //取v的鄰接邊結(jié)點

32

while(p!=NULL){vj=p->dest; //取v的鄰接點vj

if(visited[vj]==0){cout<<Vertices[vj].data<<"";visited[vj]=1; //訪問且標(biāo)記vj

Q.EnQueue(vj); //vj入隊

}p=p->next; //取下一個鄰接邊結(jié)點

}//whilep}//whileQ

cout<<"\nend!"<<endl;}33廣度優(yōu)先遍歷算法分析采用鄰接鏈表存儲結(jié)構(gòu)，BFS算法的時間復(fù)雜度為O(n2)。采用鄰接鏈表存儲結(jié)構(gòu)，廣度優(yōu)先搜索遍歷圖的時間復(fù)雜度與深度優(yōu)先遍歷是相同的，其時間復(fù)雜度也是O(n+e)。圖的廣度優(yōu)先遍歷，不論圖選用何種存儲結(jié)構(gòu)都會用到輔助存儲隊列。為什么頂點的訪問是在入隊時進(jìn)行，能否考慮將訪問放在出隊時進(jìn)行呢？347.3.3非連通圖和連通分量對于連通圖，從圖的任意一個頂點開始深度或廣度優(yōu)先遍歷一定可以訪問圖中的所有頂點。但對于非連通圖，從圖的任意一個頂點開始遍歷并不能訪問圖中的所有頂點。對于非連通圖，從任意一個頂點開始深度或廣度優(yōu)先遍歷只能訪問包括該首頂點的連通分量中的所有頂點。當(dāng)把每一個頂點都作為一次首頂點深度或廣度優(yōu)先遍歷非連通圖，并根據(jù)頂點的訪問標(biāo)記來判斷是否需要訪問該頂點時，就一定可以訪問該非連通圖中的所有頂