PPT《7.1 图的抽象数据类型定义》

7.

1 图的抽象数据类型定义 7.2 图的存储表示 7.3 图的遍历 7.4 最小生成树 7.7 两点之间的最短路径问题 7.5 拓扑排序 7.6 关键路径 7.1 图的抽象数据类型定义

一、图的结构定义

二、名词和术语

三、基本操作 图是由一个顶点集 V 和一个弧集 VR构成的数据结构.Graph = (V, VR )其中,VR={| v,w∈V 且P(v,w)} 表示从 v 到w的一条弧,并称 v 为弧尾,w 为弧头. 谓词 P(v,w) 定义了弧 的意义或信息.

一、图的结构定义 V是顶点的有穷非空集合,VR是两顶点间关系的集合. v w 由于 弧 是有方向的,因此称由顶点集和弧集构成的图为有向图. E A C B D 例如: G1 = (V1, VR1) 其中V1={A, B, C, D, E}VR1={, , , , , , }

二、名词和术语 1.有向图: 若?VR 必有?VR, 即VR是对称的,则以无序对(v,w)代替这两个有序对,称顶点 v 和顶点 w 之间存在一条边(v,w) . B C A F E D 由顶点集和边集构成的图称作无向图. 例如: G2=(V2,VR2)V2={A, B, C, D, E, F}VR2={(A, B), (A, E)B, E), (C, D), (D, F)B, F), (C, F) } 3.边: 2.无向图: A B E C F A E F B B C 设图G=(V, VR) 和图G?=(V?, VR?),且V??V, VR??VR,则称 G? 为G的子图.

15 9

7 21

11 3

2 弧或边带权的图分别称作有向网或无向网. 4. 子图: 5. 有向网,无向网: 完全图假设图中有 n 个顶点,e 条边, 如果e=n(n-1)/2 ,则该无向图为完全图. 有向完全图 将含有 e=n(n-1) 条弧的有向图 称作有向完全图. 稀疏图:如果边或弧的个数满足 e <

n log n, 则称作稀疏图,否则称作稠密图. 6. 完全图、稀疏图、稠密图: 邻接点:假若顶点v 和顶点w 之间存在一条边,则称顶点 v 和w互为邻接点, 例如: TD(B) =

3 TD(A) =

2 度:与顶点v 关联的边的数目,记为TD(v). A C D F E B 7.邻接点、度 对无向图来说, 顶点的出度: 以顶点v 为弧尾的弧的数目,记为OD(v);

A B E C F 对有向图来说, 顶点的入度: 以顶点v为弧头的弧的数目,记为ID(v). 有向图中顶点的:度(TD)=出度(OD)+入度(ID) 例如: I D(B) =

2 OD(B) =

1 TD(B) =

3 由于弧有方向性,则有入度和出度之分 8.入度、出度 设图G=(V,VR)中的一个顶点序列{ u=vi,0,vi,1, …, vi,m=w}中,(vi,j-1,vi,j)?VR ,1≤j≤m,则称从顶点u 到顶点w 之间存在一条路径.路径上边的数目称作路径长度. A B E C F 如:从A到F长度为3的路径: 简单路径:指序列中顶点不重复出现的路径. 简单回路:指序列中第一个顶点和最后一个顶点相同,且除此之外序列中顶点不重复出现的路径. 9. 路径、路径长度、简单路径、简单回路 ABC ABCFB {A,B,C,F}和{A,E,C,F} BCFB 若无向图中任意两个顶点之间都有路径相通,则称此图为连通图;

若无向图为非连通图,则图中各个连通子图称作此图的连通分量. 10. 连通图、连通分量 B A C D F E G1 B A C D F E G2 若任意两个顶点之间都存在一条有向路径,则称此有向图为强连通图. A B E C F A B E C F 对有向图, 否则,其各个强连通子图称作它的强连通分量. 11. 强连通图、强连通分量 假设一个连通图有 n 个顶点和 e 条边,其中 n 个顶点和n-1 条边 构成一个极小连通子图,称该极小连通子图为此连通图的生成树. B A C D F E 12. 生成树 B A C D F E B A C D F E B A C D F E 若在一棵生成树任添加一条边,则?. 则必定构成一个环,因为新添加的边必使得依附于这条边的两个顶点之间有了第二条路经. 一棵有n个顶点的生成树有且仅有?边 若少于n-1条边,则非连通;

若多于n-1条边,则必有环. 对非连通图,则称由各个连通分量生成树的集合为此非连通图的生成森林. 13. 生成森林 B A E E C D F 非连通图 B A E E C D F 生成森林 1. 结构的建立和销毁 3. 插入或删除顶点 5. 对邻接点的操作 2. 对顶点的访问操作 6. 遍历 4. 插入和删除弧

三、基本操作 CreatGraph(&

G, V, VR): // 按定义(V, VR) 构造图 DestroyGraph(&

G): // 销毁图 1. 结构的建立和销毁 2. 对顶点的访问操作 LocateVex(G, u);

// 若G中存在顶点u,则返回该顶点在 // 图中 位置 ;

否则返回其它信息. GetVex(G, v)返回 v 的值. PutVex(&

G, v, value);

// 对v赋值value. 3. 对邻接点的操作 FirstAdjVex(G, v);

// 返回 v 的 第一个邻接点 .若该顶点//在G中没有邻接点,则返回 空 . NextAdjVex(G, v, w);

// 返回 v 的(相对于 w 的) 下一个邻接// 点 .若w是v的最后一个邻接点,则// 返回 空 . 例NextAdjVex(G, B, E)=? FirstAdjVex(G, B) =? 邻接点操作与存储表示有关 B A C D F E G

1 2

3 4

5 5

4 3

2 1 A F 4. 插入或删除顶点 InsertVex(&

G, v);

//在图G中增添新顶点v. DeleteVex(&

G, v);

// 删除G中顶点v及其相关的弧. 5. 插入和删除弧 InsertArc(&

G, v, w);

// 在G中增添弧,若G是无向的, //则还增添对称弧. DeleteArc(&

G, v, w);

//在G中删除弧,若G是无向的, //则还删除对称弧. 6. 遍历DFSTraverse(G, v, Visit());

//从顶点v起深度优先遍历图G,并对每//个顶点调用函数Visit一次且仅一次. BFSTraverse(G, v, Visit());

//从顶点v起广度优先遍历图G,并对每//个顶点调用函数Visit一次且仅一次. 7.1 图的抽象数据类型定义 7.2 图的存储表示 7.3 图的遍历 7.4 最小生成树 7.7 两点之间的最短路径问题 7.5 拓扑排序 7.6 关键路径 7.2 图的存储表示

一、图的数组(邻接矩阵)存储表示

二、图的邻接表存储表示

三、有向图的十字链表存储表示

四、无向图的邻接多重表存储表示 图的存储表示的特点: 1. 没有顺序存储结构,但可以借助数组的数据 类型表示图元素之间的关系;

2. 以顶点为核心,建立邻接点和弧的关系;

A[i][j]={

0 , (vi,vj)?VR

1 , (vi,vj)?VR

一、图的数组(邻接矩阵)存储表示 定义: n*n矩阵的元素为

1 2

3 4

5 6

123456 V1 V2 V3 V4 V5 V6 无向图 网的邻接矩阵存储表示 定义: n*n矩阵的元素为 无向网 V1 V2 V3 V4 V5 V6

15 6

7 11

2 25

12 1

2 3

4 5

6 123456

8 8

8 8

8 8

8 8

8 8

8 8

8 8

8 8

8 8

8 8

8 Aij= { wi,j ,(vi,vj) ? VR ,(vi,vj) ? VR

8 显然,无向图和无向网的邻接矩阵是对称矩阵. 有向图的邻接矩阵为非对称矩阵 V1 V2 V4 V3 V5

1 2

3 4

5 12345 出度?入度? 出度 入度 typedef struct { // 图的定义 } MGraph;

typedef struct ArcCell { // 弧的定义 VRType adj;

VRType是顶点关系类型.对无权图,用1或0表示相邻否;

对带权图,则为权值类型. InfoType *info;

该弧相关信息的指针} ArcCell, AdjMatrix[MAX_VERTEX_NUM]MAX_VERTEX_NUM];

// 二维数组 VertexType vexs[MAX_VERTEX_NUM]顶点向量,顶点信息 AdjMatrix arcs;

邻接矩阵 ,弧信息 int vexnum, arcnum;

顶点数,弧数 GraphKind kind;

图的种类标志 // DG,UDG,DN,UDN 采用邻接矩阵构造无向图 输入: 图的顶点数vexnum, 边数arcnum,边信息指针info 图的顶点向量(V1, V2, …, Vn ) 图的边信息(V1, V2 ) 及权值W 输出:邻接矩阵AdjMatrix[vexnum][vexnum]顶点向量 vexs[vexnum] Status CreateUDN (Mgraph &

G) { //构造无向图 scanf(&

G.vexnum,&

G.arcnum,&

IncInfo) //输入顶点,边数 for(i=0;

i<

G.vexnum;

++i) scanf(&

G.vexs[i]);

//输入顶点向量 for(i=0;

i<

G.vexnum;

++i)初始化邻接矩阵 for(j=0;

j<

G.vexnum;

++j) G.arcs[i][j]={0,NULL};

for(k=0;

k<

G.arcnum;

++k)构造邻接矩阵 scanf(&

v1,&

........