第7章-1-(71-72圖的定義及存儲結(jié)構(gòu))

1、第7章 圖本章教學(xué)目的與要求：掌握圖的基本概念、存儲方法、基本操作。掌握與圖相關(guān)的一些算法，如遍歷、最短路徑、最小生成樹等。7.1圖的定義和術(shù)語圖的實(shí)例其中用圓圈標(biāo)示的是數(shù)據(jù)元素，在圖中稱為其中用圓圈標(biāo)示的是數(shù)據(jù)元素，在圖中稱為頂點(diǎn)頂點(diǎn)。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345圖圖G1圖圖G2圖圖G37.1圖的定義和術(shù)語頂點(diǎn)之間的連線，表示數(shù)據(jù)元素之間的頂點(diǎn)之間的連線，表示數(shù)據(jù)元素之間的關(guān)系關(guān)系。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345圖圖G1圖圖G2圖圖G32022-3-14v圖圖(Graph)圖圖G是由兩個集合是由兩個

2、集合V(G)和和E(G)組成組成 的的,記為記為G=(V,E)其中：其中：V(G)V(G)是頂點(diǎn)的非空有限集是頂點(diǎn)的非空有限集 E(G)E(G)是是關(guān)系關(guān)系的有限集合，的有限集合，關(guān)系關(guān)系是頂點(diǎn)的無序?qū)蛴行驅(qū)κ琼旤c(diǎn)的無序?qū)蛴行驅(qū)有向圖有向圖有向圖有向圖G是由兩個集合是由兩個集合V(G)和和E(G)組成組成 V(G)V(G)是頂點(diǎn)的非空有限集，是頂點(diǎn)的非空有限集，E(G)E(G)是是有向邊有向邊（也稱（也稱弧?。┑挠邢蓿┑挠邢藜?，弧是頂點(diǎn)的有序?qū)?，記為集合，弧是頂點(diǎn)的有序?qū)Γ洖?，vi,vjvi,vj是頂點(diǎn)，是頂點(diǎn)，vi vi為為弧尾，弧尾，vjvj為弧頭為弧頭v無向圖無向圖無向圖無向圖

3、G是由兩個集合是由兩個集合V(G)和和E(G)組成組成 V(G)V(G)是頂點(diǎn)的非空有限集，是頂點(diǎn)的非空有限集，E(G)E(G)是是邊邊的有限集合，邊是頂?shù)挠邢藜?，邊是?點(diǎn)的無序?qū)?，記為（點(diǎn)的無序?qū)Γ洖椋╲i,vjvi,vj）或（或（vj,vi)vj,vi)，并且并且（vi,vj)=(vj,vi)vi,vj)=(vj,vi)圖圖的概念的概念v1v2v3v4v1v2v3v4v5圖圖G1圖圖G2G1=(V1,A1)其中，其中，V1=v1,v2,v3.v4 A1=,G2=(V2,E2)其中，其中，V2=v1,v2,v3.v4,v5 E2=(v1,v2),(v1,v4),(v2,v3),(v2,

4、v5),(v3,v4),(v3,v5)7.1圖的定義和術(shù)語在在G1中，連線上有箭頭表示方向，則該連線稱為中，連線上有箭頭表示方向，則該連線稱為弧弧。我們。我們可以用可以用表示一條弧，表示一條弧，v1稱為稱為弧尾弧尾，v2稱為稱為弧頭弧頭。相應(yīng)的，圖相應(yīng)的，圖G1稱為稱為有向圖有向圖。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345圖G1圖G2圖G37.1圖的定義和術(shù)語在在G2中，沒有箭頭的連線稱為中，沒有箭頭的連線稱為邊邊。圖。圖G2稱為稱為無向圖無向圖。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345圖圖G1圖圖G2圖圖G37.1圖的定

5、義和術(shù)語在在G3中，連線上標(biāo)有與之相關(guān)聯(lián)的數(shù)值（稱為權(quán)），這種中，連線上標(biāo)有與之相關(guān)聯(lián)的數(shù)值（稱為權(quán)），這種形式的圖通常稱為形式的圖通常稱為網(wǎng)網(wǎng)。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345圖圖G1圖圖G2圖圖G37.1圖的定義和術(shù)語有有n個頂點(diǎn)，且每兩個頂點(diǎn)之間均有邊的無向圖，稱為個頂點(diǎn)，且每兩個頂點(diǎn)之間均有邊的無向圖，稱為完完全圖全圖。完全圖共有。完全圖共有n*（n-1）/ 2條邊。條邊。幾個完全圖的例子如下：幾個完全圖的例子如下：v1v2v3v4v1v1v2v1v2v37.1圖的定義和術(shù)語有有n個頂點(diǎn)，且每兩個頂點(diǎn)之間均有邊的有向圖，稱為個頂點(diǎn)，且每兩個頂

6、點(diǎn)之間均有邊的有向圖，稱為有有向完全圖向完全圖。有向完全圖共有。有向完全圖共有n*（n-1）條邊。條邊。幾個幾個有向完全圖有向完全圖的例子如下：的例子如下：v1v2v3v4v1v1v2v1v2v3v子圖子圖如果圖如果圖G(V,E)G(V,E)和圖和圖G G(V(V,E,E), ),滿足：滿足：V V V V，E E E E 則稱則稱G G為為G G的子圖的子圖24513635621v1v3v4v2v1v3v2v3v47.1圖的定義和術(shù)語7.1圖的定義和術(shù)語在無向圖中，若在無向圖中，若(v,w)是一條邊，是一條邊， (v,w) E則則v,w互為互為鄰接點(diǎn)鄰接點(diǎn)uvw7.1圖的定義和術(shù)語在無向圖中

7、，頂點(diǎn)在無向圖中，頂點(diǎn)v的的度度是指與是指與v相連的邊的條數(shù)。相連的邊的條數(shù)。uvw7.1圖的定義和術(shù)語在有向圖中，頂點(diǎn)在有向圖中，頂點(diǎn)v的的出度出度是指是指v作為弧尾的作為弧尾的弧的條數(shù)。記為弧的條數(shù)。記為OD(v)uvw7.1圖的定義和術(shù)語在有向圖中，頂點(diǎn)在有向圖中，頂點(diǎn)v的的入度入度是指是指v作為弧頭的作為弧頭的弧的條數(shù)。記為弧的條數(shù)。記為ID(v)uvw7.1圖的定義和術(shù)語在有向圖中，頂點(diǎn)在有向圖中，頂點(diǎn)v的的度度是指是指v的入度和出度的入度和出度之和。記為之和。記為TD(v)TD(v)=ID(v)+OD(v)uvw7.1圖的定義和術(shù)語頂點(diǎn)頂點(diǎn)v到頂點(diǎn)到頂點(diǎn)w的的路徑路徑指從指從v出發(fā)

8、沿著邊或者弧到達(dá)出發(fā)沿著邊或者弧到達(dá)w所經(jīng)過的頂點(diǎn)序列。所經(jīng)過的頂點(diǎn)序列。如上圖中如上圖中 v-v2-w 是從是從v到到w的一條路經(jīng)的一條路經(jīng)路徑上邊或者弧的數(shù)目稱為路徑上邊或者弧的數(shù)目稱為路徑的長度路徑的長度。序列中頂點(diǎn)不重復(fù)的路徑稱為序列中頂點(diǎn)不重復(fù)的路徑稱為簡單路徑簡單路徑vv2v3v4w7.1圖的定義和術(shù)語第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑稱為第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑稱為回路回路或者或者環(huán)。環(huán)。路徑路徑 v-v2-v3-v4-v 就是一條回路就是一條回路除第一個頂點(diǎn)和最后一個頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)除第一個頂點(diǎn)和最后一個頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路，稱為的回路，稱為

9、簡單回路或者簡單環(huán)簡單回路或者簡單環(huán)vv2v3v4w7.1圖的定義和術(shù)語在無向圖中，如果從在無向圖中，如果從v到到w之間有路徑，則稱頂點(diǎn)之間有路徑，則稱頂點(diǎn)v和頂點(diǎn)和頂點(diǎn)w是是連通的連通的。如果圖中任意兩個頂點(diǎn)都是連通的，則稱該圖為如果圖中任意兩個頂點(diǎn)都是連通的，則稱該圖為連通圖連通圖。vv2v3v4w連通圖連通圖7.1圖的定義和術(shù)語上圖看作一個整體，不是上圖看作一個整體，不是連通圖連通圖。v1v2v3v4v5v6v77.1圖的定義和術(shù)語無向圖中的一個無向圖中的一個極大連通子圖極大連通子圖，稱為該圖的，稱為該圖的連通分量連通分量。v1v2v3v4v5v6v3v6v1v2v4v52個連通分量個連

10、通分量G0上圖上圖G0不是連通圖，有兩個不是連通圖，有兩個連通分量連通分量.v強(qiáng)連通圖強(qiáng)連通圖有向圖中，如果對每一對有向圖中，如果對每一對Vi,VjVi,Vj V, V, ViVi Vj,Vj,從從ViVi到到Vj Vj 和從和從VjVj到到 ViVi都存在路徑，則稱都存在路徑，則稱G G是是強(qiáng)連通圖強(qiáng)連通圖強(qiáng)連通圖強(qiáng)連通圖356245136非強(qiáng)連通圖非強(qiáng)連通圖7.1圖的定義和術(shù)語v1v2v3v4v5v1v2v3v47.1圖的定義和術(shù)語上圖上圖G1不是強(qiáng)連通圖，有兩個不是強(qiáng)連通圖，有兩個強(qiáng)連通分量強(qiáng)連通分量 ：G1-1和和G1-2v1v2v3v4圖圖G1v1v3v4圖圖G1-1v2圖圖G1-2

11、有向圖中的有向圖中的極大極大強(qiáng)連通子圖稱為有向圖的強(qiáng)連通子圖稱為有向圖的強(qiáng)連通分量強(qiáng)連通分量。7.1圖的定義和術(shù)語連通圖的連通圖的生成樹生成樹是一個是一個極小連通子圖極小連通子圖。生成樹中包含圖的全部頂點(diǎn)（假定為生成樹中包含圖的全部頂點(diǎn)（假定為n個），包含能夠連接個），包含能夠連接起起n個頂點(diǎn)的個頂點(diǎn)的n-1條邊，使得生成樹也是一個連通圖。條邊，使得生成樹也是一個連通圖。如上面圖如上面圖G2-1為圖為圖G2的一棵的一棵生成樹生成樹。v1v2v3v4v5圖G2v1v2v3v4v5圖G2-12022-3-125一個連通圖的一個連通圖的生成樹生成樹是一個是一個極小連通子圖極小連通子圖，它含有圖中它含

12、有圖中全部頂點(diǎn)全部頂點(diǎn)，但只有足以構(gòu)成一棵，但只有足以構(gòu)成一棵樹的樹的n-1條邊條邊。一棵有一棵有n個頂點(diǎn)的生成樹有且僅有個頂點(diǎn)的生成樹有且僅有n-1條邊。條邊。15732461573246連通圖連通圖生成樹生成樹26抽象數(shù)據(jù)類型-圖ADT Graph 數(shù)據(jù)對象數(shù)據(jù)對象 V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R：R=VR VR=|v,w V|v,w V且且P(v,wP(v,w), 表示從表示從v v到到w w的弧，的弧， 謂詞謂詞P(v,wP(v,w)定義了弧定義了弧的意義或信息的意義或信息 基本操作基本操作P： Gr

13、aphCreat(G,，V，VR)；/創(chuàng)建圖創(chuàng)建圖 GraphDestory(G)；/銷毀圖銷毀圖 GraphLocateVertex(G，v)；/尋找頂點(diǎn)尋找頂點(diǎn)v GraphGetVertex(G，v)；/返回頂點(diǎn)返回頂點(diǎn)v的值的值 GraphPutVertex(&G，v, value)；/為頂點(diǎn)為頂點(diǎn)v賦值賦值 GraphFirstAdjVex(G，v)；/返回返回v的第一個鄰接頂點(diǎn)的第一個鄰接頂點(diǎn) GraphNextAdjVex(G，v，w)；/返回返回v的下一個鄰接頂點(diǎn)的下一個鄰接頂點(diǎn) GraphInsertVertex(G，v)；/在圖中添加新頂點(diǎn)在圖中添加新頂點(diǎn)v Gra

14、phDeleteVertex(G，v)；/刪除頂點(diǎn)刪除頂點(diǎn)v及相關(guān)的弧及相關(guān)的弧 GraphInsertArc(G，v，w)；/在圖中增加弧在圖中增加弧 GraphDeleteArc(G，v，w)；/刪除圖中刪除圖中v和和w之間的弧之間的弧 DFSTtraverse(G，v，Visit()；/深度優(yōu)先遍歷深度優(yōu)先遍歷 BFSTtraverse(G，v，Visit()；/廣度優(yōu)先遍歷廣度優(yōu)先遍歷 ADT Graph 7.2 圖的存儲結(jié)構(gòu) 由于圖的頂點(diǎn)之間存在多對多的關(guān)系，因此，圖由于圖的頂點(diǎn)之間存在多對多的關(guān)系，因此，圖的存儲結(jié)構(gòu)相應(yīng)的比較復(fù)雜。的存儲結(jié)構(gòu)相應(yīng)的比較復(fù)雜。本節(jié)我們介紹兩種最常用的

15、存儲結(jié)構(gòu)，本節(jié)我們介紹兩種最常用的存儲結(jié)構(gòu)，鄰接矩陣鄰接矩陣表示表示法法(數(shù)組表示法數(shù)組表示法)和和鄰接表鄰接表表示法。表示法。十字鏈表十字鏈表表示法表示法鄰接多重表鄰接多重表表示法表示法7.2.1鄰接矩陣表示法（數(shù)組表示法）用一個一維數(shù)組存儲頂點(diǎn)的信息。用一個一維數(shù)組存儲頂點(diǎn)的信息。用一個二維數(shù)組存儲數(shù)據(jù)元素之間關(guān)系用一個二維數(shù)組存儲數(shù)據(jù)元素之間關(guān)系(邊或弧邊或弧)的信息，的信息，這種表示方法我們稱之為這種表示方法我們稱之為鄰接矩陣法鄰接矩陣法。7.2.1鄰接矩陣表示法（數(shù)組表示法）一、舉例說明鄰接矩陣表示法一、舉例說明鄰接矩陣表示法1.有向圖有向圖v1v2v3v4圖G1v1v2v3v4邊信

16、息數(shù)組邊信息數(shù)組arcsv1v2v3v4v1v2v3v4頂點(diǎn)信息數(shù)組頂點(diǎn)信息數(shù)組vexs7.2.1鄰接矩陣表示法（數(shù)組表示法）之間無邊相連、若之間有邊相連、若vjvivjvi01vjviarcsv1v2v3v4圖G1v1v2v3v4邊信息數(shù)組arcsv1v2v3v4v10110v20000v30001v41000頂點(diǎn)信息數(shù)組vexs7.2.1鄰接矩陣表示法（數(shù)組表示法）v1v2v3v4圖G1v1v2v3v4邊信息數(shù)組arcsv1v2v3v4v10110v20000v30001v41000思考思考：（1）如何從）如何從arcs尋找尋找v1的出度、入度，鄰接點(diǎn)；的出度、入度，鄰接點(diǎn)；（2）是否能從

17、）是否能從arcs判斷該圖是否有向圖。判斷該圖是否有向圖。頂點(diǎn)信息數(shù)組vexs7.2.1鄰接矩陣表示法（數(shù)組表示法）邊信息數(shù)組arcsv1v2v3v4v10110v20000v30001v41000解答：解答：（1）如何從）如何從arcs尋找尋找v1的出度、入度，鄰接的出度、入度，鄰接點(diǎn)；點(diǎn)；V1行所有行所有1的個數(shù)為的個數(shù)為v1的出度；的出度；V1列所有列所有1的個數(shù)為的個數(shù)為v1的入度；的入度；V1行所有行所有1對應(yīng)的下標(biāo)在對應(yīng)的下標(biāo)在vexs中對應(yīng)的頂點(diǎn)。中對應(yīng)的頂點(diǎn)。（2）能否從）能否從arcs判斷該圖的類型，（有向圖判斷該圖的類型，（有向圖還是無向圖）。還是無向圖）。當(dāng)當(dāng)arcs數(shù)組

18、關(guān)于主對角線不對稱時，可以肯定數(shù)組關(guān)于主對角線不對稱時，可以肯定其是有向圖。否則不能判定。其是有向圖。否則不能判定。7.2.1鄰接矩陣表示法（數(shù)組表示法）2.無向圖無向圖v1v2v3v4v5邊信息數(shù)組arcsv1v2v3v4v5v1v2v3v4v5頂點(diǎn)信息數(shù)組vexsv1v2v3v4v5圖G27.2.1鄰接矩陣表示法（數(shù)組表示法）之間無邊相連、若之間有邊相連、若vjvivjvi01vjviarcsv1v2v3v4v5邊信息數(shù)組arcsv1v2v3v4v5v10 101 0v21 010 1v30 101 1v41 010 00 110 0v5頂點(diǎn)信息數(shù)組vexsv1v2v3v4v5圖G27.2

19、.1鄰接矩陣表示法（數(shù)組表示法）思考思考：（1）如何從）如何從arcs尋找尋找v1的度，鄰接點(diǎn)；的度，鄰接點(diǎn)；（2）是否能從）是否能從arcs判斷該圖是否有向圖。判斷該圖是否有向圖。v1v2v3v4v5邊信息數(shù)組arcsv1v2v3v4v5v10 101 0v21 010 1v30 101 1v41 010 00 110 0v5頂點(diǎn)信息數(shù)組vexsv1v2v3v4v5圖G27.2.1鄰接矩陣表示法（數(shù)組表示法）解答：解答：（1）如何從）如何從arcs尋找尋找v1的度，鄰接點(diǎn)；的度，鄰接點(diǎn)；V1行所有行所有1的個數(shù)為的個數(shù)為v1的度；的度；V1行所有行所有1對應(yīng)的下標(biāo)在對應(yīng)的下標(biāo)在vexs中對應(yīng)

20、的頂點(diǎn)。中對應(yīng)的頂點(diǎn)。（2）能否從）能否從arcs判斷該圖的類型，（有向圖判斷該圖的類型，（有向圖還是無向圖）。還是無向圖）。當(dāng)當(dāng)arcs數(shù)組關(guān)于主對角線不對稱時，可以肯定數(shù)組關(guān)于主對角線不對稱時，可以肯定其是有向圖。否則不能判定。其是有向圖。否則不能判定。邊信息數(shù)組arcsv1v2v3v4v5v10 101 0v21 010 1v30 101 1v41 010 00 110 0v57.2.1鄰接矩陣表示法（數(shù)組表示法）3.網(wǎng)網(wǎng)v1v2v3v4v5v61555346798v1v2v3v4v5v6頂點(diǎn)信息數(shù)組vexs7.2.1鄰接矩陣表示法（數(shù)組表示法）v1v2v3v4v5v6155534679

21、8邊信息數(shù)組arcsv1v2v3v4v5v6v157v24v389v4565v5v631之間無邊相連、若之間有邊相連、若vjvivjviwijvjviarcs二、用c語言描述圖的存儲結(jié)構(gòu)及其操作1.存儲結(jié)構(gòu)存儲結(jié)構(gòu) 為了簡單起見，我們假設(shè)頂點(diǎn)所代表數(shù)據(jù)的數(shù)據(jù)類型是字符為了簡單起見，我們假設(shè)頂點(diǎn)所代表數(shù)據(jù)的數(shù)據(jù)類型是字符串，如串，如“v1”、“v2”等；考慮到頂點(diǎn)之間的邊上可能帶有權(quán)值，等；考慮到頂點(diǎn)之間的邊上可能帶有權(quán)值，則鄰接矩陣的類型設(shè)為則鄰接矩陣的類型設(shè)為double。當(dāng)然大家可以根據(jù)應(yīng)用問題的不。當(dāng)然大家可以根據(jù)應(yīng)用問題的不同，適當(dāng)調(diào)整同，適當(dāng)調(diào)整數(shù)據(jù)類型數(shù)據(jù)類型。struct MGr

22、aphchar *vexs100;/存儲頂點(diǎn)信息存儲頂點(diǎn)信息double arcs100100;/存儲邊的信息存儲邊的信息 int vexnum,arcnum;/頂點(diǎn)數(shù)目和邊的數(shù)目頂點(diǎn)數(shù)目和邊的數(shù)目;二、用二、用c語言描述圖的存儲結(jié)構(gòu)及其操作語言描述圖的存儲結(jié)構(gòu)及其操作2.基本操作基本操作 圖的基本操作包括圖的初始化、查找頂點(diǎn)是否存在、查找邊是否存在、插入圖的基本操作包括圖的初始化、查找頂點(diǎn)是否存在、查找邊是否存在、插入一個頂點(diǎn)，插入一條邊，刪除一個頂點(diǎn)，刪除一條邊，求頂點(diǎn)的鄰接點(diǎn)等。一個頂點(diǎn)，插入一條邊，刪除一個頂點(diǎn)，刪除一條邊，求頂點(diǎn)的鄰接點(diǎn)等。void InitGraph(MGraph

23、&mg)/圖的初始化圖的初始化mg.arcnum=mg.vexnum=0;/頂點(diǎn)和邊的數(shù)目均為頂點(diǎn)和邊的數(shù)目均為0for(int i=1;i100;i+)for(int j=1;j100;j+) mg.arcsij=0; /各個頂點(diǎn)之間初始情況下沒有邊相連各個頂點(diǎn)之間初始情況下沒有邊相連二、用二、用c語言描述圖的存儲結(jié)構(gòu)及其操作語言描述圖的存儲結(jié)構(gòu)及其操作2.基本操作基本操作int FindVex(MGraph mg,char *vex)/查找頂點(diǎn)查找頂點(diǎn)vex是否存在是否存在for(int i=1;i=mg.vexnum;i+) if(strcmp(mg.vexsi,vex)=0)r

24、eturn i;/頂點(diǎn)存在，返回頂點(diǎn)存在，返回ireturn 0;/頂點(diǎn)不存在，返回頂點(diǎn)不存在，返回0二、用二、用c語言描述圖的存儲結(jié)構(gòu)及其操作語言描述圖的存儲結(jié)構(gòu)及其操作2.基本操作基本操作int FindArc(MGraph mg,char *v1,char *v2)/查找邊或弧查找邊或弧是否存在是否存在int x,y;x=FindVex(mg,v1);y=FindVex(mg,v2);if(x=0 | y=0) return 0; /某個頂點(diǎn)不存在某個頂點(diǎn)不存在,邊肯定不存在，返回邊肯定不存在，返回0if(mg.arcsxy=1) return 1;/邊存在，返回邊存在，返回1二、用二、

25、用c語言描述圖的存儲結(jié)構(gòu)及其操作語言描述圖的存儲結(jié)構(gòu)及其操作2.基本操作基本操作void InsertVex(MGraph &mg,char *vex)/插入一個頂點(diǎn)插入一個頂點(diǎn)vexif(FindVex(mg,vex)=0) /頂點(diǎn)不存在頂點(diǎn)不存在mg.vexnum+;mg.vexsmg.vexnum=new charstrlen(vex);strcpy(mg.vexsmg.vexnum,vex);/新頂點(diǎn)加入新頂點(diǎn)加入二、用二、用c語言描述圖的存儲結(jié)構(gòu)及其操作語言描述圖的存儲結(jié)構(gòu)及其操作2.基本操作基本操作void InsertArc(MGraph &mg,char *v1

26、,char *v2)/插入一條邊或弧插入一條邊或弧int x,y;x=FindVex(mg,v1);y=FindVex(mg,v2);if(x & y) mg.arcsxy=1;mg.arcnum+;二、用二、用c語言描述圖的存儲結(jié)構(gòu)及其操作語言描述圖的存儲結(jié)構(gòu)及其操作2.基本操作基本操作int FirstAdjVex(MGraph mg,int v) /在圖在圖mg中，求頂點(diǎn)中，求頂點(diǎn)v的第一個鄰接點(diǎn)的第一個鄰接點(diǎn)/使用頂點(diǎn)的下標(biāo)代替字符串，使用頂點(diǎn)的下標(biāo)代替字符串，/如頂點(diǎn)如頂點(diǎn)“v1“對應(yīng)下標(biāo)為對應(yīng)下標(biāo)為v, 則使用則使用v代表代表“v1“for(int i=1;i=mg.vex

27、num;i+) if(mg.arcsvi!=0)return i;return 0; /不存在鄰接點(diǎn)時，返回不存在鄰接點(diǎn)時，返回0二、用二、用c語言描述圖的存儲結(jié)構(gòu)及其操作語言描述圖的存儲結(jié)構(gòu)及其操作2.基本操作基本操作int NextAdjVex(MGraph mg,int v,int w)/在圖在圖mg中，求頂點(diǎn)中，求頂點(diǎn)v的相對于頂點(diǎn)的相對于頂點(diǎn)w的下一個鄰接點(diǎn)的下一個鄰接點(diǎn)for(int i=w+1;i=mg.vexnum;i+)if(mg.arcsvi!=0)return i;return 0;二、用二、用c語言描述圖的存儲結(jié)構(gòu)及其操作語言描述圖的存儲結(jié)構(gòu)及其操作2.基本操作基本操作

28、對于左圖，可以用右面代碼來構(gòu)造對于左圖，可以用右面代碼來構(gòu)造v1v2v3v4圖圖G1int main(int argc, char* argv ) MGraph mg; InitGraph(mg);/圖的初始化圖的初始化InsertVex(mg,v1);/插入頂點(diǎn)插入頂點(diǎn)InsertVex(mg,v2);InsertVex(mg,v3);InsertVex(mg,v4);InsertArc(mg,v1,v2);/插入邊插入邊InsertArc(mg,v1,v3);InsertArc(mg,v3,v4);InsertArc(mg,v4,v1); return 0;7.2.2 鄰接表表示法一、舉例

29、說明鄰接表表示法一、舉例說明鄰接表表示法1.有向圖有向圖v1v2v3v4圖圖G11 v12 v23 v34 v42341思考：根據(jù)右圖思考：根據(jù)右圖1.如何求如何求v1的出度、入度、以的出度、入度、以v1為弧尾的鄰接點(diǎn)？為弧尾的鄰接點(diǎn)？2.如何求圖中共有幾條邊？如何求圖中共有幾條邊？7.2.2 鄰接表表示法一、舉例說明鄰接表表示法一、舉例說明鄰接表表示法1.有向圖有向圖1 v12 v23 v34 v42341思考：思考：1.如何求如何求v1的出度、入度、以的出度、入度、以v1為弧尾的鄰接點(diǎn)？為弧尾的鄰接點(diǎn)？解答：解答：v1的出度是的出度是v1后面鏈表的長后面鏈表的長度。度。 V1的入度為所有鏈

30、表中數(shù)據(jù)域?yàn)榈娜攵葹樗墟湵碇袛?shù)據(jù)域?yàn)?的結(jié)點(diǎn)的個數(shù)。的結(jié)點(diǎn)的個數(shù)。V1的鄰接點(diǎn)就是的鄰接點(diǎn)就是v1后鏈表上的所有后鏈表上的所有結(jié)點(diǎn)。結(jié)點(diǎn)。2.如何求圖中共有幾條邊？如何求圖中共有幾條邊？所有鏈表中所有結(jié)點(diǎn)的個數(shù)。所有鏈表中所有結(jié)點(diǎn)的個數(shù)。7.2.2 鄰接表表示法一、舉例說明鄰接表表示法一、舉例說明鄰接表表示法2.無向圖無向圖1 v12 v23 v34 v45 v524 41v1v2v3v4v5圖G2135 25 3 23 思考：根據(jù)右圖思考：根據(jù)右圖1.如何求如何求v1的度、的度、v1的鄰接點(diǎn)？的鄰接點(diǎn)？2.如何求圖中共有幾條邊？如何求圖中共有幾條邊？7.2.2 鄰接表表示法一、用c語言描述

31、圖的鄰接表存儲結(jié)構(gòu)及其操作1.存儲結(jié)構(gòu)存儲結(jié)構(gòu) 從上面的例子可以從上面的例子可以看出，鄰接表中存在兩看出，鄰接表中存在兩種結(jié)點(diǎn)，一種是種結(jié)點(diǎn)，一種是鏈表的鏈表的頭結(jié)點(diǎn)頭結(jié)點(diǎn)，用來存儲，用來存儲頂點(diǎn)頂點(diǎn)信息；一種是信息；一種是表結(jié)點(diǎn)表結(jié)點(diǎn)，用來存放用來存放鄰接點(diǎn)以及邊鄰接點(diǎn)以及邊的信息。的信息。1 v12 v23 v34 v45 v524 41135 25 3 23 7.2.2 鄰接表表示法一、用c語言描述圖的鄰接表存儲結(jié)構(gòu)及其操作1 v12 v23 v34 v45 v524 41135 25 3 23 datafirstarc表頭結(jié)點(diǎn)：表頭結(jié)點(diǎn)：頂點(diǎn)信息頂點(diǎn)信息指向第指向第1個鄰接個鄰接點(diǎn)的指

32、針點(diǎn)的指針表結(jié)點(diǎn)表結(jié)點(diǎn)adjvexinfonextarc鄰接點(diǎn)鄰接點(diǎn)邊或弧的信息（如邊或弧的信息（如權(quán)值）權(quán)值）指向下一條邊或指向下一條邊或弧的結(jié)點(diǎn)弧的結(jié)點(diǎn)7.2.2 鄰接表表示法一、一、用用c語言描述圖的鄰接表存儲結(jié)構(gòu)及其操作語言描述圖的鄰接表存儲結(jié)構(gòu)及其操作/表結(jié)點(diǎn)表結(jié)點(diǎn)-結(jié)構(gòu)體類型結(jié)構(gòu)體類型struct ArcNodeint adjvex; /鄰接點(diǎn)鄰接點(diǎn)double weight; /邊的信息邊的信息(權(quán)權(quán))ArcNode *nextarc; /指向下一條邊的指針指向下一條邊的指針;7.2.2 鄰接表表示法一、一、用用c語言描述圖的鄰接表存儲結(jié)構(gòu)及其操作語言描述圖的鄰接表存儲結(jié)構(gòu)及其操

33、作/頭結(jié)點(diǎn)頭結(jié)點(diǎn)-結(jié)構(gòu)體類型結(jié)構(gòu)體類型typedef struct VexNodechar data5;/頂點(diǎn)信息（字符串）頂點(diǎn)信息（字符串）ArcNode *firstarc;/指向第一條邊的指針指向第一條邊的指針VexNode;/圖圖-結(jié)構(gòu)體類型結(jié)構(gòu)體類型typedef structVexNode vexs100;/頂點(diǎn)的集合頂點(diǎn)的集合int vexnum,arcnum;/頂點(diǎn)的數(shù)目，邊的數(shù)目頂點(diǎn)的數(shù)目，邊的數(shù)目ALGraph;7.2.2 鄰接表表示法一、一、用用c語言描述圖的鄰接表存儲結(jié)構(gòu)及其操作語言描述圖的鄰接表存儲結(jié)構(gòu)及其操作 圖的基本操作包括圖的基本操作包括圖的初始化、查找頂點(diǎn)是否

34、存在、查找邊是否存在、圖的初始化、查找頂點(diǎn)是否存在、查找邊是否存在、插入一個頂點(diǎn)，插入一條邊，刪除一個頂點(diǎn)，刪除一插入一個頂點(diǎn)，插入一條邊，刪除一個頂點(diǎn)，刪除一條邊，求頂點(diǎn)的鄰接點(diǎn)等。條邊，求頂點(diǎn)的鄰接點(diǎn)等。 void InitGraph(ALGraph &mg)/圖的初始化圖的初始化mg.arcnum=mg.vexnum=0;for(int i=1;i100;i+)strcpy(mg.vexsi.data,);mg.vexsi.firstarc=0;int FindVex(ALGraph mg,char *vex)/查找頂點(diǎn)查找頂點(diǎn)vex是否存在是否存在for(int i=1;i=m

35、g.vexnum;i+)if(strcmp(mg.vexsi.data,vex)=0)return i;return 0; /不存在不存在int FindArc(ALGraph mg,char *v,char *w)/查找邊或弧查找邊或弧是否存在是否存在int v1=FindVex(mg,v);int w1=FindVex(mg,w);if(v1 *w1=0) return 0; /不存在不存在ArcNode *p=mg.vexsv1.firstarc; /表結(jié)點(diǎn)表結(jié)點(diǎn)pwhile(p)if(p-adjvex=w1) return 1;/找到了找到了p=p-nextarc; /指向下一條邊指向

36、下一條邊(下一個鄰接點(diǎn)下一個鄰接點(diǎn))return 0;/不存在不存在void InsertVex(ALGraph &mg,char *vex)/插入一個頂點(diǎn)插入一個頂點(diǎn)vexint v=FindVex(mg,vex);if(v!=0) return; /該頂點(diǎn)已經(jīng)存在該頂點(diǎn)已經(jīng)存在mg.vexnum+;strcpy(mg.vexsmg.vexnum .data,vex); return;void InsertArc(ALGraph &mg,char *v1,char *v2)/插入一條邊或弧插入一條邊或弧if(FindArc(mg,v1,v2)=0) /邊不存在邊不存在/此時我們假定頂點(diǎn)已經(jīng)存在此時我們假定頂點(diǎn)已經(jīng)存在ArcNode *p=new ArcNode; /定義表結(jié)點(diǎn)定義表結(jié)點(diǎn) /生成一個新的結(jié)點(diǎn)生成一個新的結(jié)點(diǎn) p-adjvex=FindVex(mg,v2);p-nextarc=0;p-weight=0;int v=FindVex(mg,v1); /新結(jié)點(diǎn)作為鏈表第一個結(jié)點(diǎn)新結(jié)點(diǎn)作為鏈表第一個結(jié)點(diǎn)p-nextarc=mg.vexsv.firstarc;mg.vexsv.firstarc=p;i