第四章 图论算法.

Slides:



Advertisements
Similar presentations
因数与倍数 2 、 5 的倍数的特征
Advertisements

3 的倍数的特征 的倍数有 : 。 5 的倍数有 : 。 既是 2 的倍数又是 5 的倍数有 : 。 12 , 18 , 20 , 48 , 60 , 72 , , 25 , 60 ,
练一练: 在数轴上画出表示下列各数的点, 并指出这些点相互间的关系: -6 , 6 , -3 , 3 , -1.5, 1.5.
3.4 空间直线的方程.
小学生游戏.
最大团问题 回溯法应用 作者:余新华 时间:
第4章 数组 数组是由一定数目的同类元素顺序排列而成的结构类型数据 一个数组在内存占有一片连续的存储区域 数组名是存储空间的首地址
第三节 格林公式及其应用(2) 一、曲线积分与路径无关的定义 二、曲线积分与路径无关的条件 三、二元函数的全微分的求积 四、小结.
图 2008赛前知识点梳理三.
探索三角形相似的条件(2).
初中数学八年级下册 (苏科版) 10.4 探索三角形 相似的条件(2).
C++中的声音处理 在传统Turbo C环境中,如果想用C语言控制电脑发声,可以用Sound函数。在VC6.6环境中如果想控制电脑发声则采用Beep函数。原型为: Beep(频率,持续时间) , 单位毫秒 暂停程序执行使用Sleep函数 Sleep(持续时间), 单位毫秒 引用这两个函数时,必须包含头文件
C++程序设计 王希 图书馆三楼办公室.
第六章 图(一).
第七章 图 (Graph)
Ch.7 图 图是一种复杂的非线性结构 应用:AI、工程、数学、生物、计算机 结点间的逻辑关系:任两个结点都可能相关
第七章 图 7.1 图的基本概念 7.2 图的存储表示 7.3 图的遍历 7.4 图的生成树 7.5 最短路径 7.6 拓扑排序
函數(一) 自訂函數、遞迴函數 綠園.
图(一).
图的遍历.
C++语言程序设计 C++语言程序设计 第六章 指针和引用 第十一组 C++语言程序设计.
强连通分量 无向图 1、任意两顶点连通称该图为连通图 2、否则将其中的极大连通子图称为连通分量 A D C B E 有向图
第七章 图 知识点2:图的存储结构.
第七章 图 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
第七章 图.
C++语言程序设计 C++语言程序设计 第六章 指针和引用 第十一组 C++语言程序设计.
切換Dev c++顯示語言 工具->環境選項(V)->介面->language (Chinese TW)
绿色圃中小学教育网 比例 比例的意义 绿色圃中小学教育网
使用矩阵表示 最小生成树算法.
宁波市高校慕课联盟课程 与 进行交互 Linux 系统管理.
宁波市高校慕课联盟课程 与 进行交互 Linux 系统管理.
无向树和根树.
第六节 最小生成树.
第四章 第三节 最短路径算法.
第6章 图 本章中介绍下列主要内容: 图的定义 图的存储结构 图的遍历操作 图的几个典型问题.
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
线段的有关计算.
复习 图的定义和术语 图(Graph)、有向图、无向图、子图、有向完全图 、完全图、稀疏图、稠密图、权、网、邻接点、相关边、度、路径、路径长度、回路、简单路径、简单回路、连通、连通图、连通分量、强连通图、强连通分量、生成树 图的存储方法 给定一个图,画出邻接矩阵、邻接表 图的邻接矩阵和邻接表的存储算法.
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
C++语言程序设计 C++语言程序设计 第三章 控制语句 第十一组 C++语言程序设计.
12.2全等三角形的判定(2) 大连市第三十九中学 赵海英.
物件導向程式設計 CH2.
用计算器开方.
常宝宝 北京大学计算机科学与技术系 数据结构(六) 常宝宝 北京大学计算机科学与技术系
第11章 從C到C++語言 11-1 C++語言的基礎 11-2 C++語言的資料型態與運算子 11-3 C++語言的輸出與輸入
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
图论初步 柏钧文.
C++程式設計入門 變數與運算子 作者:黃建庭.
iSIGHT 基本培训 使用 Excel的栅栏问题
知识点回顾 图的深度优先和广度优先遍历思想 图的深度优先遍历算法(用邻接表作为存储结构) 图的广度优先遍历算法(用邻接矩阵作为存储结构)
3.16 枚举算法及其程序实现 ——数组的作用.
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
树和图 tree and graph 蔡亚星.
第4课时 绝对值.
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
O x y i j O x y i j a A(x, y) y x 5.4 平面向量的坐标运算 5.4 平面向量的坐标运算 5.4 平面向量的坐标运算 5.4 平面向量的坐标运算 5.4 平面向量的坐标运算 5.4 平面向量的坐标运算 5.4 平面向量的坐标运算.
第七、八次实验要求.
分数再认识三 真假带分数的练习课.
实验目的:掌握数据的顺序存储结构及它们在计算机中的操作。 实验内容:
基于列存储的RDF数据管理 朱敏
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
4.2 图的存储结构(cont.) v1 v2 v3 v4 v5 vertex= v1 v2 v3 v4 v5 v
3.4 角的比较.
位似.
§4.5 最大公因式的矩阵求法( Ⅱ ).
H a S = a h.
最小生成树 最优二叉树.
第三章 图形的平移与旋转.
3.3.2 两点间的距离 山东省临沂第一中学.
Presentation transcript:

第四章 图论算法

第一节 基本概念 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

三、图的存储结构 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个图对应的邻接矩阵分别如下:    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 ∞

下面是建立图的邻接矩阵的参考程序段: 建立邻接矩阵时,有两个小技巧: #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.

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; }

两种方法各有用武之地,需按具体情况,具体选用。 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; 两种方法各有用武之地,需按具体情况,具体选用。

第二节 图的遍历 一、深度优先与广度优先遍历   从图中某一顶点出发系统地访问图中所有顶点,使每个顶点恰好被访问一次,这种运算操作被称为图的遍历。为了避免重复访问某个顶点,可以设一个标志数组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

这个非连通无向图任何一个点为起点都不能遍历整个图 下面给出的深度优先遍历的参考程序,假设图以邻接表存储  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为起点根本不能遍历整个图 这个非连通无向图任何一个点为起点都不能遍历整个图

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

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

【参考程序】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; //记录下路径   }

  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;   }

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

三、哈密尔顿环   欧拉回路是指不重复地走过所有路径的回路,而哈密尔顿环是指不重复地走过所有的点,并且最后还能回到起点的回路。   使用简单的深度优先搜索,就能求出一张图中所有的哈密尔顿环。下面给出一段参考程序: #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; }

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的值不恢复。

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;

【上机练习】 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

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

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行,每行一个整数,依次表示路径经过的顶点号。注意数据可能有多组解,但是只有上面题目要求的那一组解是认为正确的。

【输入样例】 【输出样例】 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