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

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

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

:n

）設計為鄰鏈式存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)：無！

（多個頂點，無序可言）

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

接矩陣

?

鄰接表

?

鄰接多重表

?

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

]

][

[

.

A

j

i

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

如果

<

i,

j

>E

或者

(i,

j)E0,

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

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

v5v1v4A

頂點表：

（

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頁，當前為第3頁。

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

=(

v1

v2

v3

v4

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

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

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

1

00

0100

0001

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

Vi

)=

A.Edge[

i

][j

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

Vi

)=

A.Edge[

j

][i

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

Vi

)

+

ID(

Vi

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

5

∞

∞

7

∞

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

A.Edge[

i

][

j

]=Wij

∞<vi,

vj>

或（vi,

vj）∈VR

無邊（弧）v2v4Nv1

v54

v3

8955

576

3v6

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

∞

∞

4

∞

∞

∞

N.Edge

=

8

∞

∞

∞

∞

9

∞

∞

5

∞

∞

6

∞

∞

∞

5

∞

∞

3

∞

∞

∞

1

∞頂點表：

(

v1

v2

v3

v4

v5

v6

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

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

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

注：用兩個數(shù)組分別存儲頂點表和鄰接矩陣#define

INFINITY

INT_MAX#define

MAX_VERTEX_NUM

//最大值∞20

//假設的最大頂點數(shù)Typedef

enum

{DG,

DN,AG,AN

}

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

struct

ArcCell{//?。ㄟ叄┙Y(jié)點的定義VRTypeadj;//頂點間關(guān)系，無權(quán)圖取1或0；有權(quán)圖取權(quán)值類型

InfoType

*info;

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

[

MAX_VERTEX_NUM

]

[MAX_VERTEX_NUM

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

struct{//圖的定義VertexType

vexs

[MAX_VERTEX_NUM

]

;

//頂點表，用一維向量即可AdjMatrix

arcs;//鄰接矩陣int

Vernum,

arcnum;

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

kind;//圖的種類標志}Mgraph;

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

表結(jié)點

Adjvex鄰接點域，表示vi一個鄰接點的位置nextarc

鏈域，指向

vi下一個邊

或弧的結(jié)點info

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

邊有關(guān)信息

（如權(quán)值）

data數(shù)據(jù)域，存儲頂點vi

信息firstarc

鏈域，指向

單鏈表的第

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

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

v1v3v2v4V1V2

^V3V423

^0

^1

^鄰接表(出邊)V1V2V3V43

^0

^0

^2

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

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

區(qū)別：

①

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

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

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

MAX_VERTEX_NUM

20

//假設的最大頂點數(shù)Typedef

struct

ArcNode

{int

adjvex;

//該弧所指向的頂點位置struct

ArcNode

*nextarcs;

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

*info;

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

struct

VNode{

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

data;

//頂點信息ArcNode

*

firstarc;

//指向依附該頂點的第一條弧的指針}VNode,AdjList[

MAX_VERTEX_NUM

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

struct

{

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

AdjList

vertics

;

//應包含鄰接表int

vexnum,

arcnum;

//應包含頂點總數(shù)和弧總數(shù)int

kind;

//還應說明圖的種類（用標志）}ALGraph;

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

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

V0V110100

30

10

5

60

V4

20

V350V5V2始點

終點

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和源點v,

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

第4講：最短路徑

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

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

1

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

w

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

取D[v]和D[w]+cost[w][v]中值較小的作為新的D[v]重復上述，直到S中包含V中其余各頂點的最短路徑。第4講：最短路徑數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁，當前為第20頁。第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頁，當前為第21頁。

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)終點

V1

V2

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

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

0

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

vi≠vj，要求求出每一對頂點之間的最短路徑和最短路徑長度。解決方案：

1.

每次以一個頂點為源點，重復執(zhí)行迪杰斯特拉算法n次。這樣，便可求得每一對頂點之間的最短路徑?？偟膱?zhí)行時間為O(n3)。2.

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

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

Vi到Vj

的中間頂點的序號不大于0

的最短路徑。假如在路徑上再增加一個頂點

V1，…依次類推。可同時求得各對頂點間的最短路徑。第4講：最短路徑數(shù)據(jù)結(jié)構(gòu)與算法---圖-全文共26頁，當前為第24頁。定義一個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]=