《软件技术基础 图结构》由会员分享，可在线阅读，更多相关《软件技术基础 图结构（45页珍藏版）》请在金锄头文库上搜索。
1、软件技术基础,制作 主讲,段景山,段景山,图结构,第四章 图结构,图的基本概念,图的遍历,图的存储,4.1图的定义和术语 图是由非空的顶点组成的有限集和边的有限集组成。 二元组 G = （ V，E） V：顶点集合 E：边的集合，即顶点间的关系 图结构中的关系可以是任意的，甚至可以是空集 图是一种对结点的前驱和后继个数不加限制的数据结构,图的定义、术语,1）有向图与无向图 由有向边组成的图，称为有向图 有向边以表示，又称为弧 X：弧尾 Y：弧头 有向边与不是同一条边 由无向边组成的图，称为无向图 无向边以（X，Y）表示 无向边（X，Y）与（Y，X）是同一条边,图的术语,图的术语,2）权与网 图中
2、边或弧所具有的相关数称为权 一般用于表明从一个顶点到另一个顶点的距离或耗费 带权的图称为网 3）邻接与顶点的度 对于（X，Y）E 则X ，Y互为邻接 对于 E 则Y是X的邻接结点,13,图的术语,顶点的度 课堂练习，给出以下顶点的度,顶点度为,有向图：,出度：,入度：,以该顶点为弧尾的弧数,以该顶点为弧头的弧数,无向图,：顶点的边数,总边数 ,2,1,D（Vi）,i=1,n,和,2,1,各顶点度之和,图的术语,4）路径与回路 路径：图中沿着各条边，从X到Y所经历的顶点序列称为路径 路径：X ， b ， a ， Y 环：第一顶点与最后一个顶点相同的路径称为环 环：X，a，Y，b，X 回路： 序列
3、中不出现重复的路径称为简单路径 有重复的路径称为回路 回路：X，a，b，a，Y,a,X,Y,b,图的术语,5）连通、连通图与连通分量 连通：在图中若X与Y之间有路径，则称X，Y是连通的 连通图：任意两个顶点都连通的图称为连通图 没有孤立顶点 连通分量：指无向图中极大连通子图，即有多少个连通子图,图的存储 邻接矩阵,4.2 图的存储 4.2.1 邻接矩阵法 （1）给顶点编号 （2）建立邻接（关系）矩阵,1 2 3 4,1 2 3 4,0 0 0 0,1 0 1 1,1 0 0 1,0 1 1 0,a i j表示弧 1：表示有弧；0:表示无弧,任意顶点的出度是该行元素之和 任意顶点的入度是该列元素
4、之和,图的存储 邻接矩阵,4.2.1 邻接矩阵法 若边 顶点2 则邻接矩阵为稀疏矩阵。 邻接矩阵的优点：增减边的操作简单 邻接矩阵的缺点： 增减顶点的操作需要搬移大量的元素， 浪费存储空间,1 2 3 4,1 2 3 4,0 1 1 0,1 0 1 1,1 1 0 1,0 1 1 0,无向图的邻接矩阵是对称的,图的存储 邻接矩阵的实现,图的邻接矩阵实现,typedef struct graph_m elemtype nodeMAXNUM; int arcsMAXNUMMAXNUM; graph_m;,顶点集合,边的邻接矩阵,二维数组,图的存储 邻接表,4.2.2 邻接表法 一个邻接表由两种结构
5、组成 存放各顶点元素的数组，头结点 各顶点各自的邻接链表，邻接结点,3,data,顶点号,元素域,邻接链表头指针,邻接顶点号,下一邻接结点,图的存储（课堂练习）,请写出下面这副图的邻接表 1、给顶点编号 2、建立顶点数组 3、建立各顶点的邻接链表 注意，此图为有向图,2,1,3,4,5,图的存储 邻接表的实现,邻接表的定义 头结点的定义 邻接结点的定义,typedef struct headnode int node_index; elemtype data; struct adj_node * next_adj; headnode;,typedef struct adj_node int n
6、ode_index; struct adj_node *next_adj; adj_node;,图的存储 邻接表,图邻接表的定义,typedef struct graph_l headnode node_listMAXNUM; int node_num; graph_l;,图的存储 邻接表,2,1,4,3,2,1,4,3,注意：有向图与无向图的区别,图的存储,图的邻接表存储法的特点 优点 节省存储空间 边的插入和删除操作比较简便 缺点 结构复杂 具有两种不同的基本组成单元,图的存储,4.2.3边带权值的图的存储 1）在邻接矩阵中的实现,0 2 3 5 0 1 0 1 0 1 5 0 1 0,a
7、44 =,a i j ：记录边的权值；为0表示无边,2,3,5,1,1,图的存储,4.2.3边带权值的图的存储 2）在邻接表中的实现 在邻接结点结构中增加一个权值域,顶点号,边权值,1,2,4,3,3,2,5,1,1,10,3,图的遍历,4.3图的遍历 问题： 1、对于连通图，从一个顶点出发沿着所有可能的路径，是否可以将所有的顶点遍历到。 2、图中有回路，遍历算法可能产生死循环。,图的遍历 深优,4.3.1 深度优先遍历 （1）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。 （2）如果顶点的所有相邻顶点都是已访问过的，则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。
8、（3）对于前两个步骤是递归的,图的遍历 深优,4.3.1 深度优先遍历 （1）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。 （2）如果顶点的所有相邻顶点都是已访问过的，则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。 （3）对于前两个步骤是递归的,1,2,5,8,4,6,3,7,1,7,3,6,5,2,8,4,1,7,3,6,5,2,8,4,1 3 6 8 4 2 5 7,或者按以下顺序遍历：,注意使用栈支持递归：,图的遍历 深优,深度优先遍历的特点 “深度”：总是访问顶点的一个相邻顶点，好像是沿着图中的一条路径走到“底”，然后后退一点，再选一条路。如此“进进退退”
9、，直到所有顶点都被访问 对于连通图，如果第一个被访问的顶点的所有相邻顶点都被访问了，意味着图中所有顶点都被访问了。 即栈空时,算法实现分析 （1）需要记录结点的访问状态。 int visited 顶点号 ; （2）需要进行回溯。 lstack_type stack （3）图以邻接表的方式存储 graph_l graph ; （4）算法框架 （5）核心算法,图的遍历 深优,图的遍历 深优,（4）算法框架 利用栈，不断将顶点的相邻顶点入栈、访问、出栈 算法以栈空结束 框架：,第一个被访问的顶点入栈；,while（！empty（stack） 核心算法; （即顶点被访问、出入栈的过程）； ,图的遍历
10、深优,（5）核心算法,2、找到该顶点的一个未被访问过的相邻顶点,3、若找到就将该顶点入栈，并访问，回到1,4、否则进行回退出栈，回到1,1、从一个顶点开始,p = graph.node_list v ;,adjp = p-next_adj; while( adjp != NULL ) if ( visited adjp-node_index = = true ) adjp = adjp-next_adj; else break; ,if ( adjp != NULL) v = adjp-node_index; visit（v）；visited v = true; push(stack , ad
11、jp-node_index); ,else v = pop(stack);,void dfs( graph, v ) int visitedMAXNUM; initialize visited ; create_stack(stack); visit( v ); visited v = true; push( stack , v );,while( !empty (stack ) p = graph-node_list v ; adjp = p-next_adj; while( adjp != NULL) if(visited adjp-node_index = true) adjp = ad
12、jp-next_adj; else break; ,if（adjp != NULL ) v = adjp-node_index; visit( v ); visited v = true; push( stack , v ）； else v = pop(stack); ,经过检查/调试上述算法有误,问题出在哪里？,在“入栈并访问”的实现 谁该入栈，谁该被访问？,当前节点入栈（为回退做准备）,访问它的相邻未被访问过节点,正确做法是：,void dfs( graph, v ) int visitedMAXNUM; initialize visited ; create_stack(stack);
13、visit( v ); visited v = true; push( stack , v );,while( !empty (stack ) p = graph-node_list v ; adjp = p-next_adj; while( adjp != NULL) if(visited adjp-node_index = true) adjp = adjp-next_adj; else break; ,if（adjp != NULL ) push( stack , v ）； v = adjp-node_index; visit( v ); visited v = true; else v
14、 = pop(stack); ,图的遍历 深优,用递归调用实现深度优先遍历算法,void dfs （g，v） ,1访问顶点v；,visit（v）；visited v = 1;,p = gv-next_adj while(p != NULL) w = p-node_index; if(visitedw = 0) p = p-next_adj; ,2取得顶点的一个未被访问过的顶点w；,3 dfs（g，w）；回到2；,4重复2，3直到该顶点所有的相邻顶点都被访问过；,dfs(g,w);,void dfs（g ，v） visited v = 1; p = g v -next_adj while(p !
15、= NULL) w = p-node_index; if(visited w = 0) dfs( g, w ); p = p-next_adj; ,void dfs（g ，2） visited 2 = 1; p = g 2 -next_adj while(p != NULL) w = p-node_index; if(visited 3 = 0) dfs( g, 3 ); p = p-next_adj; ,void dfs（g ，3） visited 3 = 1; p = g 3 -next_adj while(p != NULL) w = p-node_index; if(visited 4 = 0) dfs( g , 4 ); p = p-next_adj; ,void dfs（g ，4） visited 4 = 1; p = g 4 -next_adj while(p != NULL) w = p-node_index; if(visited w = 0) dfs( g , w );
