第四章 图论算法.

Presentation on theme: "第四章 图论算法."— Presentation transcript:

1 第四章 图论算法

2 第一节 基本概念 1 2 3 4 5 (a) (b) 1 2 3 4 5 一、什么是图？
　　很简单，点用边连起来就叫做图，严格意义上讲，图是一种数据结构，定义为：graph=（V，E）。V是一个非空有限集合，代表顶点（结点），E代表边的集合。 二、图的一些定义和概念 (a)有向图：图的边有方向，只能按箭头方向从一点到另一点。(a)就是一个有向图。 (b)无向图：图的边没有方向，可以双向。(b)就是一个无向图。 结点的度：无向图中与结点相连的边的数目，称为结点的度。 结点的入度：在有向图中，以这个结点为终点的有向边的数目。 结点的出度：在有向图中，以这个结点为起点的有向边的数目。 权值：边的“费用”，可以形象地理解为边的长度。 连通：如果图中结点U，V之间存在一条从U通过若干条边、点到达V的通路，则称U、V 是连通的。 回路：起点和终点相同的路径，称为回路，或“环”。 完全图：一个n 阶的完全无向图含有n*(n-1)/2 条边；一个n 阶的完全有向图含有n*(n-1)条边； 　　　　稠密图：一个边数接近完全图的图。 　　　　稀疏图：一个边数远远少于完全图的图。 强连通分量：有向图中任意两点都连通的最大子图。右图中，1-2-5构成一个强连通分量。特殊地，单个点也算一个强连通分量，所以右图有三个强连通分量：1-2-5，4，3。 1 2 3 4 5 (a) (b) 1 2 3 4 5

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.二维数组邻接矩阵存储 定义int G[101][101]; G[i][j]的值，表示从点i到点j的边的权值，定义如下： 　　上图中的3个图对应的邻接矩阵分别如下： 　　 ∞ ∞ 3 G（A）= G（B）= ∞ 2 ∞ 6 　　 G（C）= ∞ 　　 ∞ ∞ 10 ∞ 11 　　 ∞

4 下面是建立图的邻接矩阵的参考程序段： 建立邻接矩阵时，有两个小技巧: #include<iostream>
using namespace std; int i,j,k,e,n; double g[101][101]; double w; int main() { int i,j; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) g[i][j] = 0x7fffffff（赋一个超大值）; //初始化，对于不带权的图g[i][j]=0，表示没有边连通。这里用0x7fffffff代替无穷大。 cin >> e; for (k = 1; k <= e; k++) cin >> i >> j >> w; //读入两个顶点序号及权值 g[i][j] = w; //对于不带权的图g[i][j]=1 g[j][i] = w; //无向图的对称性,如果是有向图则不要有这句！ } ………… return 0; 建立邻接矩阵时，有两个小技巧: 　　初始化数组大可不必使用两重for循环。 　　1)　　如果是int数组，采用memset(g, 0x7f, sizeof(g))可全部初始化为一个很大的数(略小于0x7fffffff)，使用memset(g, 0, sizeof(g))，全部清为0，使用memset(g, 0xaf, sizeof(g))，全部初始化为一个很小的数。　　 2)如果是double数组，采用memset(g,127,sizeof(g));可全部初始化为一个很大的数1.38*10306，使用memset(g, 0, sizeof(g))全部清为0.

5 2.数组模拟邻接表存储 　　图的邻接表存储法，又叫链式存储法。本来是要采用链表实现的，但大多数情况下只要用数组模拟即可。 　　以下是用数组模拟邻接表存储的参考程序段： #include <iostream> using namespace std; const int maxn=1001,maxm=100001; struct Edge { int next; //下一条边的编号 int to; //这条边到达的点 int dis; //这条边的长度 }edge[maxm]; int head[maxn],num_edge,n,m,u,v,d; void add_edge(int from,int to,int dis) //加入一条从from到to距离为dis的单向边 edge[++num_edge].next=head[from]; edge[num_edge].to=to; edge[num_edge].dis=dis; head[from]=num_edge; }

6 两种方法各有用武之地，需按具体情况，具体选用。
int main() { num_edge=0; scanf("%d %d",&n,&m); //读入点数和边数 for(int i=1;i<=m;i++) scanf("%d %d %d",&u,&v,&d); //u、v之间有一条长度为d的边 add_edge(u,v,d); } for(int i=head[1];i!=0;i=edge[i].next) //遍历从点1开始的所有边 //... return 0; 两种方法各有用武之地，需按具体情况，具体选用。

7 第二节 图的遍历 一、深度优先与广度优先遍历
　　从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组visited[i]，未访问时值为false，访问一次后就改为true。 　　图的遍历分为深度优先遍历和广度优先遍历两种方法，两者的时间效率都是O(n*n)。 1.深度优先遍历 　　深度优先遍历与深搜DFS相似，从一个点A出发，将这个点标为已访问visited[i]:=true;，然后再访问所有与之相连，且未被访问过的点。当A的所有邻接点都被访问过后，再退回到A的上一个点（假设是B），再从B的另一个未被访问的邻接点出发，继续遍历。 　　例如对右边的这个无向图深度优先遍历，假定先从1出发 　　程序以如下顺序遍历： 　　1→2→5，然后退回到2，退回到1。 　　从1开始再访问未被访问过的点3 ，3没有未访问的邻接点，退回1。 　　再从1开始访问未被访问过的点4，再退回1 。 　　起点1的所有邻接点都已访问，遍历结束。 1 2 3 4 5

8 这个非连通无向图任何一个点为起点都不能遍历整个图
下面给出的深度优先遍历的参考程序，假设图以邻接表存储 　void dfs(int i) //图用数组模拟邻接表存储，访问点i 　{ 　　 visited[i] = true; //标记为已经访问过 　　 for (int j = 1; j <= num[i]; j++) //遍历与i相关联的所有未访问过的顶点 　　 if (!visited[g[i][j]]) 　　 dfs(g[i][j]); 　} 主程序如下: 　int main() …… memset(visited,false,sizeof(visited)); for (int i = 1; i <= n; i++) //每一个点都作为起点尝试访问，因为不是从任何 //一点开始都能遍历整个图的，例如下面的两个图。 if (!visited[i]) dfs(i); return 0; 1 2 3 4 5 以3为起点根本不能遍历整个图 这个非连通无向图任何一个点为起点都不能遍历整个图

9 2.广度优先遍历 　　广度优先遍历并不常用，从编程复杂度的角度考虑，通常采用的是深度优先遍历。 　　广度优先遍历和广搜BFS相似，因此使用广度优先遍历一张图并不需要掌握什么新的知识，在原有的广度优先搜索的基础上，做一点小小的修改，就成了广度优先遍历算法。 二、一笔画问题 　　如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。 　　我们定义奇点是指跟这个点相连的边数目有奇数个的点。对于能够一笔画的图，我们有以下两个定理。 　　　定理1：存在欧拉路的条件：图是连通的，有且只有2个奇点。 　　　定理2：存在欧拉回路的条件：图是连通的，有0个奇点。 　　两个定理的正确性是显而易见的，既然每条边都要经过一次，那么对于欧拉路，除了起点和终点外，每个点如果进入了一次，显然一定要出去一次，显然是偶点。对于欧拉回路，每个点进入和出去次数一定都是相等的，显然没有奇点。 　　求欧拉路的算法很简单，使用深度优先遍历即可。 　　根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行DFS，时间复杂度为O(m+n)，m为边数，n是点数。

10 以下是寻找一个图的欧拉路的算法实现： 样例输入:第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。 5 5 1 2 2 3 3 4 4 5 5 1 样例输出:欧拉路或欧拉回路

11 【参考程序】Euler.cpp 　　#include<iostream> 　　#include<cstring> 　　using namespace std; 　　#define maxn 101 　　int g[maxn][maxn]; //此图用邻接矩阵存储 　　int du[maxn]; //记录每个点的度，就是相连的边的数目 　　int circuit[maxn]; //用来记录找到的欧拉路的路径 　　int n,e,circuitpos,i,j,x,y,start; 　　void find_circuit(int i) //这个点深度优先遍历过程寻找欧拉路 　　{ 　　 int j; 　　 for (j = 1; j <= n; j++) 　　 if (g[i][j] == 1) //从任意一个与它相连的点出发 　　 { 　　 g[j][i] = g[i][j] = 0; 　　 find_circuit(j); 　　 } 　　 circuit[++circuitpos] = i; //记录下路径 　　}

12 　　int main() 　　{ 　　 memset(g,0,sizeof(g)); 　　 cin >> n >> e; 　　 for (i = 1; i <= e; i++) 　　 { 　　 cin >> x >> y; 　　 g[y][x] = g[x][y] = 1; 　　 du[x]++; //统计每个点的度 　　 du[y]++; 　　 } 　　 start = 1; //如果有奇点，就从奇点开始寻找，这样找到的就是 　　 for (i = 1; i <= n; i++) //欧拉路。没有奇点就从任意点开始， 　　 if (du[i]%2 == 1) //这样找到的就是欧拉回路。(因为每一个点都是偶点) start = i; 　　 circuitpos = 0; 　　 find_circuit(start); 　　 for (i = 1; i <= circuitpos; i++) 　　 cout << circuit[i] << ' '; 　　 cout << endl; 　　 return 0; 　　}

13 　　注意以上程序具有一定的局限性，对于下面这种情况它不能很好地处理：
　　上图具有多个欧拉回路，而本程序只能找到一个回路。读者在遇到具体问题时，还应对程序作出相应的修改。

14 三、哈密尔顿环 　　欧拉回路是指不重复地走过所有路径的回路，而哈密尔顿环是指不重复地走过所有的点，并且最后还能回到起点的回路。 　　使用简单的深度优先搜索，就能求出一张图中所有的哈密尔顿环。下面给出一段参考程序： #include<iostream> #include<cstring> using namespace std; int start,length,x,n; bool visited[101],v1[101]; int ans[101], num[101]; int g[101][101]; void print() { int i; for (i = 1; i <= length; i++) cout << ' ' << ans[i]; cout << endl; }

15 void dfs(int last,int i) //图用数组模拟邻接表存储，访问点i，last表示上次访问的点
{ visited[i] = true; //标记为已经访问过 v1[i] = true; //标记为已在一张图中出现过 ans[++length] = i; //记录下答案 for (int j = 1; j <= num[i]; j++) 　　{ 　　 if (g[i][j]==x&&g[i][j]!=last) //回到起点，构成哈密尔顿环 　　 { 　　 ans[++length] = g[i][j]; 　　 print(); //这里说明找到了一个环，则输出ans数组。 　　 length--; 　　 break; 　　 } if (!visited[g[i][j]]) dfs(i,g[i][j]); //遍历与i相关联的所有未访问过的顶点 } length--; visited[i] = false; //这里是回溯过程，注意v1的值不恢复。

16 int main() { memset(visited,false,sizeof(visited)); memset(v1,false,sizeof(v1)); for (x = 1; x <= n; x++) //每一个点都作为起点尝试访问，因为不是从任何一点开始都能找过整个图的 if (!v1[x]) //如果点x不在之前曾经被访问过的图里。 length = 0; //定义一个ans数组存答案，length记答案的长度。 dfs(x); } return 0;

17 【上机练习】 1、珍珠BEAD 【问题描述】 有n颗形状和大小都一致的珍珠，它们的重量都不相同。n为整数，所有的珍珠从1到n编号。你的任务是发现哪颗珍珠的重量刚好处于正中间，即在所有珍珠的重量中，该珍珠的重量列(n+1)/2位。下面给出将一对珍珠进行比较的办法： 给你一架天平用来比较珍珠的重量，我们可以比出两个珍珠哪个更重一些，在作出一系列的比较后，我们可以将某些肯定不具备中间重量的珍珠拿走。 　　例如，下列给出对5颗珍珠进行四次比较的情况： 　　1、珍珠2比珍珠1重 　　2、珍珠4比珍珠3重 　　3、珍珠5比珍珠1重 　　4、珍珠4比珍珠2重 　　根据以上结果，虽然我们不能精确地找出哪个珍珠具有中间重量，但我们可以肯定珍珠1和珍珠4不可能具有中间重量，因为珍珠2、4、5比珍珠1重，而珍珠1、2、3比珍珠4轻，所以我们可以移走这两颗珍珠。 写一个程序统计出共有多少颗珍珠肯定不会是中间重量。 【输入格式】 　　　输入文件第一行包含两个用空格隔开的整数N和M，其中1<=N<=99，且N为奇数，M表示对珍珠进行的比较次数，接下来的M行每行包含两个用空格隔开的整数x和y，表示珍珠x比珍珠y重。 【输出格式】 　　　输出文件仅一行包含一个整数，表示不可能是中间重量的珍珠的总数。 【输入样例】BEAD.IN 　　5 4 　　2 1 　　4 3 　　5 1 　　4 2 【输出样例】BEAD.OUT 　　2

18 2、铲雪车snow 【问题描述】 　　随着白天越来越短夜晚越来越长，我们不得不考虑铲雪问题了。整个城市所有的道路都是双车道，因为城市预算的削减，整个城市只有1辆铲雪车。铲雪车只能把它开过的地方（车道）的雪铲干净，无论哪儿有雪，铲雪车都得从停放的地方出发，游历整个城市的街道。现在的问题是：最少要花多少时间去铲掉所有道路上的雪呢？ 【输入格式】 　　输入数据的第1行表示铲雪车的停放坐标（x,y），x，y为整数，单位为米。下面最多有100行，每行给出了一条街道的起点坐标和终点坐标，所有街道都是笔直的，且都是双向一个车道。铲雪车可以在任意交叉口、或任何街道的末尾任意转向，包括转U型弯。铲雪车铲雪时前进速度为20 km/h，不铲雪时前进速度为50 km/h。 　　保证：铲雪车从起点一定可以到达任何街道。 【输出格式】 铲掉所有街道上的雪并且返回出发点的最短时间，精确到分种。 【输入样例】 　　1 　　0 0 　　 　　 　　 【输出样例】 　　3:55 【注解】 　　3小时55分钟

19 3、骑马修栅栏 【问题描述】 　　农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。 　　John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。 　　每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(>=1)个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。 　　你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个 (也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的，等等)。 输入数据保证至少有一个解。 【输入格式】fence.in 　　第1行: 一个整数F(1 <= F <= 1024)，表示栅栏的数目 　　第2到F+1行: 每行两个整数i, j(1 <= i,j <= 500)表示这条栅栏连接i与j号顶点。 【输出格式】fence.out 　　输出应当有F+1行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。

20 【输入样例】 【输出样例】 9 1 2 2 3 3 4 4 2 4 5 2 5 5 6 5 7 4 6 1 2 3 4 5 6 7