数据结构与算法-图-

第2讲：图的存储结构

图的特点：非线性结构（m

:n

）设计为邻链式存储结构：顺序存储结构：无！

（多个顶点，无序可言）

但可用数组描述元素间关系。可用多重链表

接矩阵

•

邻接表

•

邻接多重表

•

十字链表重点介绍：数据结构与算法---图-全文共26页，当前为第1页。

]

][

[

.

A

j

i

Edge第2讲：图的存储结构1,

如果

<

i,

j

>E

或者

(i,

j)E0,

否则数据结构与算法---图-全文共26页，当前为第2页。A.Edge

=第1讲：图的存储结构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数据结构与算法---图-全文共26页，当前为第3页。

第2讲：图的存储结构例2：有向图的邻接矩阵v1v2v3v4邻接矩阵：A.Edge

=(

v1

v2

v3

v4

)v1v2v3v4注：在有向图的邻接矩阵中，

第i行含义：以结点vi为尾的弧(即出度边）；

第i列含义：以结点vi为头的弧(即入度边）。顶点表：0001

1

00

0100

0001

0数据结构与算法---图-全文共26页，当前为第4页。第2讲：图的存储结构分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点的出度=第i行元素之和，OD(

Vi

)=

A.Edge[

i

][j

]顶点的入度=第i列元素之和。ID(

Vi

)=

A.Edge[

j

][i

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

Vi

)

+

ID(

Vi

)数据结构与算法---图-全文共26页，当前为第5页。∞

5

∞

∞

7

∞

第2讲：图的存储结构特别讨论：网（即有权图）的邻接矩阵定义为：

A.Edge[

i

][

j

]=Wij

∞<vi,

vj>

或（vi,

vj）∈VR

无边（弧）v2v4Nv1

v54

v3

8955

576

3v6

1以有向网为例：邻接矩阵：

∞

∞

4

∞

∞

∞

N.Edge

=

8

∞

∞

∞

∞

9

∞

∞

5

∞

∞

6

∞

∞

∞

5

∞

∞

3

∞

∞

∞

1

∞顶点表：

(

v1

v2

v3

v4

v5

v6

)数据结构与算法---图-全文共26页，当前为第6页。第2讲：图的存储结构邻接矩阵法优点：邻接矩阵法缺点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。

对稀疏图而言尤其浪费空间。数据结构与算法---图-全文共26页，当前为第7页。

第2讲：图的存储结构图的邻接矩阵存储表示（参见教材P161）

注：用两个数组分别存储顶点表和邻接矩阵#define

INFINITY

INT_MAX#define

MAX_VERTEX_NUM

//最大值∞20

//假设的最大顶点数Typedef

enum

{DG,

DN,AG,AN

}

GraphKind;//有向/无向图，有向/无向网Typedef

struct

ArcCell{//弧（边）结点的定义VRTypeadj;//顶点间关系，无权图取1或0；有权图取权值类型

InfoType

*info;

//该弧相关信息的指针}ArcCell,AdjMatrix

[

MAX_VERTEX_NUM

]

[MAX_VERTEX_NUM

];数据结构与算法---图-全文共26页，当前为第8页。第2讲：图的存储结构Typedef

struct{//图的定义VertexType

vexs

[MAX_VERTEX_NUM

]

;

//顶点表，用一维向量即可AdjMatrix

arcs;//邻接矩阵int

Vernum,

arcnum;

//顶点总数，弧（边）总数GraphKind

kind;//图的种类标志}Mgraph;

对于n个顶点的图或网，空间效率=O(n2)数据结构与算法---图-全文共26页，当前为第9页。第2讲：图的存储结构

表结点

Adjvex邻接点域，表示vi一个邻接点的位置nextarc

链域，指向

vi下一个边

或弧的结点info

数据域，与

边有关信息

（如权值）

data数据域，存储顶点vi

信息firstarc

链域，指向

单链表的第

一个结点数据结构与算法---图-全文共26页，当前为第10页。v1v2v3v4v5第2讲：图的存储结构v3v2

v5v1v401234^23^134441232^^^010数据结构与算法---图-全文共26页，当前为第11页。第2讲：图的存储结构

v1v3v2v4V1V2

^V3V423

^0

^1

^邻接表(出边)V1V2V3V43

^0

^0

^2

^逆邻接表(入边)数据结构与算法---图-全文共26页，当前为第12页。第2讲：图的存储结构讨论：邻接表与邻接矩阵有什么异同之处？1.

联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.

区别：

①

对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。②

邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.

用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（e<<n2)数据结构与算法---图-全文共26页，当前为第13页。第2讲：图的存储结构图的邻接表存储表示（参见教材P163）#define

MAX_VERTEX_NUM

20

//假设的最大顶点数Typedef

struct

ArcNode

{int

adjvex;

//该弧所指向的顶点位置struct

ArcNode

*nextarcs;

//指向下一条弧的指针InfoArc

*info;

//该弧相关信息的指针}ArcNode；Typedef

struct

VNode{

//顶点结构VertexType

data;

//顶点信息ArcNode

*

firstarc;

//指向依附该顶点的第一条弧的指针}VNode,AdjList[

MAX_VERTEX_NUM

];数据结构与算法---图-全文共26页，当前为第14页。第2讲：图的存储结构Typedef

struct

{

//图结构

AdjList

vertics

;

//应包含邻接表int

vexnum,

arcnum;

//应包含顶点总数和弧总数int

kind;

//还应说明图的种类（用标志）}ALGraph;

//图结构数据结构与算法---图-全文共26页，当前为第15页。第4讲：最短路径

所谓最短路径问题是指：如果从图中某一顶点（称为源点）出发到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和达到最小。1.单源点最短路径2.所有顶点对之间的最短路径数据结构与算法---图-全文共26页，当前为第16页。

V0V110100

30

10

5

60

V4

20

V350V5V2始点

终点

V0

V1

V2

V3

V4

V560

∞D[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讲：最短路径

给定带权有向图G和源点v,

求从v到G中其余各顶点的最短路径。数据结构与算法---图-全文共26页，当前为第17页。第4讲：最短路径如何在计算机中求得最短路径？数据结构与算法---图-全文共26页，当前为第18页。

第4讲：最短路径

Dijkstra提出了一个按路径“长度”递增的次序，逐步得到由给定源点到图的其余各点间的最短路径的算法：nn假设我们以邻接矩阵cost表示所研究的有向网。迪杰斯特拉算法需要一个顶点集合，初始时集合内只有一个源点V0

，以后陆续将已求得最短路径的顶点加入到集合中，到全部顶点都进入集合了，过程就结束了。集合可用一维数组来表示，设此数组为S，凡在集合S以外的顶点，其相应的数组元素S[i]为0，否则为

1

。数据结构与算法---图-全文共26页，当前为第19页。nnn另需一个一维数组D，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，其初值为D[i]=cost[V0][i]，i=1…n。数组D中的数据随着算法的逐步进行要不断地修改定义了S集合和D数组并对其初始化后，迪杰斯特拉算法在进行中，都是从S之外的顶点集合中选出一个顶点w，使D[w]的值最小。于是从源点到达w只通过S中的顶点，把

w

加入集合S中，并调整D中记录的从源点到集合中每个顶点v的距离：

取D[v]和D[w]+cost[w][v]中值较小的作为新的D[v]重复上述，直到S中包含V中其余各顶点的最短路径。第4讲：最短路径数据结构与算法---图-全文共26页，当前为第20页。第4讲：最短路径V0V1V2V3V4V5

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

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

V5100

∞

∞

10

60

∞V25

V5

30101050

100V0

V160

V4

20V3数据结构与算法---图-全文共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终点

V1

V2

V3第4讲：最短路径数据结构与算法---图-全文共26页，当前为第22页。问题描述：

已知一个各边权值均大于

0

的带权有向图，对每对顶点

vi≠vj，要求求出每一对顶点之间的最短路径和最短路径长度。解决方案：

1.

每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。这样，便可求得每一对顶点之间的最短路径。总的执行时间为O(n3)。2.

形式更直接的弗洛伊德（Floyd）算法。时间复杂度也为O(n3)。2、所有顶点对之间的最短路径第4讲：最短路径数据结构与算法---图-全文共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讲：最短路径数据结构与算法---图-全文共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]=