软件基础第三章非线性数据结构2

第三章非线性数据结构

"线性表

「A线性结构J栈

数

据&数据的逻辑结构d〔队

结

构-B非线性结构J树形结构

的Y

三［图形结构

个

方2、数据的存储结构［人顺序存储

面IB链式存储

(3、数据的运算：检索、排序、插入、删除、修改等。

N01

2011-7-4

3.2图结构

3.2.1图的定义和术语

'图(Graph)—图G是由两个集合V(G)和E(G)组成的，记为G=(V,E)

其中：

♦:*V(G)是顶点的非空有限集

♦:*E(G)是边的有限集合，边是顶点的无序对或有序对

例1：例2：

G1G2

2011-7-4

3.2图结构

3.2.1图的定义和术语

&有向图——有向图G是由两个集合V(G)和E(G)组成的

其中：V(G)是顶点的非空有限集

E(G)是有向边(也称弧)的有限集合，弧是顶点的有序

对，记为<v,w>,V,W是顶点，V为弧尾，W为弧头

例

图G1中：

V(G1)={1,2,3,456}

E(G1)={<1,2>,<2,1>,<2,3>,<2,4>?<3,5>,<5,6>,<6,3>}

N032011-7-4

3.2图结构

3.2.1图的定义和术语

'无向图——无向图G是由两个集合V(G)和E(G)组成的

其中：V(G)是顶点的非空有限集

E(G)是边的有限集合，边是顶点的无序对，记为(v,w)

或(叫V),并且(v,w)=(w,v)的］

图G2中：V(G2)={1,2,3,456,7}

E(G1尸{(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}

N042011-7-4

3.2图结构

3.2.1图的定义和术语

；」有向完全图----n个顶点的有向图最大边数是n(n・1)

&无向完全图——n个顶点的无向图最大边数是n(n-1)/2

例

有向完全图无向完全图

❖权-----与图的边或弧相关的数据信息叫权。

。网图------带权的图叫网图。

N052011-7-4

3.2图结构

3.2.1图的定义和术语

*子图——如果图G(V,E)和图G，(V'E)满足:

❖V9oV

OE七E

则称G，为G的子图

图与子图

N062011-7-4

3.2图结构

3.2.1图的定义和术语

&顶点的度

♦:♦无向图中，顶点的度TD(Vi)为与Vi顶点相连的边数

♦:♦有向图中，顶点的度分成入度ID(V)与出度OD(V)

A入度ID(V)：以该顶点为头的弧的数目

A出度OD(V)：以该顶点为尾的弧的数目

顶点5的度TD(5尸3顶点2入度ID(2)=1出度OD(2)=3

顶点2的度TD(2尸4顶点4入度ID(4)=1出度OD(4尸0

N072011-7-4

3.2图结构

3.2.1图的定义和术语

&顶点的度

♦:♦无向图中，顶点的度TD(Vi)为与Vi顶点相连的边数

♦:♦有向图中，顶点的度分成入度ID(V)与出度OD(V)

A入度ID(V)：以该顶点为头的弧的数目

A出度OD(V)：以该顶点为尾的弧的数目

卡对于具有n个顶点、e条边的图，顶点v的度TD(v)与顶点

的个数以及边的数目满足关系：(书139页有错，请改正)

e=(fTD(vi))/2

i=l

N082011-7-4

3.2图结构

3.2.1图的定义和术语

&路径——路径是顶点的序列V={ViO,V“……Vin},满足(VMM)£E

或<Vw,Vij>£E,(1<j«n)

及简单路径——序列中顶点不重复出现的路径叫简单路径。

&路径长度——沿路径边的数目或沿路径各边权值之和。

A回路——第一个顶点和最后一个顶点相同的路径叫回路。

以简单回路——除了第一个顶点和最后一个顶点外，其余顶点

不重复出现的回路叫简单回路。

路径:25

例1,

度

路径

长5

简单

径

路235

回路2563

•.

简单1,

路

回3593

G1

N092011-7-4

&连通——从顶点V到顶点W有一条路径，则说V和W是连通的。

&连通图——图中任意两个顶点都是连通的叫连通图。

&连通分量——非连通图的每一个连通部分叫连通分量。

&强连通图——有向图中，如果对每一对ViWViwVj,从Vi到Vj

和从Vj到Vi都存在路径，则称G是强连通图。

NO102011-7-4

♦：.生成树—连通图G的生成树是包含G中所有顶点的一个

极小连通子图，它有且仅有面条边。

特点：

1）任意两顶点间有且仅有一条路经

2）在生成树中添加任意一条属于G的边必定会产生回路

3）若生成树中减少任意一条边，则必然成为非连通图

连通图GG的生成树

N0112011-7-4

3.2图结构

3.2.2图的存储结构

「图中顶点的信息

图的信息包括两部分V

L边或弧的信息

图的存储结构应完整、准确地反映这两部分信息。

常用的存储方式有：

①邻接矩阵

②邻接表

③十字链表

N0122011-7-4

一、邻接矩阵

邻接矩阵存储结构是用一维数组存储图中顶点的信息，用

矩阵表示图中各顶点的邻接关系——表示顶点间相联关系的矩

阵。

♦:♦定义：设G=(V,E)是有仑1个顶点的图，G的邻接矩阵A是具

有以下性质的n阶方阵：

1,若Vj)或<vi?Vj>eE(G)

/忆刀=

o,其它

①②③④⑤

①0101o-

②10101

③01011

④10100

⑤01100

NO132011-7-4

一、邻接矩阵

邻接矩阵存储结构是用一维数组存储图中顶点的信息，用

矩阵表示图中各顶点的邻接关系——表示顶点间相联关系的矩

阵。

♦:♦定义：设G=(V,E)是有*1个顶点的图，G的邻接矩阵A是具

有以下性质的n阶方阵：

1,若(v「Vj)或<vi9v.>eE(G)

①②③④

N0142011-7-4

♦:♦若G=(V,E)是网图，贝IJG的邻接矩阵的元素值为边的权值。

%，(Vi，Vj),VVj>eE(G)

/必力=

00，其它

①②③④⑤

例

①0057oo3一

②5000048

③700821

④0042006

⑤L381600

N0152011-7-4

右邻接矩阵的特点:

♦:♦若G为无向图，贝ij：

A邻接矩阵A为对称矩阵，可压缩存储；有n个顶点的无向

图需存储空间为n(n+1)/2；

A第i行非0元素的个数为顶点Vi的度，TD(Vi)

①②③④⑤

①「o10101

②10101

③01011

TD(1)=2④10100

TD(2)=3⑤Lo1100

TD(3)=3

TD(4)=2

TD(5)=2

N0162011-7-4

*邻接矩阵的特点：

♦:♦若G为有向图，则:

A有向图邻接矩阵不一定对称；有n个顶点的有向图需存

1诸空间为1；

A顶点Vi的出度是A中第i行元素之和;

＞顶点Vi的入度是A中第i列元素之和。

①②③④

①ro110

②0000

③0001

ID(1)=1@Li000

OD(1)=2

N0172011-7-4

右邻接矩阵的特点：

♦:♦若G为无向图，贝IJ：

A邻接矩阵A为对称矩阵，可压缩存储；有n个顶点的无向

图需存储空间为n(n+1)/2；

A第i行非0元素的个数为顶点Vi的度，TD(Vi)o

♦:♦若G为有向图，贝IJ：

A有向图邻接矩阵不一定对称；有n个顶点的有向图需存

［诸空间为X；

＞顶点Vi的出度是A中第i行元素之和；

＞顶点Vi的入度是A中第i列元素之和。

・缺点：

统计图中边的总数时，需按行按列逐个检测、代价大。

N0182011-7-4

二、邻接表

♦:♦邻接表是一种顺序存储（顶点顺序表）与链式存储（边的单链

表）结合的存储方法，类似于树的孩子链表表示法。

typedefstructnode

{intadjvex;

structnode*next;

}JD;

adjvexnext

表头接点：

typedefstructtnode

{intvdata;

vdatafirst

structnode*first;

}TD;

TDga[M];

N0192011-7-4

二、邻接表

♦:♦邻接表是一种顺序存储（顶点顺序表）与链式存储（边的单

链表）结合的存储方法，类似于树的孩子链表示法。

vdatafirstadjvexnext

1a—24A

A

2b—1435

3c—2；45A

4

d—1.3A

5e—2.3A

NO202011-7-4

♦:♦特点

A无向图中顶点Vi的度为第i个单链表中的结点数

TD(a)=2

TD(b)=3

TD(c)=3

TD(d)=2

TD(e)=2

N0212011-7-4

二、邻接表

♦:♦邻接表是一种顺序存储（顶点顺序表）与链式存储（边的单

链表）结合的存储方法，类似于树的孩子链表示法。

vdatafirstadjvexnext

a—32A

bA

c4A

d1A

NO222011-7-4

♦:♦特点

A有向图中

来顶点Vi的出度为第i个单链表中的结点个数；

来顶点Vi的入度为整个单链表中邻接点域值是i的结点个数。

OD(a)=2

OD(b)=0

0D(c)=1

0D(d)=1

NO232011-7-4

♦:♦特点

A无向图中顶点Vi的度为第i个单链表中的结点数；

A有向图中

来顶点Vi的出度为第i个单链表中的结点个数；

来顶点Vi的入度为整个单链表中邻接点域值是i的结点个数。

I逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。

例ID(a)=1vdatafirstadjvexnext

—A

ID(b)=1a4

ID(c)=1b1A

ID(d)=1c—1A

d—3A

NO242011-7-4

323图的遍历

一、深度优先遍历(DFS)

♦:♦方法：从图的某一顶点Vo出发，访问此顶点；然后依次从

Vo的未被访问的邻接点出发，深度优先遍历图，直至图中

所有和Vo相通的顶点都被访问到；若此时图中尚有顶点未

被访问，则另选图中一个未被访问的顶点作起点，重复上

述过程，直至图中所有顶点都被访问为止。

例

假定从V1出发，遍历次序如何?

深度遍历:V?:nV4nV8-5^V3^V6^V7

NO252011-7-4

例

深度遍历：vx=>v2=>v4V8=>V5=>v6=>v3=>V7

NO262011-7-4

3.2.3图的遍历

二、广度优先遍历（BFS）

方法：从图的某一顶点V0出发，访问此顶点后，依次访

问V0的各个未曾访问过的邻接点；然后分别从这些邻接

点出发，广度优先遍历图，直至图中所有已被访问的顶

点的邻接点都被访问到；若此时图中尚有顶点未被访问

,则另选图中一个未被访问的顶点作起点，重复上述过

程，直至图中所有顶点都被访问为止。

广度遍历：V1=>V2nV3=>

V4=>V5=>V6nV7=>V8

NO272011-7-4

广度遍历：VinV2nV3=>V4nV5nV6

nV7nV8

NO282011-7-4

6.4生成树

I♦:♦定义：所有顶点均由边连接在一起，但不存在回路的图叫〜

I♦:♦深度优先生成树与广度优先生成树

I♦:♦生成森林：非连通图每个连通分量的生成树一起组成非连通

图的〜

I♦:♦说明

A一个图可以有许多棵不同的生成树©

»所有生成树具有以下共同特点：0x70

来生成树的顶点个数与图的顶点个数相同T/

来生成树是图的极小连通子图@

来一个有n个顶点的连通图的生成树有n・1条边

来生成树中任意两个顶点间的路径是唯一的

来在生成树中再加一条边必然形成回路

s”》含n个顶点面条边的图不一定是生成树

NO292011.7.4

广度优先生成树

深度优先生成树

NO302011-7-4

例

B深度优先生成森林

N0312011-7-4

♦:♦最小生成树

A问题提出

要在n个城市间建立通信联络网，

顶点——表示城市

权—城市间建立通信线路所需花费代价

希望找到一棵生成树，它的每条边上的权值之和（即建立

该通信网所需花费的总代价）最小-----最小代价生成树

问题分析

n个城市间，最多可设置n（n・l）/2条线路

n个城市间建立通信网，只需n・l条线路

问题转化为：如何在可能的线路中选择n・l条，能把

所有城市（顶点）均连起来，且总耗费

（各边权值之和）最小

NO322011-7-4

A构造最小生成树方法

来方法一：普里姆(Prim)算法

》算法思想：设N=(V,{E})是连通网，TE是N上

最小生成树中边的集合

初始令U={llo},(UowV),TE=O>

在所有U£U,V£V・U的边(U,V)£E中，找一条

代价最小的边(uO,vO)

将(uO,vO)并入集合TE,同时vO并入U

重复上述操作直至U=V为止，贝|JT=(V,{TE})

为N的最小生成树

NO332011-7-4

崇方法二：克鲁斯卡尔(Kruskal)算法

》算法思想：设连通网N=(V,{E}),令最小生成树

初始状态为只有n个顶点而无边的非连通图

T=(V,{<D}),每个顶点自成一个连通分量

在E中选取代价最小的边，若该边依附的顶点落在T中不

同的连通分量上，则将此边加入到T中；否则，舍去此

边，选取下一条代价最小的边

依此类推，直至T中