數(shù)據(jù)結構課件第七章圖第1頁，課件共76頁，創(chuàng)作于2023年2月7.1圖的定義和術語1．圖的定義定義：圖（Graph）是由非空的頂點集合和一個描述頂點之間關系（邊或者?。┑募辖M成。其二元組定義為：

G＝（V，E）

V＝{vi|vi∈DataObject} E＝{(vi,vj)|vi,vj∈V且P(vi,vj)}其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。集合E可以是空集，若E為空，則該圖只有頂點而沒有邊。

第2頁，課件共76頁，創(chuàng)作于2023年2月圖的應用舉例例1交通圖（公路、鐵路）

頂點：地點

邊：連接地點的公路例2電路圖

頂點：元件

邊：連接元件之間的線路例3各種流程圖如產(chǎn)品的生產(chǎn)流程圖

頂點：工序

邊：各道工序之間的順序關系V0V4V3V1V2V0V2V3V1第3頁，課件共76頁，創(chuàng)作于2023年2月2．圖的相關術語有向圖和無向圖

在圖中，若用箭頭標明了邊是有方向性的，則稱這樣的圖為有向圖，否則稱為無向圖。在無向圖中，一條邊（x,y）與（y,x）表示的結果相同，用圓括號表示。例如：G1=(V1,E1)

其中：V1={v0,v1,v2,v3,v4}

E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3),(v2,v4)}無序對(vi,vj)：用連接頂點vi、vj的線段表示，稱為無向邊；無向圖G1V0V4V3V1V2第4頁，課件共76頁，創(chuàng)作于2023年2月在有向圖中，一條邊<x,y>與<y,x>表示的結果不相同，用尖括號表示。<x,y>表示從頂點x出發(fā)向頂點y的邊，x為始點，y為終點，有向邊也稱為弧，x為弧尾，y為弧頭,則<x,y>表示為一條弧,而<y,x>表示y為弧尾，x為弧頭的另一條弧。

例如：G2=(V2,E2)其中：V2={v0,v1,v2,v3}E2={<v0,v1>,<v0,v2>,<v2,v3>,<v3,v0>}有向圖G2V0V2V3V1有序對<vi,vj>：用以vi為起點、以vj為終點的有向線段表示，稱為有向邊或弧；在圖G中，若所有邊都是無向邊，則稱G為無向圖；在圖G中，若所有邊都是有向邊，則稱G為有向圖；在圖G中，既有無向邊又有有向邊，則稱G為混合圖；第5頁，課件共76頁，創(chuàng)作于2023年2月

頂點、邊、弧、弧頭、弧尾圖中的數(shù)據(jù)元素vi稱為頂點(Vertex)；P(vi,vj)表示在頂點vi和頂點vj之間有一條直接連線。如果是在無向圖中，則稱這條連線為邊(edge)；邊用頂點的無序偶對(vi,vj)來表示，稱頂點vi和頂點vj互為鄰接點，邊(vi,vj)依附于頂點vi與頂點vj。在有向圖中，用有序偶對<vi,vj>表示從頂點vi出發(fā)向頂點vj的邊，vi為始點，vj為終點。有向邊也稱為弧(arc)，vi為弧尾(tail)或初始點，vj為弧頭(head)或終端點,則<vi,vj>表示為一條弧,而<vj,vi>表示vj為弧尾、vi為弧頭的另一條弧。ViVjViVj無向圖有向圖第6頁，課件共76頁，創(chuàng)作于2023年2月

端點和鄰接點

在一個無向圖中,若存在一條邊(vi,vj),則稱vi和vj為此邊的兩個端點,并稱它們互為鄰接點(adjacent).

在一個有向圖中,若存在一條弧<vi,vj>,則稱vi和vj為此弧的初始點和終端點,稱它們互為鄰接點，稱vj為vi得出邊鄰接點,vi為vj的入邊鄰接點.G2G17126543523641第7頁，課件共76頁，創(chuàng)作于2023年2月

完全圖、稠密圖、稀疏圖無向完全圖：在一個無向圖中，如果任意兩頂點都有一條直接邊相連接，則稱該圖為無向完全圖。在一個含有n個頂點的無向完全圖中，有n(n-1)/2條邊。有向完全圖：在一個有向圖中，如果任意兩頂點之間都有方向互為相反的兩條弧相連接，則稱該圖為有向完全圖。在一個含有n個頂點的有向完全圖中，有n(n-1)條弧。

稠密圖、稀疏圖：若一個圖接近完全圖，稱為稠密圖；稱邊數(shù)很少的圖為稀疏圖。

有向完全圖無向完全圖312312第8頁，課件共76頁，創(chuàng)作于2023年2月G2頂點2入度：1出度：3頂點4入度：1出度：0G1頂點5的度：3頂點2的度：47126543523641

度、入度、出度

在圖中，一個頂點依附的邊或弧的數(shù)目，稱為該頂點的度。在有向圖中，以頂點V為起點的有向邊數(shù)稱為頂點V的出度(Outdegree)，以頂點V為終點的有向邊數(shù)稱為頂點V的入度(Indegree)，有向圖中某個頂點的入度和出度之和稱為該頂點的度。第9頁，課件共76頁，創(chuàng)作于2023年2月設圖G的頂點數(shù)為n，邊或弧數(shù)為e。則圖中所有頂點的度數(shù)和=2*e。（每條邊對圖的所有頂點的度數(shù)都“貢獻”2度）

G2G17126543523641ri

為入度，

ci為出度在有向圖中，所有頂點的入度之和等于出度之和：第10頁，課件共76頁，創(chuàng)作于2023年2月

邊的權、網(wǎng)

與邊有關的數(shù)據(jù)信息稱為權（weight），權可以代表一個頂點到另一個頂點的距離，耗費等。邊上帶權的圖稱為網(wǎng)（network）。

1254317632458BCA21435無向帶權圖和有向帶權圖

(a)無向網(wǎng)(b)有向網(wǎng)第11頁，課件共76頁，創(chuàng)作于2023年2月

路徑、路徑長度在無向圖中，若存在一個頂點序列vp,vi1,vi2,…,vim,vq使得(vp,vi1),(vi1,vi2),…,(vim,vq)都屬于E(G)，則稱其為頂點vp到頂點vq之間的一條路徑（Path）。路徑上邊的數(shù)目稱為路徑長度（Pathlength）。在有向圖中，路徑也是有向的，它是由若干條弧組成。如圖所示的無向圖G1中，v0→v3→v2→v4與v0→v1→v4是從頂點v0到頂點v4的兩條路徑，路徑長度分別為3和2。V0V4V3V1V2V0V1G1第12頁，課件共76頁，創(chuàng)作于2023年2月

回路、簡單路徑、簡單回路

起點和終點相同的路徑稱為回路或者環(huán)（Cycle）。序列中頂點不重復出現(xiàn)的路徑稱為簡單路徑。除第一個頂點與最后一個頂點之外，其他頂點不重復出現(xiàn)的回路稱為簡單回路。在圖G1中，V0,V1,V2,V3是簡單路徑；V0,V1,V2,V4,V1不是簡單路徑；在圖G2中，V0,V2,V3,V0是簡單回路；V0V4V3V1V2V0V2V3V1無向圖G1有向圖G2第13頁，課件共76頁，創(chuàng)作于2023年2月

子圖

若有兩個圖G和G'，G=(V,E)，G'=(V',E')，滿足如下條件：V'V，E'E，即V'為V的子集，E'為E的子集，稱圖G'為圖G的子圖（Subgraph）。例：(b)是(a)的子圖，(c)圖不是（a）的子圖。V0V4V3V1V2V0V4V3V1V2V0V3V1(a)(b)(c)第14頁，課件共76頁，創(chuàng)作于2023年2月

連通圖、連通分量

在無向圖中，如果從一個頂點vi到另一個頂點vj（i≠j）有路徑，則稱頂點vi和vj是連通的。若圖中任意兩個頂點都是連通的，則稱此無向圖為連通圖（ConnectedGraph），否則稱為非連通圖。

無向圖中，極大的連通子圖為該圖的連通分量。顯然，任何連通圖的連通分量只有一個，即它本身，而非連通圖有多個連通分量。

V0

V4

V3

V1

V2

V0

V2

V3

V1

V5

V4連通圖G1非連通圖G2G2的兩個連通分量第15頁，課件共76頁，創(chuàng)作于2023年2月

強連通圖、強連通分量

對于有向圖來說，若圖中任意一對頂點vi和vj（i≠j）均有從一個頂點vi到另一個頂點vj的路徑，也有從vj到vi的路徑，則稱該有向圖是強連通圖。有向圖的極大強連通子圖稱為強連通分量。顯然，任何強連通圖的強連通分量只有一個，即它本身，而非強連通圖有多個強連通分量。

V0

V1

V2

V3

V0

V1

V2

V3強連通圖G1非強連通圖G2

V1

V0

V2

V3G2的兩個強連通分量第16頁，課件共76頁，創(chuàng)作于2023年2月

生成樹、生成森林所謂連通圖G的生成樹，是G的包含其全部n個頂點，且以最少的邊數(shù)使其連通的一個極小連通子圖。它必定包含且僅包含G的n-1條邊。

極小連通子圖意思是：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。非連通圖的生成樹則組成一個生成森林。若圖中有n個頂點，m個連通分量，則生成森林中有n-m條邊。

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2連通圖G1G1的生成樹第17頁，課件共76頁，創(chuàng)作于2023年2月G2G15426311732465路徑：1，2，3，5，6，3路徑長度：5簡單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡單回路：3，5，6，3路徑：1，2，5，7，6，5，2，3路徑長度：7簡單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡單回路：1，2，3，1第18頁，課件共76頁，創(chuàng)作于2023年2月3、圖的運算和其它結構一樣，圖的基本操作也是查找、插入和刪除。但在操作中常常需要指出頂點在圖中位置。從圖的邏輯結構的定義來看，圖中的頂點之間不存在全序的關系（即無法將圖中頂點排列成一個線性序列），任何一個頂點都可被看成是第一個；另一方面，任一頂點的鄰接點之間也不存在次序關系。但為了操作方便，我們需要將圖中頂點按任意的順序排列起來（這個排列和關系E無關）。由此，所謂頂點在圖中的位置指的是該頂點在這個人為的隨意排列中的位置（或序號）。同理可對某個頂點的所有鄰接點進行排隊，在這個排隊中自然形成了第1個或第k個鄰接點。若某個頂點的鄰接點的個數(shù)大于k則稱第k＋1個鄰接點為第k個鄰接點的下一個鄰接點，而最后一個鄰接點的下一個鄰接點為“空”。第19頁，課件共76頁，創(chuàng)作于2023年2月圖的基本操作1、CreatGraph(&G,V,E)

按V和E的定義構造圖G。2、DestroyGraph(&G)銷毀圖G。3、LocateVex(G,u)

若G中存在頂點u，返回其在圖中位置，否則返回-1。4、GetVex(G,v)在圖中找到頂點v，并返回頂點v的相關信息，否則返回空。5、FirstAdjVex(G,v)

返回圖中頂點v的第一個鄰接頂點，若沒有，返回空。6、NextAdjVex(G，v，w)

返回v的相對于w的下一個鄰接頂點，若w是v的最后一個鄰接點，則返回空。第20頁，課件共76頁，創(chuàng)作于2023年2月7、AddVex(&G,v)

在圖G中增添新頂點v。8、DelVex(&G,v)

在圖G中，刪除頂點v及所有和其相關的邊或弧。9、

AddArc(&G,v,w)

在圖G中增添一條從頂點v到頂點w的邊或弧。10、DelArc(&G,v,w)

在圖中刪除一條從頂點v到頂點w的邊或弧。11、DFS(G,v)

在圖G中，從頂點v出發(fā)深度優(yōu)先遍歷圖。12、BFS(G,v)

在圖G中，從頂點v出發(fā)廣度優(yōu)先遍歷圖。圖的基本操作第21頁，課件共76頁，創(chuàng)作于2023年2月7.2圖的存儲結構圖是一種結構復雜的數(shù)據(jù)結構，表現(xiàn)在不僅各個頂點的度可以千差萬別，而且頂點之間的邏輯關系也錯綜復雜。從圖的定義可知，一個圖的信息包括兩部分，即圖中頂點的信息以及描述頂點之間的關系（邊或者?。┑男畔?。因此無論采用什么方法建立圖的存儲結構，都要完整、準確地反映這兩方面的信息。圖通常有鄰接矩陣、鄰接表、鄰接多重表和十字鏈表等表示方法。第22頁，課件共76頁，創(chuàng)作于2023年2月7.2.1鄰接矩陣

定義：在鄰接矩陣表示中，除了用一維數(shù)組存放頂點本身信息外，還用一個矩陣表示各個頂點之間的鄰接關系。這個矩陣稱為鄰接矩陣。

假設圖G＝(V,E)有n個確定的頂點，即V＝{v0,v1,…,vn-1}，則表示G中各頂點相鄰關系為一個n×n的矩陣，矩陣的元素為：

1

若（i,j）∈E(G)或〈i,j〉∈E(G) 0其它情形

若G是帶權圖，則鄰接矩陣定義為：

wij

若（i,j）∈E(G)或〈i,j〉∈E(G) 0所在對角線上元素 ∞其它情形

其中，wij表示邊上的權值；∞表示大于所有邊上權值的數(shù)。A[i][j]=A[i][j]=第23頁，課件共76頁，創(chuàng)作于2023年2月例V0V1V2V30110000000011000V0V4V3V1V20101010101010111010001100V0V2V1V3V485679340365∞304∞∞640895∞807∞∞970A=B=C=無向圖有向圖無向網(wǎng)第24頁，課件共76頁，創(chuàng)作于2023年2月從無向圖(網(wǎng))的鄰接矩陣可以得出如下結論：矩陣是對稱的；可壓縮存儲（上（下）三角）;第i行或第i列非0元(非∞元)的個數(shù)為頂點i的度；矩陣中非0元(非∞元)的個數(shù)的一半為圖中邊的數(shù)目；很容易判斷頂點i和頂點j之間是否有邊相連(看矩陣中i行j列值是否為非0元(非∞元))。從有向圖(網(wǎng))的鄰接矩陣可以得出如下結論：矩陣不一定是對稱的；第i行中非0元(非∞元)的個數(shù)為頂點i的出度；第i列中非0元(非∞元)的個數(shù)為頂點i的入度；矩陣中非0元(非∞元)的個數(shù)為圖中弧的數(shù)目；很容易判斷頂點i和頂點j是否有弧相連。第25頁，課件共76頁，創(chuàng)作于2023年2月容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（?。?、找頂點的鄰接點等等。

n個頂點需要n*n個單元存儲邊(弧);空間復雜度為O(n2)。對稀疏圖而言尤其浪費空間。鄰接矩陣法優(yōu)點：鄰接矩陣法缺點：第26頁，課件共76頁，創(chuàng)作于2023年2月圖的鄰接矩陣數(shù)據(jù)類型描述：在用鄰接矩陣存儲圖時，除了用一個二維數(shù)組存儲用于表示頂點間相鄰關系的鄰接矩陣外，還需用一個一維數(shù)組來存儲頂點信息，另外還有圖的頂點數(shù)和邊數(shù)。故可將其形式描述如下：#defineMaxVerNum20typedefstruct{ VertexTypevexs[MaxVerNum]; intedges[MaxVerNum][MaxVerNum]; intn,e;}MGragh;/*最大頂點個數(shù)*//*頂點向量*//*鄰接矩陣，即邊表*//*頂點數(shù)和邊數(shù)*//*以鄰接矩陣存儲的圖類型*/第27頁，課件共76頁，創(chuàng)作于2023年2月鄰接矩陣建立：voidCreatGraph(MGraph&G){ inti,j,k; scanf(“%d%d”,&G.n,&G.e);//cin>>G.n>>G.e;

for(i=0;i<G.n;i++) scanf(“%c”,&G.vexs[i]);

for(i=0;i<G.n;i++) for(j=0;j<G.n;j++) G.edges[i][j]=0;

for(k=0;k<G.e;k++){ scanf((“%d%d”,&i,&j); G.edges[i][j]=1; }}/*建立有向圖G的鄰接矩陣存儲*//*輸入頂點數(shù)和邊數(shù)*//*輸入頂點信息，建立頂點表*//*初始化鄰接矩陣*//*輸入e條邊，建立鄰接矩陣*//*無向圖？！*/第28頁，課件共76頁，創(chuàng)作于2023年2月7.2.2鄰接表鄰接表（AdjacencyList）是圖的一種順序存儲與鏈式存儲結合的存儲方法。它包括兩部分：一部分是單鏈表，用來存放邊的信息；另一部分是數(shù)組，主要用來存放頂點本身的數(shù)據(jù)信息。第29頁，課件共76頁，創(chuàng)作于2023年2月一、無向圖的鄰接表對圖中每個頂點Vi建立一個單鏈表，鏈表中的結點表示依附于頂點Vi的邊，每個鏈表結點為兩個域：其中：鄰接點域adjvex記載與頂點Vi鄰接的頂點信息；指針域next指向下一個與頂點Vi鄰接的結點每個鏈表附設一個頭結點，頭結點結構為：其中：頂點域vexdata存放頂點信息（姓名、編號等）；表頭指針firstedge指向鏈表的第一個結點。頂點域表頭指針vertexfirstedge鄰接點域指針域adjvexnext第30頁，課件共76頁，創(chuàng)作于2023年2月頂點：通常按編號順序將頂點數(shù)據(jù)存儲在一維數(shù)組中；與同一頂點關聯(lián)的邊：用線性鏈表存儲特點：設無向圖中頂點數(shù)為n，邊數(shù)為e，則它的鄰接表需要n個頭結點和2e個表結點。頂點Vi的度

TD（Vi）=鏈表i中的表結點數(shù)。

V0V4V3V1V20V01V12V23V34V4213422110034返回第31頁，課件共76頁，創(chuàng)作于2023年2月圖的鄰接表數(shù)據(jù)類型描述：#defineMaxVerNum20typedefstructnode{ intadjvex;//鄰接點在數(shù)組中的下標

InfoTypeInfo;//該條邊(弧)的權值

structnode*next;//指向邊表中下一表結點}EdgeNode;typedefstructvnode{ VertexTypevertex;//頂點信息域

EdgeNode*firstedge;//邊表頭指針}VNode;typedefstruct{ VNodeadjList[MaxVerNum];//鄰接表

intn,e;

}ALGraph;/*最大頂點數(shù)為20*//*定義表結點類型ArcNode*//*定義頂點結點類型VNode*//*定義圖的類型ALGraph*//*頂點數(shù)和邊數(shù)*/返回第32頁，課件共76頁，創(chuàng)作于2023年2月鄰接表的建立voidCreateALGraph(ALGraph*G){ inti,j,k;EdgeNode*p;

cin>>G->n>>G->e; for(i=0;i<G->n;i++){

cin>>G->adjList[i].vertex; G->adjList[i].firstedge=NULL;}for(k=0;k<G->e;k++){

cin>>i>>j;

p=newEdgeNode; p->adjvertex=j;

p->next=G->adjList[i].firstedge;

//頭插法

G->adjList[i].firstedge=p;}第33頁，課件共76頁，創(chuàng)作于2023年2月二、有向圖鄰接表在有向圖中，第i個鏈表中的結點個數(shù)是頂點vi的出度。要求某個結點的入度，必須遍歷整個鄰接表。在所有鏈表中其鄰接點域的值為i的結點的個數(shù)是頂點vi的入度。

n個頂點，e條弧的有向圖，需n個表頭結點，e個表結點。

V0

V1

V2

V30V01V1∧

2V23V31230用鏈表存儲同一頂點為起點的弧第34頁，課件共76頁，創(chuàng)作于2023年2月三、有向圖的逆鄰接表

為了便于確定頂點的入度或以頂點vi為頭的弧，可以建立一個有向圖的逆鄰接表，即對每個頂點vi建立一個以vi為弧頭的結點組成的鏈表。

V0

V1

V2

V30V01V1

2V23V3用鏈表存儲同一頂點為起點的弧3002第35頁，課件共76頁，創(chuàng)作于2023年2月1．從無向圖的鄰接表可以得到如下結論

（1）第i個鏈表中結點數(shù)目為頂點i的度；（2）所有鏈表中結點數(shù)目的一半為圖中邊數(shù)；（3）占用的存儲單元數(shù)目為n+2e。2．從有向圖的鄰接表可以得到如下結論（1）第i個鏈表中結點數(shù)目為頂點i的出度；（2）所有鏈表中結點數(shù)目為圖中弧數(shù)；（3）占用的存儲單元數(shù)目為n+e。四、結論第36頁，課件共76頁，創(chuàng)作于2023年2月

從有向圖的鄰接表可知，不能求出頂點的入度。為此，我們可以另外建立有向圖的逆鄰接表，以便求出每一個頂點的入度。有向圖的逆鄰接表與鄰接表類似，只是它是從入度考慮結點，而不是從出度考慮結點。3.建立的鄰接表不是惟一的，與鍵盤輸入邊的順序有關，輸入的邊的順序不同，則得到的鏈表也不同。第37頁，課件共76頁，創(chuàng)作于2023年2月例：已知某網(wǎng)的鄰接（出邊）表，請畫出該網(wǎng)絡。8064125當鄰接表的存儲結構形成后，圖便唯一確定！第38頁，課件共76頁，創(chuàng)作于2023年2月鄰接表的缺點：鄰接表的優(yōu)點：空間效率高；容易尋找頂點的鄰接點；

判斷兩頂點間是否有邊或弧，需搜索兩結點對應的單鏈表，沒有鄰接矩陣方便。第39頁，課件共76頁，創(chuàng)作于2023年2月討論：鄰接表與鄰接矩陣有什么異同之處？1.聯(lián)系：鄰接表中每個鏈表對應于鄰接矩陣中的一行，鏈表中結點個數(shù)等于該行中非零元素的個數(shù)。2.區(qū)別：①對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關）。②鄰接矩陣的空間復雜度為O(n2),而鄰接表的空間復雜度為O(n+e)。3.用途：鄰接矩陣多用于稠密圖的存儲（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲（e<<n2)第40頁，課件共76頁，創(chuàng)作于2023年2月7.2.3十字鏈表（有向圖）

十字鏈表是將有向圖的鄰接表和逆鄰接表結合起來的一種有向圖鏈式存儲結構。結點結構有向圖的每一條弧有一個弧結點，每一個頂點必有一個頂點結點，其結構為：

弧結點頂點結點tailvex:

指示弧尾頂點的位置；headvex:

指示弧頭頂點的位置；hlink:指向弧頭相同的下一條??；tlink:

指向弧尾相同的下一條弧.vertex:

存放頂點的有關信息firstin:

指向以該頂點為弧頭

的第一個弧結點；firstout:

指向以該頂點為弧尾的第一個弧結點。tailvexheadvexhlinktlinkvertexfirstinfirstout整體結構通過hlink將弧頭相同的弧連在一個鏈表上；通過tlink將弧尾相同的弧連在一個鏈表上;

hlink鏈和tlink鏈的頭結點就是頂點結點第41頁，課件共76頁，創(chuàng)作于2023年2月例1234123413123431434241^^^^^^^^

1432弧結點頂點結點tailvexheadvexhlinktlinkvertexfirstinfirstout特點：①頂點結點數(shù)=頂點數(shù)；弧結點數(shù)=弧的條數(shù)②求入度：從頂點Vi出發(fā)，沿著hlink所經(jīng)過的弧結點數(shù)

求出度：從頂點Vi出發(fā)，沿著tlink所經(jīng)過的弧結點數(shù)第42頁，課件共76頁，創(chuàng)作于2023年2月有向圖的十字鏈表存儲結構：#defineMaxVerNum20typedefstructArcNode{ inttailvex,headvex; structArcNode*hlink,*tlink; InfoTypeinfo;}ArcNode;typedefstructVexNode{ VertexTypevertex; ArcNode*firstin,*firstout;}VexNode;typedefstruct{ VexNodexlist[MaxVerNum]; intvexnum,arcnum;}OLGraph;/*弧的尾和頭頂點的位置*//*指向頭相同和尾相同弧的鏈域*//*指向該頂點第一條入弧和出弧*//*頂點相關信息*//*有向圖的頂點數(shù)和弧數(shù)*//*表頭數(shù)組*//*弧結點的結構類型*//*頂點的結構類型*//*圖的結構類型*//*弧的權值信息*/第43頁，課件共76頁，創(chuàng)作于2023年2月建立有向圖的十字鏈表：voidCreateDG(OLGraph*G){ scanf(&G->vexnum,&G->arcnum); for(i=0;i<G->vexnum;i++){ scanf(&G->xlist[i].vertex); G->xlist[i].firstin=NULL;G->xlist[i].firstout=NULL; } for(k=0;k<G.arcnum;k++){ scanf(&v1,&v2); i=LocateVex(G,v1); j=LocateVex(G,v2); p=(ArcNode*)malloc(sizeof(ArcNode)); p->tailvex=i; p->headvex=j;

p->tlink=G->xlist[i].firstout; G->xlist[i].firstout=p;

p->hlink=G->xlist[j].firstin; G->xlist[j].firstin=p; }}/*構造表頭數(shù)組*//*輸入各弧并構造十字鏈表*//*確定v1和v2在G中位置*//*結點賦值*//*出弧的插入*//*入弧的插入*/第44頁，課件共76頁，創(chuàng)作于2023年2月7.2.4鄰接多重表（無向圖）鄰接多重表是無向圖的另一種鏈式存儲結構。每一個頂點有一個頂點結點，頂點結點結構為：圖的每一條邊有一個邊結點，邊結點的結構為：其中：vertex存放頂點的信息。

firstedge指向第一條依附于該頂點的邊結點。

mark為標記域，用以標記該條邊是否被處理過。

ivex和jvex為該邊所依附的兩個頂點。

ilink指向下一條依附于頂點ivex的邊。

jlink指向下一條依附于頂點jvex的邊。vertexfirstedgeivexilinkjvexjlinkmark第45頁，課件共76頁，創(chuàng)作于2023年2月圖的鄰接多重表數(shù)據(jù)類型描述：#defineMaxVerNum20typedefenum{unvisited,visited}VisitIf;typedefstructEdgeNode{ VisitIfmark; intivex,jvex; structEdgeNode*ilink,*jlink;}EdgeNode;typedefstructVexNode{ VertexTypevertex; EdgeNode*fistedge;}VexNode;typedefstruct{ VexNodeadjmulist[MaxVerNum]; intvexnum,edgenum;}AMLGraph;/*訪問標記*//*該邊依附的兩個頂點的位置*//*指向依附這兩個頂點的下一條邊*//*指向第一條依附該頂點的邊*//*無向圖的當前頂點數(shù)和邊數(shù)*//*邊結點的結構類型*//*頂點的結構類型*//*圖的結構類型*/第46頁，課件共76頁，創(chuàng)作于2023年2月1234134255121434323552^^^^^

15423例特點： 頂點結點數(shù)為n，邊結點數(shù)為e；對需要得到邊的兩個頂點的一類操作很方便第47頁，課件共76頁，創(chuàng)作于2023年2月在不同的存儲結構下，實現(xiàn)各種操作的效率可能是不同的。所以在求解實際問題時，要根據(jù)求解問題所需操作，選擇合適的存儲結構。分析:在圖的鏈接存儲(鄰接表、逆鄰接表、十字鏈表和鄰接多重表)中，表頭向量需要占用n個存儲單元，所有邊結點需要占用2e或e存儲單元，所以最多需要（n+2e）個存儲單元，稀疏圖采用這種存儲方式可節(jié)省存儲空間。第48頁，課件共76頁，創(chuàng)作于2023年2月7.3圖的遍歷和樹的遍歷類似，圖的遍歷也是從某個頂點出發(fā)，沿著某條搜索路徑對圖中所有頂點各作一次訪問。圖訪問的四個難點：

首結點、非連通圖、回路、多個相連頂點

我們可以設置一個全局型標志數(shù)組visited來標志某個頂點是否被訪過，未訪問的值為0，訪問過的值為1。根據(jù)搜索路徑的方向不同，圖的遍歷有兩種方法：深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。第49頁，課件共76頁，創(chuàng)作于2023年2月

深度優(yōu)先搜索遍歷類似于樹的先序遍歷。假定給定圖G的初態(tài)是所有頂點均未被訪問過，在G中任選一個頂點i作為遍歷的初始點，訪問此頂點，然后依次從i的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直到圖中所有和i有路徑相通的頂點都被訪問到；若此時尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。7.3.1深度優(yōu)先搜索深度優(yōu)先搜索是一種遞歸的過程。第50頁，課件共76頁，創(chuàng)作于2023年2月深度優(yōu)先搜索遍歷基本思想如下：首先訪問頂點i，并將其訪問標記置為訪問過，即visited[i]=1；然后搜索與頂點i有邊相連的下一個頂點j，若j未被訪問過，則訪問它，并將j的訪問標記置為訪問過，visited[j]=1，然后從j開始重復此過程，

若j已訪問，再訪問與i有邊相連的其它頂點；若與i有邊相連的頂點都被訪問過，則退回到前一個訪問頂點并重復剛才過程，直到圖中所有頂點都被訪問完止。深度優(yōu)先搜索是一種遞歸的過程。第51頁，課件共76頁，創(chuàng)作于2023年2月深度優(yōu)先遍歷從圖中某頂點v出發(fā)：

V0

V7

V6

V5

V4

V3

V2

V1訪問頂點v；依次從v的未被訪問的鄰接點

出發(fā)，對圖進行深度優(yōu)先遍歷；先序遍歷若樹非空訪問根結點；按照從左到右的順序先序遍歷根結點的每一棵子樹。如果將圖中頂點的鄰接點看作樹中結點的孩子，圖的深度優(yōu)先遍歷與樹的先序遍歷是否很類似？比較：第52頁，課件共76頁，創(chuàng)作于2023年2月深度遍歷：V1V2V4V8V5V6V3V7深度遍歷：V1V2V4V8V3V6V7V5V6V1V2V4V5V3V7V8V1V2V4V5V3V7V6V8由于沒有規(guī)定訪問鄰接點的順序,深度優(yōu)先序列不是唯一的第53頁，課件共76頁，創(chuàng)作于2023年2月若圖是連通的或強連通的，則從圖中某一個頂點出發(fā)可以訪問到圖中所有頂點，否則只能訪問到一部分頂點，再從未被訪問的頂點中選一個頂點出發(fā)訪問未被訪問的頂點。另外，從剛才寫出的遍歷結果可以看出，從某一個頂點出發(fā)的遍歷結果是不唯一的。

第54頁，課件共76頁，創(chuàng)作于2023年2月從連通圖中某個頂點出發(fā)的深度優(yōu)先遍歷的遞歸算法voidDFS(GraphG,intv){

visit(v);

visited[v]=TRUE;

for(w=FisrtAdjVertex(G,v);w;w=NextAdjVertex(G,v,w))

if(!visited[w])

DFS(G,w);}/*訪問v，標志位置位*//*w為v的首個鄰接點；w存在；w賦值為v的下一個鄰接點*//*對v尚未訪問的鄰接頂點w遞歸調用DFS*/第55頁，課件共76頁，創(chuàng)作于2023年2月以鄰接矩陣為存儲結構的深度優(yōu)先遍歷算法:第56頁，課件共76頁，創(chuàng)作于2023年2月算法描述為下面形式：voidDFS(MGraphG,inti)//從頂點i出發(fā)遍歷{intj;

visit(i);

//訪問頂點i,cout<<G.vexs[i];visited[i]=1;for(j=0;j<n;j++)//依次訪問鄰接點

if((G.edges[i][j]==1)&&(!visited[j]))DFS(j);}第57頁，課件共76頁，創(chuàng)作于2023年2月下圖描述的是從頂點1出發(fā)的深度優(yōu)先搜索遍歷過程，其中實線表示下一層遞歸調用，虛線表示遞歸調用的返回。從圖中，可以得到從頂點1的遍歷結果為1,2,4,8,5,6,3,7。同樣可以分析出從其它頂點出發(fā)的遍歷結果。1234567812345678第58頁，課件共76頁，創(chuàng)作于2023年2月以鄰接表為存儲結構的深度優(yōu)先遍歷算法:鄰接點域指針域adjvexnext

V0V4V3V1V20V01V12V23V34V4213422110034頂點域表頭指針vertexfirstedge第59頁，課件共76頁，創(chuàng)作于2023年2月voidDFS(ALGraph*G,inti){

ArcNode*p;

visit(G->adjlist[i].vertex);

visited[i]=True;

p=G->adjlist[i].firstedge;

while(p){

if(!visited[p->adjvex])

DFS(G,p->adjvex);

p=p->next;

}}/*以Vi為起點對G進行DFS搜索*//*訪問頂點Vi*//*取Vi邊表的頭指針*//*依次搜索Vi的鄰接點Vj=p->adjvex*//*若Vj未訪問，則以Vj為起點DFS搜索*//*找Vi的下一個鄰接點*/圖的鄰接表存儲結構演示第60頁，課件共76頁，創(chuàng)作于2023年2月

V0

V7

V6

V5

V4

V3

V2

V101234567V0V1V2V3V4V5V6V7120115773064265243V0V1V3V7V4V2V5V6例:深度遍歷：V0V1V3V7V4V2V5V6第61頁，課件共76頁，創(chuàng)作于2023年2月booleanvisited[MaxVerNum];

//訪問標志數(shù)組，全局數(shù)組voidDFSTraverse(GraphG){

//對圖G作深度優(yōu)先遍歷for(v=0;v<G.n;++v)

//訪問標志數(shù)組初始化

visited[v]=FALSE;for(v=0;v<G.n;++v)

//對尚未訪問的頂點調用DFS

if(!visited[v])DFS(G,v);｝對圖的深度優(yōu)先遍歷的算法：第62頁，課件共76頁，創(chuàng)作于2023年2月在遍歷時，對圖中每個頂點至多調用一次DFS函數(shù)，因為一旦某個頂點被標志成已被訪問，就不再從它出發(fā)進行搜索。因此，遍歷圖的過程實質上是對每個頂點查找其鄰接點的過程。其耗費的時間則取決于所采用的存儲結構。當用二維數(shù)組表示鄰接矩陣圖的存儲結構時，查找每個頂點的鄰接點所需時間為O（n2），其中n為圖中頂點數(shù)。而當以鄰接表作圖的存儲結構時，找鄰接點所需時間為O（e），其中e為無向圖中邊的數(shù)或有向圖中弧的數(shù)。由此，當以鄰接表作存儲結構時，深度優(yōu)先搜索遍歷圖的時間復雜度為O（n+e）。深度優(yōu)先搜索的算法復雜度：01100000000110000V01V1∧

2V23V31230

V0

V1

V2

V3第63頁，課件共76頁，創(chuàng)作于2023年2月

廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷。設圖G的初態(tài)是所有頂點均未訪問，在G中任選一頂點i作為初始點，訪問該頂點，然后再依次訪問該頂點的各個未曾訪問的鄰接點，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點起始點，上述過程，直至圖中所有頂點都被訪問到為止。7.3.2廣度優(yōu)先搜索第64頁，課件共76頁，創(chuàng)作于2023年2月廣度優(yōu)先搜索的基本思想是：首先訪問頂點i，并將其訪問標志置為已被訪問，即visited[i]=1；接著依次訪問與頂點i有邊相連的所有頂點W1，W2，…，Wt；然后再按順序訪問與W1，W2，…，Wt有邊相連又未曾訪問過的頂點；依此類推，直到圖中所有頂點都被訪問完為止。

即廣度優(yōu)先搜索遍歷圖的過程中以v1為起始點，由近至遠，依次訪問和v1有路徑相通且路徑長度為1，2，…的頂點。

V6V1V2V4V5V3V7V8第65頁，課件共76頁，創(chuàng)作于2023年2月

V0

V7

V6

V5

V4

V3

V2

V1V0

V1

V3

V2

V7

V6

V5

V4在遍歷過程中所經(jīng)過的路徑求圖G中以V0起點的的廣度優(yōu)先序列：V0,V1,V2,V3,V4,V5,V6,V7由于沒有規(guī)定訪問鄰接點的順序,廣度優(yōu)先序列不是唯一的例:第66頁，課件共76頁，創(chuàng)作于2023年2月廣度遍歷：V1V2V3V4V5V6V7V8廣度遍歷：V1V2V3V4V6V7V8V5V6V1V2V4V5V3V7V8例:V1V2V4V5V3V7V6V8第67頁，課件共76頁，創(chuàng)作于2023年2月從圖中某頂點vi出發(fā)：訪問頂點vi；訪問vi的所有未被訪問的鄰接點w1,w2,…wk；依次從這些鄰接點(在步驟2中訪問的頂點)出發(fā)，訪問它們的所有未被訪問的鄰接點;依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；為實現(xiàn)3)，需要保存在步驟(2)中訪問的頂點，而且訪問這些頂點鄰接點的順序為：先保存的頂點，其鄰接點先被訪問。

V0

V7

V6

V5

V4

V3

V2

V1廣度優(yōu)先遍歷算法（類似于樹的按層遍歷）在廣度優(yōu)先遍歷算法中，需設置一隊列Q，保存已訪問的頂點，并控制遍歷頂點的順序。第68頁，課件共76頁，創(chuàng)作于2023年2月開始訪問V0,置標志求V鄰接點ww存在嗎V下一鄰接點ww訪問過結束NYNYBFS初始化隊列V0入隊隊列空嗎隊頭V出隊訪問w,置標志w入隊NY從連通圖中某個頂點出發(fā)的廣度優(yōu)先遍歷的遞歸算法第69頁，課件共76頁，創(chuàng)作于2023年2月圖的廣度優(yōu)先遍歷算法開始標志數(shù)組初始化i=0Vi訪問過BFSi=i+1i<G.