Microsoft PowerPoint - DS_Ch7.ppt [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - DS_Ch7.ppt [兼容模式]"

凰尹
4 years ago
Views:

Ch.7 图图是一种复杂的非线性结构 Def: 图由两集合组成 G=(V, E) V(G): 顶点集顶点的有穷非空集 E(G): 边集 V 中顶点偶对的有穷集无向图 : 边由顶点的无序对构成应用 :AI 工程数学生物计算机和表示同一条边, 称为无向边有向图 : 边由顶点的有序对构成结点间的逻辑关系 : 任两个结点都可能相关和表示不同的有向边弧尾起点 1 弧头终点 2

1 Ch.7 图图是一种复杂的非线性结构 Def: 图由两集合组成 G=(V, E) V(G): 顶点集顶点的有穷非空集 E(G): 边集 V 中顶点偶对的有穷集无向图 : 边由顶点的无序对构成应用 :AI 工程数学生物计算机和表示同一条边, 称为无向边有向图 : 边由顶点的有序对构成结点间的逻辑关系 : 任两个结点都可能相关和表示不同的有向边弧尾起点 1 弧头终点 2 例子 : 顶点和边的关系 : 设 1 无向图 : 当当时, 则为零图, 则称之为 ( 无向 ) 完全图完全图中任一顶点到其他顶点均有边 2 有向图 : 约定 : 只讨论简单图 1 不允许有反身边 : 即或则 2 不允许平行边 : 中不允许有重复元素 3 当, 则称之为有向完全图 4 3 稀疏图稠密图. 边少边多. 邻接与关联 ( 依附 ) 若, 则和互为邻接点若, 则邻接到, 邻接自边和关联 ( 依附 ) 于顶点和不好定义前驱和后继顶点的度无向图 : 关联于顶点的边数例有向图 : 出度以为起点的边数入度以为终点的边数子图对有向或无向图均成立设是图,, 且中边所关联的顶点均在中, 则亦为图, 称之为 G 的子图 5 6 1

路径有根图 : 若存在一顶点序列使在有向图 G 中, 若存在, 从到其他顶点均有路径可达, 则称为根,G 为有根图则称从到存在一条路径所经过的边数称为路径长度有向路径类似定义简单路径 : 连通连通图联通分量设

连通图只有一个连通分量, 即自身简单回路 ( 环 ): 起点和终点相同的简单路径 7 8 强连通图设 G 是有向图,, 若到及到都有路径, 则是强连通图 n 个顶点的强连通图至少有几条边? 有向完全图是强连通图?

2 图的存储结构没有前驱和后继的关系, 任两结点均可能有邻接关系无向图中, 邻接点互为对称, 分不清谁是前驱和后继有向图中, 边的起点为前驱, 终点为后继, 但有向环又如何表达?

2 路径有根图 : 若存在一顶点序列使在有向图 G 中, 若存在, 从到其他顶点均有路径可达, 则称为根,G 为有根图则称从到存在一条路径所经过的边数称为路径长度有向路径类似定义简单路径 : 连通连通图联通分量设 G 为无向图 1 G 中, 若和有路径, 则称和连通 2 若, 和均连通, 则 G 为连通图 3 无向图中极大连通子图称为连通分量除起点和终点外, 其余顶点均不相同的路径. 连通图只有一个连通分量, 即自身简单回路 ( 环 ): 起点和终点相同的简单路径 7 8 强连通图设 G 是有向图,, 若到及到都有路径, 则是强连通图 n 个顶点的强连通图至少有几条边? 有向完全图是强连通图? 强连通分量 : 有向图的极大强连通子图, 称为强连通分量强连通图只有一个强连通分量例 :G 1 不是强连通图, 它有两个强连通分量加权图 : 顶点边上带权图的存储结构没有前驱和后继的关系, 任两结点均可能有邻接关系无向图中, 邻接点互为对称, 分不清谁是前驱和后继有向图中, 边的起点为前驱, 终点为后继, 但有向环又如何表达? 设 G 中, 多种表示法, 重点介绍常用的两种邻接矩阵表示法邻接矩阵表示法邻接矩阵 : 表示顶点 ( 数据元素 ) 相邻关系的矩阵若顶点信息无关紧要, 则用二维数组表示, 类型说明 #define MaxVertexNum 100 // 最大顶点数 typedef int EdgeType; // 边类型对于加权图 : typedef char VertexType; // 顶点类型 typedef struct{ VertexType vexs[maxvertexnum]; // 顶点表无向图的邻接矩阵是对称的邻接矩阵表示法 : 若顶点信息重要, 则应将其组织成一个顺序表 : 边表 ( 邻接矩阵 ) 顶点表 11 EdgeType edges[maxvertexnum][maxvertexnum]; // 边表, 邻接矩阵 int n, e; // 顶点数, 边数 MGraph; 12 2

7.2.1 邻接矩阵表示法建立无向图的邻接矩阵表示 step1: 输入顶点数边数 step2: 输入顶点表 step3: 初始化邻接矩阵 step4: 输入边 ( 及权值 ) 链式存储结构为每个顶点的邻接关系建立一个单链表, 将头结点放在一个数组中, 形成一个顶点表和一个边表顶点表结点 : 边表结点 : 边表示 :, 因为和分别存储在顶点表的 ith 和 jth 分量中,

int adjvex;// 邻接点序号 struct node * next; // 指向下一个边表结点 // 若有权, 则增加一域 EdgeNode; 15 typedef struct { AdjList adjlist; // 邻接表 int n, e; // 顶点数和边数 ALGraph; 16 无向图的邻接表, 则在的邻接表中有一的边表结点在的邻接表中有一

3 7.2.1 邻接矩阵表示法建立无向图的邻接矩阵表示 step1: 输入顶点数边数 step2: 输入顶点表 step3: 初始化邻接矩阵 step4: 输入边 ( 及权值 ) 链式存储结构为每个顶点的邻接关系建立一个单链表, 将头结点放在一个数组中, 形成一个顶点表和一个边表顶点表结点 : 边表结点 : 边表示 :, 因为和分别存储在顶点表的 ith 和 jth 分量中, 故只需在的边表中存放序号 j 即可例 : typedef struct vnode{// 顶点表结点 VertexType vertex;// 顶点数据域 EdgeNode * firestedge; // 边表头指针 VertexNode,AdjList[MaxVertexNum];// 邻接表类型说明 typedef struct node{// 边表结点 int adjvex;// 邻接点序号 struct node * next; // 指向下一个边表结点 // 若有权, 则增加一域 EdgeNode; 15 typedef struct { AdjList adjlist; // 邻接表 int n, e; // 顶点数和边数 ALGraph; 16 无向图的邻接表, 则在的邻接表中有一的边表结点在的邻接表中有一的边表结点每条边表示了两次, 所以一共有 2e 个边表结点空间复杂度为, 邻接矩阵为稀疏图邻接表节省空间, 稠密图邻接矩阵为宜 17 有向图的邻接表, 在的邻接表中有一个的边表结点每边表示了 1 次, 所以共有 e 个边表结点此时的边表称为出边表出边表中求出度易, 求入度难逆邻接表 :, 在的邻接表中有一个的边表结点此时的边表称为入边表入边表中求入度易, 求出度难 18 3

4 建立邻接表 1 时间 :, 邻接矩阵 2 唯一性 : 不唯一, 不同输入次序, 结果不同但邻近矩阵唯一运算 1 判是否为边? 邻接矩阵, 邻接表 2 求顶点度数 : 二者差不多 3 检测边数 : 邻接矩阵, 邻接表 7.3 图的遍历是图上运算的基础没有开始结点, 如何访问? 任两点可能相邻, 故访问某点后可能顺回路又回到该点, 为避免重复访问, 须标记已访问过的顶点 Visited[0 n-1] 布尔数组, 初值为 false 常用的方法有两种类似于树的前序遍历基本思想设 G 初态是所有顶点均未曾访问, v V(G) 为初始出发点 ( 源点 ), 则深度优先遍历可定义为 : 首先访问出发点 v, 将其标记为已访问 ; 然后依次从 v 出发搜索 v 的每个邻接点 w, 若 w 未曾访问过, 则以 w 为出发点继续深度优先遍历, 直至图中所有和 v 有路径相通的顶点均已被访问为止 ; 若此时图中仍有未访问过的顶点, 则另选一尚未访问过的顶点作为新源点重复上述过程, 直至图中所有顶点均已访问为止 21 特点 : 遍历定义是递归的, 特点是尽可能先对纵深方向搜索, 故称为深度优先搜索 (dfs), 搜索过程 : 22 设 x 是当前访问顶点 : 1 若 v 1,v 2,v 3 均未被访问过, 则以 v 1 为出发点向纵深搜索, 不能前进后回溯到 x, 继续从 v 2,v 3 出发, 当 v 2,v 3 为出发点搜索完成后回溯至 x, 因为 x 的所有邻接点均已访问过, 故继续回溯至 x 之前被访问的顶点 ; 2 若 v 1,v 2,v 3 均访问过, 表示一定是从 x 之前被访问的顶点出发的搜索曾到达过 v 1,v 2, v 3, 故访问 x 之后返回 ( 回溯 ) 至 x 之前的结点 23 算法实现 typedef enum {FALSE, TRUE Boolean; Boolean Visited[MaxVertexNum]; // 全局量 void DFSTraverse(ALGraph *G) { // 以邻接表表示图 for (i=0; i<g->n; i++) Visited[i] = FALSE; // 初始化 for (i=0; i<g->n; i++) if (! Visited[i]) //v i 未访问过 DFS(G,i); // 以 v i 为源点开始 dfs 搜索 // 图连通仅有 1 次外部调用 24 4

5 void DFS (ALGraph *G, int i) { // 以 v i 为出发点对 G 进行 dfs EdgeNode *p; printf ( %c, G->adjlist[i].vertex); // 访问顶点 v i Visited[i]=TRUE; // 标记 v i 已访问过 p=g->adjlist[i].firstedge; // 取 v i 边表的头指针 while (p) { // 依次搜索 v i 的邻接点 v j if (!Visited[p->adjvex]) // 若 v j 未访问过,j=p->adjvex DFS(G,p->adjvex); // 以 v j 为出发点向纵深搜索 p=p->next; // 若 v j 已访问过, 或从 v j 出发的 dfs 完成, 则 // 找 v i 的下一邻接点以邻接矩阵为存储结构自己写出 DFS 25 深度优先遍历序列 (DFS 序列 ) 遍历过程的顶点访问序列 G 的 DFS 序列不唯一, 但初始源点给定, 存储结构给定时所得序列唯一 26 时间 1 对 G 中每个顶点恰做一次访问 ( 外部 + 内部调用 dfs), 共做 n 次访问 2 当访问顶点 v i 时, 时间主要花费在搜索 v i 的邻接点上合计 : 邻接表表示 : 〇 (n+e), 各个边表结点均搜索到邻接矩阵 : 〇 (n 2 ), 各个元素均检索到类似于树的层次遍历基本思想 1 选一顶点 v 为源点访问之特点尽可能先对横向搜索, 故称之为广度优先搜索 (BFS) 2 依次访问 v 的所有邻接点 w 1,w 2 w t 3 然后依次访问 w i (1 i t) 的所有未曾访问过的邻接点依次类推, 直至图中所有和源 v 有路径连通的顶点均已访问过为止此时, 若 G 是连通图, 则遍历完成 ; 否则选 G 的另一未访问过的顶点做新源点继续上述搜索过程, 直至 G 中所有顶点均已访问过为止 29 非递归, 用队列作为中间数据结构先访问的顶点其邻接点亦被先访问 (FIFO) 递归回溯, 用栈保存访问过的顶点后访问的顶点其邻接点被先访问 (LIFO) 30 5

6 设 x 和 y 是两个相继访问的顶点, 其邻接点分别记为 x 1,,x s 和 y 1,,y t x 在 y 之前访问, 故 x 1,,x s 中未访问顶点亦先于 y 1,,y t 中未访问被访问到可用 FIFO 队列 1 保存已访问过的顶点顶点入队时对其访问 2 保存尚未访问过的顶点顶点出队时对其访问第一种方法较好, 下面用此方法实现算法算法遍历算法类似于 DFSTraverse void BFS(ALGraph *G, int k) { // 以 v k 为源 InitQueue(&Q); // 队列 Q 初始化 printf( %c, G->adjlist[k].vertex); // 访问源 v k Visited[k]=TRUE; EnQueue(&Q, k); // 相当于 v k 入队 while (!QueueEmpty(&Q) ) { i=dequeue(&q); //v i 出队 p=g->adjlist[i].firstedge; // 取 v i 边表头指针 while(p) { // 依次搜索 v i 的邻接点 v j if(!visited[p->adjvex]) //v j 未访问过, 设 p->adjvex=j BFS 队列 printf( %c,g->adjlist[p->adjvex].vertex); j // 访问 v j Visited[p->adjvex]=TRUE; EnQueue(&Q, p->adjvex); //v j 入队 p=p->next; // 在下一边表结点中找 v i 下一个邻接点 33 时间每个顶点入队一次, 每个边表结点搜索一次时间与 dfs 相同图的连通性问题无向图的连通分量和生成树 1. 求连通分量每外部调用一次 DFS 或 BFS, 可求一连通分量的顶点集 2. 生成树和生成森林生成树连通图 G 的极小连通子图, 但包含 G 的所有顶点 ( 支撑树 ), 不唯一 n 个顶点的连通图的生成树一定有 n-1 条边无向图的连通分量和生成树生成森林 : 各连通分量的生成树集合求生成树和生成森林 ( 使用 DFS 和 BFS) 1 设 G 是无向图, v V(G) 做出发点若图连通, 则做一次 DFS 或 BFS, 必将 G 中 n 个顶点都访问到, 且只做一次访问两种搜索方法中, 从 v i 搜索到 v j 时, 须经过边 (v i,v j ), 故只需添加输出边的操作即可 : 36 6

7 7.4.1 无向图的连通分量和生成树在 dfs 和 bfs 中, 均在 while(p) { if(!visited[p->adjvex] ) { 加入打印 :(i,p->adjvex) j //dfs 须在递归前加入若 G 连通则求出的生成树, 否则为生成森林 2 若 G 为有向图, 仅当源点为有根图的根时, 才能求得生成树, 否则为生成森林 37 7

Microsoft PowerPoint - DS_Ch5 [兼容模式]

Microsoft PowerPoint - DS_Ch5 [兼容模式] Ch.7 图图是一种复杂的非线性结构应用 :AI 工程数学生物计算机结点间的逻辑关系 : 任两个结点都可能相关 1 Def: 图由两集合组成 G=(V, E) V(G): 顶点集顶点的有穷非空集 E(G): 边集 V 中顶点序偶对的有穷集无向图 : 边由顶点的无序对构成 (V i,v j ) 和 (V j,v i ) 表示同一条边, 称为无向边有向图 : 边由顶点的有序对构成