數(shù)據(jù)結(jié)構(gòu)與算法-圖-

第2講：圖的存儲(chǔ)結(jié)構(gòu)

圖的特點(diǎn)：非線性結(jié)構(gòu)（m

:n

）設(shè)計(jì)為鄰鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)：無(wú)！

（多個(gè)頂點(diǎn)，無(wú)序可言）

但可用數(shù)組描述元素間關(guān)系?？捎枚嘀劓湵?/p>

接矩陣

?

鄰接表

?

鄰接多重表

?

十字鏈表重點(diǎn)介紹：數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第1頁(yè)。

]

][

[

.

A

j

i

Edge第2講：圖的存儲(chǔ)結(jié)構(gòu)1,

如果

<

i,

j

>E

或者

(i,

j)E0,

否則數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第2頁(yè)。A.Edge

=第1講：圖的存儲(chǔ)結(jié)構(gòu)v3v2

v5v1v4A

頂點(diǎn)表：

（

v1

v2

v3

v4

v5

）鄰接矩陣：

0

1

0

1

0

v1

1

0

1

0

1

v2

0

1

0

1

1

v3

1

0

1

0

1

v4

0

1

1

1

0

v5數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第3頁(yè)。

第2講：圖的存儲(chǔ)結(jié)構(gòu)例2：有向圖的鄰接矩陣v1v2v3v4鄰接矩陣：A.Edge

=(

v1

v2

v3

v4

)v1v2v3v4注：在有向圖的鄰接矩陣中，

第i行含義：以結(jié)點(diǎn)vi為尾的弧(即出度邊）；

第i列含義：以結(jié)點(diǎn)vi為頭的弧(即入度邊）。頂點(diǎn)表：0001

1

00

0100

0001

0數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第4頁(yè)。第2講：圖的存儲(chǔ)結(jié)構(gòu)分析1：有向圖的鄰接矩陣可能是不對(duì)稱(chēng)的。分析2：頂點(diǎn)的出度=第i行元素之和，OD(

Vi

)=

A.Edge[

i

][j

]頂點(diǎn)的入度=第i列元素之和。ID(

Vi

)=

A.Edge[

j

][i

]頂點(diǎn)的度=第i行元素之和+第i列元素之和,即：TD(Vi)=OD(

Vi

)

+

ID(

Vi

)數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第5頁(yè)?！?/p>

5

∞

∞

7

∞

第2講：圖的存儲(chǔ)結(jié)構(gòu)特別討論：網(wǎng)（即有權(quán)圖）的鄰接矩陣定義為：

A.Edge[

i

][

j

]=Wij

∞<vi,

vj>

或（vi,

vj）∈VR

無(wú)邊（?。﹙2v4Nv1

v54

v3

8955

576

3v6

1以有向網(wǎng)為例：鄰接矩陣：

∞

∞

4

∞

∞

∞

N.Edge

=

8

∞

∞

∞

∞

9

∞

∞

5

∞

∞

6

∞

∞

∞

5

∞

∞

3

∞

∞

∞

1

∞頂點(diǎn)表：

(

v1

v2

v3

v4

v5

v6

)數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第6頁(yè)。第2講：圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣法優(yōu)點(diǎn)：鄰接矩陣法缺點(diǎn)：容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（弧）、找頂點(diǎn)的鄰接點(diǎn)等等。n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊(弧);空間效率為O(n2)。

對(duì)稀疏圖而言尤其浪費(fèi)空間。數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第7頁(yè)。

第2講：圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接矩陣存儲(chǔ)表示（參見(jiàn)教材P161）

注：用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣#define

INFINITY

INT_MAX#define

MAX_VERTEX_NUM

//最大值∞20

//假設(shè)的最大頂點(diǎn)數(shù)Typedef

enum

{DG,

DN,AG,AN

}

GraphKind;//有向/無(wú)向圖，有向/無(wú)向網(wǎng)Typedef

struct

ArcCell{//弧（邊）結(jié)點(diǎn)的定義VRTypeadj;//頂點(diǎn)間關(guān)系，無(wú)權(quán)圖取1或0；有權(quán)圖取權(quán)值類(lèi)型

InfoType

*info;

//該弧相關(guān)信息的指針}ArcCell,AdjMatrix

[

MAX_VERTEX_NUM

]

[MAX_VERTEX_NUM

];數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第8頁(yè)。第2講：圖的存儲(chǔ)結(jié)構(gòu)Typedef

struct{//圖的定義VertexType

vexs

[MAX_VERTEX_NUM

]

;

//頂點(diǎn)表，用一維向量即可AdjMatrix

arcs;//鄰接矩陣int

Vernum,

arcnum;

//頂點(diǎn)總數(shù)，?。ㄟ叄┛倲?shù)GraphKind

kind;//圖的種類(lèi)標(biāo)志}Mgraph;

對(duì)于n個(gè)頂點(diǎn)的圖或網(wǎng)，空間效率=O(n2)數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第9頁(yè)。第2講：圖的存儲(chǔ)結(jié)構(gòu)

表結(jié)點(diǎn)

Adjvex鄰接點(diǎn)域，表示vi一個(gè)鄰接點(diǎn)的位置nextarc

鏈域，指向

vi下一個(gè)邊

或弧的結(jié)點(diǎn)info

數(shù)據(jù)域，與

邊有關(guān)信息

（如權(quán)值）

data數(shù)據(jù)域，存儲(chǔ)頂點(diǎn)vi

信息firstarc

鏈域，指向

單鏈表的第

一個(gè)結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第10頁(yè)。v1v2v3v4v5第2講：圖的存儲(chǔ)結(jié)構(gòu)v3v2

v5v1v401234^23^134441232^^^010數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第11頁(yè)。第2講：圖的存儲(chǔ)結(jié)構(gòu)

v1v3v2v4V1V2

^V3V423

^0

^1

^鄰接表(出邊)V1V2V3V43

^0

^0

^2

^逆鄰接表(入邊)數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第12頁(yè)。第2講：圖的存儲(chǔ)結(jié)構(gòu)討論：鄰接表與鄰接矩陣有什么異同之處？1.

聯(lián)系：鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。2.

區(qū)別：

①

對(duì)于任一確定的無(wú)向圖，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號(hào)無(wú)關(guān)）。②

鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。3.

用途：鄰接矩陣多用于稠密圖的存儲(chǔ)（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲(chǔ)（e<<n2)數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第13頁(yè)。第2講：圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表存儲(chǔ)表示（參見(jiàn)教材P163）#define

MAX_VERTEX_NUM

20

//假設(shè)的最大頂點(diǎn)數(shù)Typedef

struct

ArcNode

{int

adjvex;

//該弧所指向的頂點(diǎn)位置struct

ArcNode

*nextarcs;

//指向下一條弧的指針I(yè)nfoArc

*info;

//該弧相關(guān)信息的指針}ArcNode；Typedef

struct

VNode{

//頂點(diǎn)結(jié)構(gòu)VertexType

data;

//頂點(diǎn)信息ArcNode

*

firstarc;

//指向依附該頂點(diǎn)的第一條弧的指針}VNode,AdjList[

MAX_VERTEX_NUM

];數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第14頁(yè)。第2講：圖的存儲(chǔ)結(jié)構(gòu)Typedef

struct

{

//圖結(jié)構(gòu)

AdjList

vertics

;

//應(yīng)包含鄰接表int

vexnum,

arcnum;

//應(yīng)包含頂點(diǎn)總數(shù)和弧總數(shù)int

kind;

//還應(yīng)說(shuō)明圖的種類(lèi)（用標(biāo)志）}ALGraph;

//圖結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第15頁(yè)。第4講：最短路徑

所謂最短路徑問(wèn)題是指：如果從圖中某一頂點(diǎn)（稱(chēng)為源點(diǎn)）出發(fā)到達(dá)另一頂點(diǎn)（稱(chēng)為終點(diǎn)）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊的權(quán)值總和達(dá)到最小。1.單源點(diǎn)最短路徑2.所有頂點(diǎn)對(duì)之間的最短路徑數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第16頁(yè)。

V0V110100

30

10

5

60

V4

20

V350V5V2始點(diǎn)

終點(diǎn)

V0

V1

V2

V3

V4

V560

∞D(zhuǎn)[i]

∞

10

50

30

10060

900,0,4,2)0,0,4

2,4)0,

,

4,

)最短路徑

(V0,

V2)

(V

(VVVV3)

(V

(VVVV3)

(V

(V0VV4V3,

(V

(VV5VV5)0,0,4

)

,5)第4講：最短路徑

給定帶權(quán)有向圖G和源點(diǎn)v,

求從v到G中其余各頂點(diǎn)的最短路徑。數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第17頁(yè)。第4講：最短路徑如何在計(jì)算機(jī)中求得最短路徑？數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第18頁(yè)。

第4講：最短路徑

Dijkstra提出了一個(gè)按路徑“長(zhǎng)度”遞增的次序，逐步得到由給定源點(diǎn)到圖的其余各點(diǎn)間的最短路徑的算法：nn假設(shè)我們以鄰接矩陣cost表示所研究的有向網(wǎng)。迪杰斯特拉算法需要一個(gè)頂點(diǎn)集合，初始時(shí)集合內(nèi)只有一個(gè)源點(diǎn)V0

，以后陸續(xù)將已求得最短路徑的頂點(diǎn)加入到集合中，到全部頂點(diǎn)都進(jìn)入集合了，過(guò)程就結(jié)束了。集合可用一維數(shù)組來(lái)表示，設(shè)此數(shù)組為S，凡在集合S以外的頂點(diǎn)，其相應(yīng)的數(shù)組元素S[i]為0，否則為

1

。數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第19頁(yè)。nnn另需一個(gè)一維數(shù)組D，每個(gè)頂點(diǎn)對(duì)應(yīng)數(shù)組的一個(gè)單元，記錄從源點(diǎn)到其他各頂點(diǎn)當(dāng)前的最短路徑長(zhǎng)度，其初值為D[i]=cost[V0][i]，i=1…n。數(shù)組D中的數(shù)據(jù)隨著算法的逐步進(jìn)行要不斷地修改定義了S集合和D數(shù)組并對(duì)其初始化后，迪杰斯特拉算法在進(jìn)行中，都是從S之外的頂點(diǎn)集合中選出一個(gè)頂點(diǎn)w，使D[w]的值最小。于是從源點(diǎn)到達(dá)w只通過(guò)S中的頂點(diǎn)，把

w

加入集合S中，并調(diào)整D中記錄的從源點(diǎn)到集合中每個(gè)頂點(diǎn)v的距離：

取D[v]和D[w]+cost[w][v]中值較小的作為新的D[v]重復(fù)上述，直到S中包含V中其余各頂點(diǎn)的最短路徑。第4講：最短路徑數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第20頁(yè)。第4講：最短路徑V0V1V2V3V4V5

V0∞∞∞∞∞∞V1∞∞∞∞∞∞

V2105∞∞∞∞V3∞∞50∞20∞V430∞∞∞∞∞

V5100

∞

∞

10

60

∞V25

V5

30101050

100V0

V160

V4

20V3數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第21頁(yè)。

V1{V0,V2,V4,V3,V5

,V1}

V5{V0,V2,V4,V3,V5}

V3{V0,V2,V4,V3}

V4{V0,V2,V4}

V2{V0,V2}

VjS={V0}V4V53060

3060{V0,4,3,5}

3090{V0,4,5}30{V0,4}

30{V0,4}100{V0,5}

100{V0,5}i=5

∞

10

50i=4

∞

10

50

i=3

∞

1050{V0,4,3}

i=2

∞

1060{V0,2,3}

i=1

∞10{V0,2}

∞D(zhuǎn)終點(diǎn)

V1

V2

V3第4講：最短路徑數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第22頁(yè)。問(wèn)題描述：

已知一個(gè)各邊權(quán)值均大于

0

的帶權(quán)有向圖，對(duì)每對(duì)頂點(diǎn)

vi≠vj，要求求出每一對(duì)頂點(diǎn)之間的最短路徑和最短路徑長(zhǎng)度。解決方案：

1.

每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行迪杰斯特拉算法n次。這樣，便可求得每一對(duì)頂點(diǎn)之間的最短路徑。總的執(zhí)行時(shí)間為O(n3)。2.

形式更直接的弗洛伊德（Floyd）算法。時(shí)間復(fù)雜度也為O(n3)。2、所有頂點(diǎn)對(duì)之間的最短路徑第4講：最短路徑數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第23頁(yè)。弗洛伊德算法思想：

假設(shè)求從頂點(diǎn)Vi到Vj的最短路徑。如果從Vi到Vj有弧，則從Vi到Vj存在一條長(zhǎng)度為arcs[i][j]的路徑，該路徑不一定是最短路徑，尚需進(jìn)行n次試探。首先考慮路徑（Vi,V0,Vj）是否存在（即判別（Vi,V0）、（V0,Vj）是否存在）。如存在，則比較（Vi,Vj）和（Vi,V0,Vj）的路徑長(zhǎng)度，取長(zhǎng)度較短者為從

Vi到Vj

的中間頂點(diǎn)的序號(hào)不大于0

的最短路徑。假如在路徑上再增加一個(gè)頂點(diǎn)

V1，…依次類(lèi)推。可同時(shí)求得各對(duì)頂點(diǎn)間的最短路徑。第4講：最短路徑數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁(yè)，當(dāng)前為第24頁(yè)。定義一個(gè)n階方陣序列D(-1),D(0),D(1),D(2),…,D(k),…,D(n-1)其中：

D(-1)[i][j]=

arcs[i][j]

D(k)[i][j]=