2018图的存储与遍历及拓扑排序

1、图的存储遍历图的存储遍历 及拓扑排序及拓扑排序 李云军 引例 有n个岛屿，给出他们的坐标， 任意两个岛屿间可以铺设一条通信电缆， 如果需要实现任意两个岛屿间都能 直接或间接通讯，求最少需要铺设的 电缆长度是多少？ 某大学计算机专业的必修课及其先修课程如下表所示： 课程 代号 C0 1 C2C3C4C5C6C7 课程 名称 高等 数学 程序 设计 语言 离散 数学 数据 结构 编译 技术 操作 系统 普通 物理 计算 机原 理 先修 课程 C0, C1 C1, C2 C3 C3, C7 C0C6 请给出一种合理的课程安排方案 图的相关概念图的相关概念 如果数据元素集合中的各元素之间存在任如果数据

2、元素集合中的各元素之间存在任 意的关系，则此数据结构称为图。如果将数据意的关系，则此数据结构称为图。如果将数据 元素抽象为顶点，元素之间的关系用边表示，元素抽象为顶点，元素之间的关系用边表示， 则图亦可以表示为则图亦可以表示为G=G=（V V，E E），其中），其中V V是顶点是顶点 的有穷（非空）集合，的有穷（非空）集合，E E为边的集合。为边的集合。 1 1、图的分类：无向图、有向图、图的分类：无向图、有向图、 带权图带权图 无向图：边集无向图：边集E（G）中为无向边。）中为无向边。 有向图：边集有向图：边集E（G）中为有向边。）中为有向边。 带权图带权图 ：边上带有权的图。也称为网。（有

3、向带权图、：边上带有权的图。也称为网。（有向带权图、 无向带权图）无向带权图） 2、顶点的度、入度、出度、顶点的度、入度、出度 顶点的度：与该顶点相关联的边的数目，有奇点、偶点之分。顶点的度：与该顶点相关联的边的数目，有奇点、偶点之分。 对于有向图：有入度和出度之分对于有向图：有入度和出度之分 入度：该顶点的入边的数目。入度：该顶点的入边的数目。 出度：该顶点的出边的数目。出度：该顶点的出边的数目。 提问提问1：一个图中，全部顶点的度数为所有边数的一个图中，全部顶点的度数为所有边数的 倍倍; 2 提问提问2：有向图中所有顶点的入度之和是有向图中所有顶点的入度之和是(大于、等于、小于大于、等于、

4、小于) 所有顶点的出度之和；所有顶点的出度之和； 提问提问3：任意一个无向图一定有（偶数、奇数）个奇点；任意一个无向图一定有（偶数、奇数）个奇点； 完全图：若是无向图中，则每两个顶点之间都存在完全图：若是无向图中，则每两个顶点之间都存在 着一条边；若是有向图，则每两个顶点之间都存在着一条边；若是有向图，则每两个顶点之间都存在 着方向相反的两条边。着方向相反的两条边。 1 23 4 5 ab c d e f 3、完全图、稠密图、稀疏图、完全图、稠密图、稀疏图 稠密图：当一个图的边数接近完全图时。稠密图：当一个图的边数接近完全图时。 稀疏图：当一个图的边数远远少于完全图时。稀疏图：当一个图的边数远

5、远少于完全图时。 n*(n-1)/2 n*(n-1) 注意：注意：1 1）一个）一个n n阶的完全无向图含有阶的完全无向图含有 条边；条边； 2 2）一个）一个n n阶的完全有向图含有阶的完全有向图含有 条边；条边； 路径：对于图路径：对于图G=G=（V V，E E），对于顶点），对于顶点a a、b b，如果存在一些顶点序列，如果存在一些顶点序列 x x1 1=a,x=a,x2 2,x,xk k=b(k1)=b(k1)，且（，且（x xi i,x,xi+1 i+1） ）EE，i=1,2k-1i=1,2k-1，则称顶点序列，则称顶点序列 x x1 1,x,x2 2,x,xk k为顶点为顶点a a

6、到顶点到顶点b b的一条路径，而路径上边的数目（即的一条路径，而路径上边的数目（即k-1k-1） 称为该称为该路径的长度路径的长度。并称顶点集合。并称顶点集合xx1 1,x,x2 2,x,xk k 为一个连通集。为一个连通集。 简单路径：如果一条路径上的顶点除了起点和终点可以相同外，其它顶简单路径：如果一条路径上的顶点除了起点和终点可以相同外，其它顶 点均不相同，则称此路径为一条简单路径；起点和终点相同的简单路径点均不相同，则称此路径为一条简单路径；起点和终点相同的简单路径 称为称为回路（或环）回路（或环）。 4 4、子图、子图 1 23 4 5 1 23 图G图G 设两个图设两个图G=（V，

7、E）和）和 G=(V,E),若若V是是V的子集的子集,且且E 是是E的子集的子集,则称则称G是是G的子图。的子图。 5、路径和回路、路径和回路 路径和简单路径的举例：路径和简单路径的举例： 左图左图123123是一条简单路径，长度为是一条简单路径，长度为2 2， 而而1341313413就不是简单路径；就不是简单路径； 右图右图121121为一个回路。为一个回路。 连通图：连通图：如果一个无向图中，任意两个顶点之间都是连通的，则称该如果一个无向图中，任意两个顶点之间都是连通的，则称该 无向图为连通图。否则称为非连通图；左图为一个连通图。无向图为连通图。否则称为非连通图；左图为一个连通图。 连通

8、分量：连通分量：一个无向图的连通分支定义为该图的最大连通子图，左图一个无向图的连通分支定义为该图的最大连通子图，左图 的连通分量是它本身。的连通分量是它本身。 连通：连通：在一个图中，如果从顶点在一个图中，如果从顶点U U到顶点到顶点V V有路径，则称有路径，则称U U和和V V是连通的；是连通的； 6 6、连通和连通分量、连通和连通分量 注意：注意：任何连通图的连通分量只有一个，即本身，而非任何连通图的连通分量只有一个，即本身，而非 连通图有多个连通分量。连通图有多个连通分量。 强连通分量：强连通分量：一个有向图的强连通分量定义为该图的最大的强连通子图，一个有向图的强连通分量定义为该图的最大

9、的强连通子图， 右图含有两个强连通分量，一个是右图含有两个强连通分量，一个是1 1和和2 2构成的一个子图，一个是构成的一个子图，一个是3 3独立构成独立构成 的一个子图。的一个子图。 强连通图：强连通图：在一个有向图中，对于任意两个顶点在一个有向图中，对于任意两个顶点U U和和V V，都存在着一条从，都存在着一条从U U到到V V 的有向路径，同时也存在着一条从的有向路径，同时也存在着一条从V V到到U U的有向路径，则称该有向图为强连通的有向路径，则称该有向图为强连通 图；右图不是一个强连通图。图；右图不是一个强连通图。 7 7、强连通图和强连通分量强连通图和强连通分量 注意：注意：强连通

10、图只有一个强连通分量，即本身，非强连强连通图只有一个强连通分量，即本身，非强连 通图有多个强连通分量。通图有多个强连通分量。 图的存储图的存储 图型结构的存储分为静态存储和动态存储。我们介绍下面三种：邻图型结构的存储分为静态存储和动态存储。我们介绍下面三种：邻 接矩阵、邻接表（用数组模拟），边集数组。接矩阵、邻接表（用数组模拟），边集数组。 1 1、邻接矩阵邻接矩阵 相邻矩阵是表示顶点间相邻关系的矩阵。若相邻矩阵是表示顶点间相邻关系的矩阵。若G=G=（V V，E E） 是一个具有是一个具有n n个顶点的图，则个顶点的图，则G G的相邻矩阵是如下定义的的相邻矩阵是如下定义的 二维数组二维数组a

11、a，其规模为，其规模为n n* *n n 上图中的3个图对应的邻接矩阵分别如下： 0 1 1 1 0 1 1 5 8 3 G（A）= 1 0 1 1 G（B）= 0 0 1 5 2 6 1 1 0 0 0 1 0 G（C）= 8 2 10 4 1 1 0 0 10 11 3 6 4 11 下面是建立图的邻接矩阵的参考程序段： int i,j,k,e,n;double g101101;double w; int main() int i,j; for (i = 1; i = n; i+) for (j = 1; j e; for (k = 1; k i j w; gij = w; /对于不带权的

12、图gij=1 gji = w; /无向图的对称性,如果是有向图则不要有这句！ return 0; 邻接矩阵存储的特点 1、占用的存储单元数只与顶点数有关而与边数无关，占用的存储单元数只与顶点数有关而与边数无关，n n* *n n的二维数组。的二维数组。 2 2、方便度数的计算。、方便度数的计算。 3 3、容易判断两点之间是否有边相连。、容易判断两点之间是否有边相连。 4 4、寻找一个点、寻找一个点相连的所有边需要一个一到相连的所有边需要一个一到n n的循环。的循环。 17 2 2、邻接表邻接表 1 2 5 3 4 2 3 4 2 1 3 2 1 2 3 4 5 223243 123153 12

13、2152 1354 233244 头指针邻接点指针 结点邻接点指针 邻接点 边权值 下一个邻接点指针 数组模拟邻接表方法一 int g101101; 寻找顶点i有边相连的点可以这样来做，gi0表示i发出的边的数量， gij表示i发出的第j条边是通向哪个顶点的。 for (int j = 1; j = gi0; j+) .gij. 这样就可以处理i发出的每条边，也就能找到顶点i有边相连的顶点。 5 6 0 4 1 0 1 2 2 0 2 3 3 4 01234 1356 0123456 next002040 to402034 数组模拟邻接表方法二 0123456 next002040 to402

14、034 01234 1356 计算每个点的出度计算每个点的出度 邻接表存储特点 1、对于稀疏图，用链表实现的邻接表，可以节省内存。 2、可以快速找到与当前顶点相连的点。 3、判断两点是否相连不如邻接矩阵快速。 3 3、边集数组边集数组 边集数组：边集数组：是利用一维数组存储图中所有边的一种图的表是利用一维数组存储图中所有边的一种图的表 示方法。示方法。 V1 V2V3 V4 5 7 12 3 8 起点起点 终点终点 权权 无向带权图的边集数组表示法无向带权图的边集数组表示法 从图中某一顶点出发系统地访问图中所有顶点，使从图中某一顶点出发系统地访问图中所有顶点，使 每个顶点恰好被访问一次，这种运

15、算操作被称为图的遍每个顶点恰好被访问一次，这种运算操作被称为图的遍 历历。 遍历可以采取两种方法进行：遍历可以采取两种方法进行： 深度优先深度优先遍历遍历 广度优先广度优先遍历遍历 1 1、图的深度优先遍历、图的深度优先遍历 对下面两个图分别进行深度优先遍历，写出对下面两个图分别进行深度优先遍历，写出 遍历结果。注意：分别从遍历结果。注意：分别从a a和和V1V1出发。出发。 左图从顶点左图从顶点a a出发，进行深度优先遍历的结果为：出发，进行深度优先遍历的结果为： a a，b b，c c，d d，e e，g g，f f 右图从右图从V V1 1出发进行深度优先遍历的结果为：出发进行深度优先遍

16、历的结果为： V V1 1，V V2 2，V V4 4，V V8 8，V V5 5，V V3 3，V V6 6，V V7 7 图的遍历分为图的遍历分为深度优先遍历和广度（宽度）优先遍历深度优先遍历和广度（宽度）优先遍历两种方法。两种方法。 为了避免重复访问某个顶点，可以设一个标志数组visi， 未访问时值为0，访问一次后就改为1。 /DFS参考代码/DFS参考代码 #include #include const int maxn=1010;const int maxn=1010; int amaxnmaxn;int amaxnmaxn; int vismaxn;int vismaxn; int

17、 n,m;int n,m; void dfs(int u)void dfs(int u) printf(%dn,u);printf(%dn,u); visu=1;visu=1; for(int i=1;i=n;i+)for(int i=1;i=n;i+) if(aui=1if(aui=1 对下面两个图分别从对下面两个图分别从a a和和V1V1出发进行广度优先出发进行广度优先 遍历，写出遍历结果。遍历，写出遍历结果。 2 2、图的广度优先遍历、图的广度优先遍历 左图从顶点左图从顶点a a出发，进行广度优先遍历的结果为：出发，进行广度优先遍历的结果为： a a，b b，d d，e e，f f，c

18、c，g g 右图从右图从V1V1出发进行广度优先遍历的结果为：出发进行广度优先遍历的结果为： V V1 1，V V2 2，V V3 3，V V4 4，V V5 5，V V6 6，V V7 7，V V8 8 广度优先遍历广度优先遍历的实现：的实现： 为避免重复访问，也需要一个状态数组为避免重复访问，也需要一个状态数组 visn，用来，用来 存储各顶点的访问状态。如果存储各顶点的访问状态。如果 visi = 1，则表示顶点，则表示顶点 i 已已 经访问过；如果经访问过；如果 visi = 0，则表示顶点，则表示顶点 i 还未访问过。初还未访问过。初 始时，各顶点的访问状态均为始时，各顶点的访问状态

19、均为 0。 为了实现逐层访问，为了实现逐层访问， BFS 算法在实现时需要使用一个算法在实现时需要使用一个 队列队列. BFS( 顶点顶点 i ) /从顶点从顶点 i 进行广度优先搜索进行广度优先搜索 visitedi = 1; /将顶点将顶点 i 的访问标志置为的访问标志置为 1 将顶点将顶点 i 入队列入队列; while( 队列不为空队列不为空 ) 取出队列头的顶点，设为取出队列头的顶点，设为 k for( j=0; jn; j+ ) /对其他所有顶点对其他所有顶点 j /j是是k的邻接顶点，且顶点的邻接顶点，且顶点j没有访问过没有访问过 if( akj=1 using namespac

20、e std; const int maxn=1010;const int maxn=1010; int qmaxn;int qmaxn; int amaxnmaxn;int amaxnmaxn; int vismaxn;int vismaxn; int n,m;int n,m; void bfs(int u)void bfs(int u) int head=0,tail=1;int head=0,tail=1; q0=u;q0=u; 如果是非连通图，主程序做如下修改如果是非连通图，主程序做如下修改: int main() memset(vis,0,sizeof(vis); for (int i

21、 = 1; i = n; i+) if (visi=0) dfs(i); return 0; 1 2 3 4 5 以3为起点根本不能 遍历整个图 这个非连通无向图任何一 个点为起点都不能遍历整 个图 1 4 5 2 3 例例1：公司数量1：公司数量 【问题描述】【问题描述】 在某个城市里住着n个人，现在给定关 在某个城市里住着n个人，现在给定关 于 n个人的m条信息（即某2个人认识），假于 n个人的m条信息（即某2个人认识），假 设所有认识（直接或间接认识都算认识）的设所有认识（直接或间接认识都算认识）的 人一定属于同一个公司。人一定属于同一个公司。 若是某两人不在给出的信息里，那么他 若是某

22、两人不在给出的信息里，那么他 们不认识，属于两个不同的公司。们不认识，属于两个不同的公司。 已知人的编号从1至n。 已知人的编号从1至n。 请计算该城市最多有多少公司。 请计算该城市最多有多少公司。 【输入】【输入】 第一行：n（=10000,人数）， 第一行：n（=10000,人数）， city.incity.out 11 9 1 2 4 5 3 4 1 3 5 6 7 10 5 10 6 10 8 9 3 【数据规模】【数据规模】 100%的的数据：数据： n=10000； m=100000。 分析分析 以人为图的顶点，相互认识的建立无向边，求无向图以人为图的顶点，相互认识的建立无向边，求

23、无向图 的连通分量数的连通分量数。 4 45 5 6 6 7 71010 8 83 31 12 2 9 9 1111 /深度优先参考代码/深度优先参考代码 #include #include const int maxn=10010;const int maxn=10010; int amaxnmaxn;int amaxnmaxn; int vismaxn;int vismaxn; int n,m,cnt;int n,m,cnt; void dfs(int k)void dfs(int k) visk=1;visk=1; for(int i=1;i=n;i+)for(int i=1;i=n;i

24、+) if(!visiif(!visi int main()int main() scanf(%d%d,scanf(%d%d, int x,y;int x,y; for(int i=1;i=m;i+)for(int i=1;i=m;i+) /广度优先参考代码/广度优先参考代码 #include #include const int maxn=10010;const int maxn=10010; int amaxnmaxn;int amaxnmaxn; int vismaxn;int vismaxn; int qmaxn;int qmaxn; int n,m,cnt;int n,m,cnt;

25、void bfs(int k)void bfs(int k) int head=0,tail=1;int head=0,tail=1; q0=k;q0=k; visk=1;visk=1; while(headtail)while(headtail) int p=qhead+;int p=qhead+; for(int i=1;i=n;i+)for(int i=1;i=n;i+) if(!visiusing namespace std; const int maxn=110;const int maxn=110; const int dx8=-1,1,0,0,-1,1,-1,1;const in

26、t dx8=-1,1,0,0,-1,1,-1,1; const int dy8=0,0,-1,1,-1,1,1,-1; const int dy8=0,0,-1,1,-1,1,1,-1; int gmaxnmaxn;int gmaxnmaxn; int n,m,cnt;int n,m,cnt; void dfs(int x,int y)void dfs(int x,int y) gxy=0;gxy=0; /BFS:油田/BFS:油田 #include #include #include #include #include #include using namespace std;using n

27、amespace std; const int maxn=110;const int maxn=110; const int dx8=-1,1,0,0,-1,1,-1,1;const int dx8=-1,1,0,0,-1,1,-1,1; const int dy8=0,0,-1,1,-1,1,1,-1; const int dy8=0,0,-1,1,-1,1,1,-1; int gmaxnmaxn;int gmaxnmaxn; int n,m,cnt;int n,m,cnt; struct nodestruct node int x,y;int x,y; 例例3红与黑(zoj2165 poj

28、1979)3红与黑(zoj2165 poj1979) 题目描述： 题目描述： 有一个长方形的房间，房间里的地面上 有一个长方形的房间，房间里的地面上 布满了正方形的瓷砖，瓷砖要么是红色，要布满了正方形的瓷砖，瓷砖要么是红色，要 么是黑色。一男子站在其中一块黑色的瓷砖么是黑色。一男子站在其中一块黑色的瓷砖 上。男子可以向他四周的瓷砖上移动，但不上。男子可以向他四周的瓷砖上移动，但不 能移动到红色的瓷砖上，只能在黑色的瓷砖能移动到红色的瓷砖上，只能在黑色的瓷砖 上移动。 上移动。 本题的目的就是要编写程序，计算他在 本题的目的就是要编写程序，计算他在 这个房间里可以到达的黑色瓷砖的数量。这个房间里

29、可以到达的黑色瓷砖的数量。 输入描述：输入描述： 输入文件中包含多个测试数据。 输入文件中包含多个测试数据。 每个测试数据的第 1 行为两个整数 W 每个测试数据的第 1 行为两个整数 W 和 H，分别表示长方形房间里 x 方向和 y 和 H，分别表示长方形房间里 x 方向和 y 方向上瓷砖的数目。W 和 H 的值不超过方向上瓷砖的数目。W 和 H 的值不超过 分析：分析： 求男子所在位置能到达的黑色求男子所在位置能到达的黑色 的连通块的大小。的连通块的大小。 从起点遍历图即可。从起点遍历图即可。 样例输入：样例输入： 6 9 6 9 .#.#. .#.# . . . . . #.#.# .#

30、.#.#.#. 11 911 9 /DFS:红与黑/DFS:红与黑 #include #include #include #include #include #include using namespace std;using namespace std; const int maxn=110;const int maxn=110; const int dx4=-1,1,0,0;const int dx4=-1,1,0,0; const int dy4=0,0,-1,1; const int dy4=0,0,-1,1; int gmaxnmaxn;int gmaxnmaxn; int n,m,

31、sx,sy,cnt;int n,m,sx,sy,cnt; void dfs(int x,int y)void dfs(int x,int y) cnt+;cnt+; gxy=0;gxy=0; for(int i=0;i4;i+)for(int i=0;i4;i+) int xx=x+dxi;int xx=x+dxi; /BFS:红与黑/BFS:红与黑 #include #include #include #include #include #include using namespace std;using namespace std; const int maxn=110;const int

32、 maxn=110; const int dx4=-1,1,0,0;const int dx4=-1,1,0,0; const int dy4=0,0,-1,1; const int dy4=0,0,-1,1; int gmaxnmaxn;int gmaxnmaxn; int n,m,sx,sy;int n,m,sx,sy; struct nodestruct node int x,y;int x,y; cur,nxt;cur,nxt; node qmaxn*maxn;node qmaxn*maxn; void bfs(int x,int y)void bfs(int x,int y) 1 2

33、 3 5 6 7 8 94 12 34 拓扑排序算法 A B C E D A B C D 开始时，只有A 入度为0，A入栈。 栈：A B C D 栈顶元素A出栈并输出A， A的后继B、C入度减1，相 当于删除A的所有关联边 栈：空 拓扑序列：A B C D B、C的入度都变成0， 依次将B、C入栈。 栈：BC（入栈顺序不唯一） 拓扑序列：A B D 栈顶元素C出栈并输出 C，C的后继D入度减1 栈：B 拓扑序列：AC D 栈顶元素B出栈并输出B， B的后继D入度再减1。这 时D入度为0，入栈。 栈：D 拓扑序列：ACB D 栈顶元素D出栈并输出 D。栈空，结束 栈：空 拓扑序列：ACBD（不唯

34、一） 【例【例4】、家谱树4】、家谱树 【问题描述】【问题描述】 有个人的家族很大，辈分关系很混乱， 有个人的家族很大，辈分关系很混乱， 请你帮整理一下这种关系。请你帮整理一下这种关系。 给出每个人的孩子的信息。 给出每个人的孩子的信息。 输出一个序列，使得每个人的后辈都比 输出一个序列，使得每个人的后辈都比 那个人后列出。那个人后列出。 【输入格式】【输入格式】 第1行一个整数N（1=N=100），表示 第1行一个整数N（1=N=100），表示 家族的人数。家族的人数。 接下来N行，第I行描述第I个人的儿 接下来N行，第I行描述第I个人的儿 子。子。 每行最后是0表示描述完毕。 每行最后是0

35、表示描述完毕。 【输出格式】【输出格式】 输出一个序列，使得每个人的后辈都比 输出一个序列，使得每个人的后辈都比 #include#include #include#include using namespace std;using namespace std; int a101101,c101,r101,ansint a101101,c101,r101,ans 101;101; int i,j,tot,temp,num,n,m;int i,j,tot,temp,num,n,m; int main()int main() cin n; cin n; for (i = 1; i = n; i+) for (i = 1; i j; cin j; if