数据结构之图论.ppt

第四章图结构
困的基本概念
的存储
困的追历
图的定义、术语

■图是由非空的顶点组成的有限集和边的有限集组成。
■二元组G=(V,E)
·V:顶点集合
·E;边的集合,即顶点间的关系
■图结构中的美系可以是任意的,甚至可以是空集
·图是一种对结点的前驱和后继个教不加限制的教据结构
图的术语
1)有向图与无向图
>由有向边组成的图,称为有向图
>有向边以<Ⅹ,Y>表示,又称为弧
·X:弧尾
·Y:孤头
>有向边<X,Y>与<Y,X>不是同一条边
由无向边组成的图,称为无向图
无向边以(X,Y)表示
无向边(X,Y)与(Y,Ⅹ)是同一条边
图的术语
2)权与网
图中边或弧所具有的相关数称为权
般用于表明从一个顶点到另一个顶点的源离或耗
费
13
带权的图称为网
3)邻接与顶点的度
对于(X,Y)∈E则Ⅹ,Y互为邻接
对于<X,Y>∈E则Y是Ⅹ的邻接结点
图的术语
出度:以该顶点为弧尾的弧数
顶点图:入度:以该顶点为弧头的弧数
和
顶点度为
无向图:顶点的边数
总边数-1各顶点度之和-1∑D(Ⅵ
·给出以下顶点的度
图的术语
4)路径与回路
■路径:图中沿着各条边,从X到Y所经历的顶点
序列称为路径
·路径:X,b,a,Y
■环:第一顶点与最后一个顶点相同的路径
环
环:X,a,Y,b,X
回路
序列中不出现重复的路径称为筒单路径
·有重复的路径称为回路
回路:X,a,b,a,Y
图的术语
5)连通、连通图与连通分量
■连通;在图中若X与Y之间有路径,则称X,Y
是连通的
■连通图:任意两个顶点都连通的图称为连通图
■没有孤立顶点
■连通分量:指无向图中极大连通子图,即有多
少个连通子图
88◎
x图的存储接矩阵


(1)给顶点编号
1(22立年接(关表示弧<b,j>
000+9
1:表示有弧;0:表示无弧
10
234
1001
0110
任意顶点的出度是该行元素之和
任意顶点的入度是该列元素之和
图的存储郐接矩阵

1234
10110
2101
1101
无向图的邻接矩阵是对称的
40110
■若边<<顶点则邻接矩阵为稀疏矩阵。
■邻接矩阵的优点:增减边的操作简单
■邻接矩阵的缺点:
增减顶点的操作需要搬移大量的元素,
≯浪费存储空间
图的存储邹接矩阵的实现
pedar解越智陆
elemtype node MAxNUM
顶点集合
int arcs MAXNU№ IAXNUM∶边的邻接矩阵
igraph m
二维数组