第七章 图 (Graph) 2007.9.

Presentation on theme: "第七章 图 (Graph) 2007.9."— Presentation transcript:

1 第七章 图 (Graph) 2007.9

2 主要内容 7.1 图的基本概念 7.2 图的存储结构 7.3 图的遍历 7.4 生成树和最小生成树

3 7.1 图的基本概念

4 1. 图的定义 图G由两个集合构成，记作G=<V,E> 其中: V（vertex）是顶点的非空有限集合
E（edge）是边的有限集合， 而边是顶点对的集合。 V0 V4 V3 V1 V2 G1=<V1,E1> V1={v0 ,v1,v2,v3,v4} E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)}

5 图的应用举例： 例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示；
例2 电路图 顶点：元件 边：连接元件之间的线路 例3 通讯线路图 边：地点间的连线 例4 各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系

6 2. 图的基本术语 有向图、无向图 有向边（弧）、弧尾、弧头 无向边（边） 完全图：总边数 子图 路径、路径长度 简单路径、简单回路
V0 V4 V3 V1 V2 有向图、无向图 有向边（弧）、弧尾、弧头 无向边（边） 完全图：总边数 有向完全图、无向完全图： 子图 路径、路径长度 简单路径、简单回路 连通图、连通分量、强连通图 网络：带权的图 V0 V1 V2 V3

7 邻接点、相邻接、边与顶点关联 无向图中顶点的度 有向图中顶点的度＝入度+出度 生成树、生成林 V0 V4 V3 V1 V2 V0 V1 V2

8 混和图：在图G中，即有无向边也有有向边 有向边（弧）、弧尾、弧头；无向边（边） 无向图:在图G中，若所有边是无向边
完全图： 无向完全图：任意两顶点间都有边的图。 在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。 有向完全图:任意两顶点之间都有方向互为相反的两条弧相连 接的有向图。 在一个含有n个顶点的有向完全图中，有n(n-1)条弧。 V0 V4 V3 V1 V2 V0 V1 V2 V3

9 邻接点：边的两个顶点 关联边：若边e= (v, u), 则称顶点v、u 关联边 顶点的度 在无向图中,顶点V的度 = 与V相关联的 边的数目，记作TD(V) 在有向图中,顶点V的度= V的出度+V的入 度 顶点V的出度=以V为起点有向边数 顶点V的入度=以V为终点有向边数

10 顶点 度 V0 2 V1 3 V2 V3 V4 顶点 入度 出度 度 V0 1 2 3 V1 V2 V3 V0 V4 V3 V1 V2 V0
V2 V3

11 G中的顶点序列v1,v2,… ,vk,若各边(vi,vi+1)E, 则 称该序列是从顶点v1到顶点vk的路径； 回路:
若路径的顶点和终点相同，则称回路。 简单路径 在一条路径中,若除起点和终点外,所有顶点各不相同,则 该路径为简单路径； 简单回路： 由简单路径组成的回路称为简单回路； V0 V4 V3 V1 V2

12 设有两个图G=（V，E）、G1=（V1，E1） ，若V1 V，E1  E，E1关联的顶点都在V1 中，则称 G1是G的子图；
例 (b)、(c) 是 (a) 的子图 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 (c) (a) (b)

13 在无（有）向图G=< V, E >中，若对任何两个顶点 v、u 都存在从v 到 u 的路径，则称G是连通图
连通图、强连通图 在无（有）向图G=< V, E >中，若对任何两个顶点 v、u 都存在从v 到 u 的路径，则称G是连通图 对有向图而言，称强连通图 非连通图 连通图 V0 V4 V3 V1 V2 V0 V2 V3 V1 V5 V4 非强连通图 强连通图 V0 V1 V2 V3 V0 V1 V2 V3

14 极大连通子图意思是：该子图是 G 连通子图 ，将G 的任何不在该子图中的顶点加入，子 图不再连通；
连通分图（有向图中为强连通分量） 无向图G 的极大连通子图称为G的连通分量 极大连通子图意思是：该子图是 G 连通子图 ，将G 的任何不在该子图中的顶点加入，子 图不再连通； 连通分图 非连通图 V0 V2 V3 V1 V5 V4

15 极大强连通子图意思是：该子图是D强连通子 图，将D的任何不在该子图中的顶点加入，子 图不再是强连通的；
强连通分量 V0 V2 V3 V1 V0 V1 V2 V3

16 G1的生成树 连通图 G1 生成树 包含无向图G 所有顶点的的极小连通子图称为G 的生成树
若T是G 的生成树当且仅当T 满足如下条件 T是G 的连通子图 T包含G 的所有顶点 T中无回路 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 G1的生成树 连通图 G1

17 边的权：在图的边或弧上表示数字，表示与该边 相关的数据信息，这个数据信息就称该边的权（ weight）。
网（network）：边（或弧）上带权的图称为网。 8 V0 V4 V3 V1 V2 6 2 3 4 5

18 7.2图的存储表示

19 ？ 邻接矩阵表示法 邻接表表示法 图的存储结构要保存两类信息： 1)顶点的数据 2)顶点间的关系 V0 V1 V2 V3 V4 V0 V4

20 7.2.1. 邻接矩阵表示 1.图的邻接矩阵 图G的邻接矩阵是满足如下条件：
A[i][j]= 1 若(vi,vi+1)E 或 <vi,vi+1>E 0 否则 V0 V1 V2 V3 V0 V1 V2 V3 V4 V0 V4 V3 V1 V2 V0 V1 V2 V3

21 1）无向图邻接矩阵是对称矩阵，可考虑矩阵的压缩 存储 2）G占用存储空间只与它的顶点数有关，与边数无 关；适用于边稠密的图；
2.无向图邻接矩阵表示的特点： 1）无向图邻接矩阵是对称矩阵，可考虑矩阵的压缩 存储 2）G占用存储空间只与它的顶点数有关，与边数无 关；适用于边稠密的图； V0 V1 V2 V3 V4 邻接矩阵表示法的空间代价 只与图的顶点数有关 V0 V4 V3 V1 V2

22 3.邻接矩阵下图的有关操作 1）求顶点v的度： 2）判断两顶点是否邻接： 3）在图中增加、删除边： 4）检测图中的总边数：
V0 V1 V2 V3 V4 V0 V4 V3 V1 V2 V0 V1 V2 V3 V0 V1 V2 V3

23 邻接矩阵存储下图的有关操作 1）求顶点v的度：等于二维数组对应行（或列）中1的个数；
2）判断两顶点是否邻接：只需判二维数组对应分量是否为1； 3）在图中增加、删除边：只需对二维数组对应分量赋值1或清0； 4）检测图中的总边数：扫描整个数组A，统计出数组中非0元素 的个数。无向图的总边数为非0元素个数的一半，而有向图的总 弧数为非0元素个数； V0 V1 V2 V3 V4 V0 V4 V3 V1 V2 V0 V1 V2 V3 V0 V1 V2 V3

24 4.邻接矩阵的C语言描述 #define N 5/*顶点数*/ #define M 6 /*边数*/
typedef char vextype; /*顶点类型*/ typedef sturct{ vextype vexs[N]; /*存顶点的数组*/ adjtype edge[N][M];/*存边信息的矩阵*/ } V0 V1 V2 V3 V4 V0 V4 V3 V1 V2

25 5.建立无向图的邻接矩阵 算法思想： 1）给存顶点的一维数组赋值； 2）初始化存边的二维数组；
3）依次读入顶点对，给二维数组相关的元素赋值。 代码见书P158，函数Creat_graph( ) 时间复杂度O（n+n2+e）

26 7.2.2.邻接表表示 邻接表是图的链式存储结构 1. 无向图的邻接表 顶点：通常按编号顺序将顶点数据存储在一维数组中；
关联同一顶点的边：用线性链表存储 下标 编号 link V0 V4 V3 V1 V2 2 1 3 4 m-1 V0 V1 V2 V3 V4 表头数据 指向邻接表的指针 邻接结点数据 指向下一邻接点的指针

27 2.有向图的邻接表和逆邻接表 1）有向图的邻接表（出边表） 顶点：用一维数组存储（按编号顺序） 以同一顶点为起点的弧：用线性链表存储 V0
下标 编号 link V0 V1 V2 V3 1 2 3 1 2 3 m-1 V0 V1 V2 V3

28 2）有向图的逆邻接表（入边表） 顶点：用一维数组存储（按编号顺序） 以同一顶点为终点的弧：用线性链表存储 V0 V1 V2 V3 1 2 3
1 2 3 m-1 V0 V1 V2 V3

29 3.邻接表存储下图的有关操作 1）求顶点v的度： 2）判断两顶点是否邻接： 3）在图中增加、删除边： 4）检测图中的总边数： V0 V1 1
1 3 4 m-1 V0 V1 V2 V3 V4 V0 V4 V3 V1 V2

30 1）求顶点v的度：等于v对应线性链表的长度；
3）在图中增加、删除边：在相应的顶点的链表 中插入、删除结点 4）检测图中的总边数：

31 无向图的邻接表的特点 1）在G邻接表中，同一条边对应两个结点；
2）设存储顶点的一维数组大小为m(m图的顶点数n), 图 的边数为e，G占用存储空间为：m+2*e。G占用存储空 间与 G 的顶点数、边数均有关；适用于边稀疏的图 1 2 3 4 m-1 V0 V1 V2 V3 V4 1 3 2 4 V0 V4 V3 V1 V2 1 3 4 2 1 2 邻接表的空间代价 与图的边及顶点数均有关

32 4. 邻接表在C语言中的类型定义 typedef struct node //定义 边结点的类型 { char adjver; //边的邻接点的数据 struct node *next; //指向本边下一邻接点的指针 }edgenode; typedef struct { //定义 顶点的类型 char vertex; //顶点的数据 edgenode *link; //指向本边邻接表 }vernode; typedef struct {//定义 图 vernode adjlist[MAX]; int n,e; //n-顶点数，e-边数 }link_graph;

33 5.建立无向邻接表 思想：如何给存储结构赋值 时间复杂度O（n+e） i j
建立顶点数组。读入各顶点数据vextex，将link域赋Null。 建立各顶点的邻接表。 读入顶点对<i,j>, 生成两个节点 ， ，分别插入顶点j,i的邻接表 的头部。直至处理完所有的边。 时间复杂度O（n+e） i j typedef struct node //定义 边结点 { char adjver struct node *next; }edgenode; typedef struct { //定义 顶点 char vertex; edgenode *link; }vernode; typedef struct {//定义 图 vernode adjlist[MAX]; int n,e; //n-顶点数，e-边数 }link_graph; link_graph *ga; 1 2 3 4 m-1 V0 V1 V2 V3 V4

34 函数：书P161 int create(link_graph *ga ) { NODE *p; int n, e, i；char v1, v2; scanf(“%d%d\n”, &n,&e); //读入顶点数、边数 ga->n=n， ga->e=e; for(i=0; i<n; i++) //建立顶点数组 { scanf(“%c”, &ga->adjlist[i].vertex); //读入顶点数据 gs->adjlist[i].link=NULL; //指针域赋空 }

35 i=0； while ( i<=e ) //建立各顶点的邻接表 { scanf(“%c to %c \n”, &v1, &v2); //读入一条边 //生成结点V2； p=( edgenode *)malloc(sizeof(edgenode )); p->adjver=v2; //插入在顶点V1的邻接表的首部 p->next=ga->adjlist[v1].link; ga->adjlist[v1].link=p; //生成结点V1； p=(edgenode *)malloc(sizeof(edgenode )); p->adjver=v1; //插入在顶点V2的邻接表的首部 p->next=ga->adjlist[v2].link; ga->adjlist[v2].link=p; }

36 在不同的存储结构下，实现各种操作的效率可能是不同的。所以在求解实际问题时，要根据求解问题所需操作，选择合适的存储结构。

37 7.3 图的遍历

38 7.3图的遍历 ？ 图的遍历：从图的某顶点出发，访问图中所有顶点， 并且每个顶点仅访问一次。 采用怎样的策略进行图的遍历 有两种遍历方法：
V0 V7 V6 V5 V4 V3 V2 V1 有两种遍历方法： 深度优先遍历（DFS：Depth First Search） 广度优先遍历（BFS：Breadth First Search）

39 7.3.1 两种遍历思想 一 、深度优先遍历（DFS） 从图中某顶点v出发：
两种遍历思想 一 、深度优先遍历（DFS） 从图中某顶点v出发： 1）访问顶点v； 2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历； 求图G以V0起点的的深度优先序列： 例 V0,V1,V3,V7,V4,V2,V5,V6, V0,V1,V4,V7,V3,V2,V5,V6 V0 V7 V6 V5 V4 V3 V2 V1 V0 V7 V6 V5 V4 V3 V2 V1 由于没有规定 访问邻接点的顺序， DFS序列不唯一

40 例 二、广度优先遍历（BFS） 图中某未访问过的顶点vi出发： 1）访问顶点vi ；
2）访问 vi 的所有未被访问的邻接点w1 ,w2 , …wk ； 3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问； 求图G 的以V0起点的的广度优先序列: V0,V1,V2,V3,V4,V5,V6,V7 例 类似于树的按层遍历 V0 V7 V6 V5 V4 V3 V2 V1 V0 V7 V6 V5 V4 V3 V2 V1 由于没有规定 访问邻接点的顺序， BFS序列不唯一

41 图的遍历算法 在图中，访问部分顶点后，可能又沿着其他边回到 已被访问过的顶点。为保证每一个顶点只被访问一次 ，必须对顶点进行标记，可用一个辅助数组 visit[MAX] 作为对顶点的标记。 visit 1 2 3 4 m-1 辅助数组 int visit[MAX]; //顶点标志数组,全局变量 若visit[i]=0，顶点vi未被访问； 若visit[i]=1，当vi已被访问。

42 7.3.2 图的遍历算法 一.深度优先遍历算法 基于邻接矩阵的DFS算法:dfsm() 基于邻接表的DFS算法:dfsl()
图的遍历算法 一.深度优先遍历算法 基于邻接矩阵的DFS算法:dfsm() 基于邻接表的DFS算法:dfsl() 二.广度优先遍历 基于邻接矩阵的BFS算法: bfsm() 基于邻接表的BFS算法: bfsl()

43 1.深度优先遍历算法 调用深度优先遍历算法的主函数 DFS(matrix_gragh *g ) // DFS(link_gragh *g ) { int i; for ( i=0;i<g->n;i++) visit[i]=0; //初始化辅助数组 for ( i=0; i<g->n; i++ ) if ( !visit [i] ) DFSM（g, i）; //从Vi出发在邻接矩阵中深度优先遍历 // DFSL（g, i）; //从Vi出发在邻接表中深度优先遍历 }

44 基于邻接矩阵的DFS算法:dfsm() 核心问题：如何在邻接矩阵中沿深度进行遍历 时间复杂度：O(n*n) 深度优先遍历（DFS）,
从图中某顶点v出发： 1）访问顶点v； 2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历； 时间复杂度：O(n*n) 递归 //从图中某顶点vi出发 Void DFSm(matrix_graph *g, int i ) { int j; //访问顶点v； visit(i); visit[i]=1; //依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历； for ( j = 0; j<=N; j++ ) if ((g->edges[i][j] = = 1&& !visit[j] ) dfsm(g,j) } #define N 5/*顶点数*/ #define M 6 /*边数*/ typedef int vextype; typedef sturct{ vextype vexs[N]; /*存顶点*/ adjtype edge[N][M];/*存边*/ }matrix_graph; matrix_graph *g;

45 基于邻接矩阵的DFS算法:dfsl() 核心问题：如何在邻接表中沿深度进行遍历 时间复杂度：O(n+e)
typedef struct node // 边结点 { int adjver struct node *next; }edgenode; typedef struct { // 顶点 int vertex; edgenode *link; }vernode; typedef struct {// 图 vernode adjlist[MAX]; int n,e; }link_graph; link_graph *ga; //从图中某顶点vi出发 Void DFSl(link_graph *g, int i ) { int j; edgenode *p; //访问顶点v； visit(i); visit[i]=1; //依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历； p=g->adjlist[i].link; while ( p ) { if ( !visit[p->vertex] ) dfsl(g,j); p=p->next; }

46 2.广度优先遍历算法 思想： 图中某未访问过的顶点vi出发： 1）访问顶点vi ；
2）访问 vi 的所有未被访问的邻接点w1 ,w2 , …wk ； 3）依次从这些邻接点出发，访问它们的所有未被访问 的邻接点; 依此类推，直到图中所有访问过的顶点的 邻接点都被访问；

47 问题：如何保证邻接点的出发顺序？ 解决：利用队列。 定义链式队列： linkQueue * Q; 1）从图中某未访问过的顶点vi出发：
3）访问 vi 的所有未被访问的邻接点w1 ,w2 , …wk ； 4）将w1 ,w2 , …wk 入队； 5）取队头顶点，从该顶点出发，访问它的所有未被访问 的邻接点；即重复2－5，直到图中所有访问过的顶点的 邻接点都被访问 定义链式队列： linkQueue * Q;

48 基于邻接矩阵的BFS算法: bfsm() Void BFSM(matrix_graph *g, int i ) { int i,j;
SetNull ( Q ); //设从V0开始； i=0; // 访问V0 visit( g->vexs[i]); visit[i]=1; EnQueue(Q, j); while ( ! EmptyQueu(Q) ) { i=DeQueue( Q); // 取队头 for ( j=0 ; j<N; j++) //访问所有邻接点 if ((g->edges[i][j] = = 1&& !visit[j] ) { visit( g->vexs[j]); visit[i]=1; } #define N 5 /*顶点数*/ #define M 6 /*边数*/ typedef int vextype; typedef sturct{ vextype vexs[N]; adjtype edge[N][M]; }matrix_graph; matrix_graph *g;

49 7.5 生成树和最小生成树

50 7.5生成树和最小生成树 生成树 生成树是一个连通图G 的一个极小的连通子图。包含图G 的所有顶点，但只有n-1 条边，并且是连通的。生成树可由遍历过程中所经过的边组成。深度优先遍历得到的生成树称为深度优先生成树；广度优先遍历得到的生成树称为广度优先生成树。 V0 V7 V6 V5 V4 V3 V2 V1 V3 V0 V7 V6 V5 V4 V2 V1 深度优先生成树 广度优先生成树

51 7.5生成树和最小生成树 ？ 例 7.5.2 最小生成树（最小支撑树）
最小生成树（最小支撑树） 若有一个连通的无向图 G ，有 n 个顶点，并且它的边是有权值的。在 G 上构造生成树 G’ ,最小生成树 n-1 条边的权值之和最小的 G’ 。 V2 V0 V3 V5 V4 V1 3 6 5 2 1 4 例   要在 n 个城市间建立交通网，要考虑的问题如何在保证 n 点连通的前题下最节省经费? 如何求连通图的 最小生成树? ？ 求解: 连通6个城市且代价最小的交通线路?

52 7.5生成树和最小生成树 (1) 普鲁姆算法 V2 V0 V3 V5 V4 V1 3 6 5 2 1 4  普鲁姆算法基本步骤
(1) 普鲁姆算法  普鲁姆算法基本步骤 设G=（V，E）为一个具有n个顶点的带权的连通网络，T=（U，TE）为构造的生成树。 （1）初始时，U={u0}，TE=； （2）在所有uU 、vV-U 的边（u,v）中选择一条权值最小的边，不妨设为（u,v)； （3）(u,v) 加入TE，同时将u 加入U； （4）重复(2)、（3），直到U=V为止； V2 V0 V3 V5 V4 V1 3 6 5 2 1 4

53 U={ V0,V2,V5} U={ V0 } U={ V0,V2 } V2 V0 V3 V5 V4 V1 3 6 5 2 1 4 V2 V0 V3 V5 V4 V1 1 V2 V0 V3 V5 V4 V1 1 4 2 V2 V0 V3 V5 V4 V1 1 4 2 V2 V0 V3 V5 V4 V1 1 4 5 2 V3 V0 V5 V4 V1 1 4 5 3 U={ V0,V2,V5,V3 } U={ V0,V2,V5,V3,V1 } U={ V0,V2,V5,V3,V1,V4 }

54 （2） 克鲁斯卡尔算法 V2 V0 V3 V5 V4 V1 3 6 5 2 1 4  基本步骤
设G=（V，E）为一个具有n个顶点的带权的连通网络，最小生成树的初始状态为有n 个顶点但无边的非连通图 T=（V，  ）。 （1）将E 中的边按权值的递增顺序排序，选择权值最小的边，若与相关的顶点落在T 中不同的连通分量上，则将其加入T 中，否则，将其弃舍。 （2）循环至所有顶点在同一的连通分量上。 如何识别一条边所相关的顶点是否落在同一个连通分量上？可将一个连通分量的所有顶点看成一个集合，当从E中取出一条边（ xi, xj ）时，若xi, xj 在同一集合u 中，则将该边弃舍； 否则，则将该边加入到T 中， 并将xj 所在的集合v 并入集合u 中。 V2 V0 V3 V5 V4 V1 3 6 5 2 1 4

55 7.5生成树和最小生成树 sets sets V2 V0 V3 V5 V4 V1 3 6 5 2 1 4 V2 V0 V3 V5 V4 V1
下标 sets 下标 sets 1 1 1 1 1 3 V2 V0 V3 V5 V4 V1 3 6 5 2 1 4 V2 V0 V3 V5 V4 V1 1 2 3 4 5