《图及其应用一课件》由会员分享，可在线阅读，更多相关《图及其应用一课件（79页珍藏版）》请在金锄头文库上搜索。
1、一、一、图的基本概念图的基本概念1、图的的定义、图的的定义 图是由顶点图是由顶点V V的集合和边的集合和边E E的集合组成的二元组：的集合组成的二元组： 记记G=G=（V V，E E） 2、无向图和有向图、无向图和有向图无向图：无向图： 在图在图G=G=（V V，E E）中，如果对于任意的）中，如果对于任意的a a，bVbV，当，当(a(a，b)Eb)E时，必有（时，必有（b b，a a）E E（即关系（即关系R R对称），对称图为无向对称），对称图为无向图。图。在一无向图中用不带箭头的边连接两个有关联的顶点。在一无向图中用不带箭头的边连接两个有关联的顶点。V=V1,V2,V3,V4,V5E=
2、(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1) 有向图：有向图：如果对于任意的如果对于任意的a a，bVbV，当，当(a(a，b)Eb)E时时 ，(b(b，a)Ea)E未必成未必成立，则称此图为有向图。立，则称此图为有向图。在有向图中，通常用带箭头的边连接两个有关联的结点。在有向图中，通常用带箭头的边连接两个有关联的结点。V=V1,V2,V3,V4 V=V1,V2,V3,V4 E=, E=, 顶点的度：顶点的度：无向图：与顶点关联的边的数目。无向图：与顶点关联的边的数目。有向图：等于该顶点的入度与出度之和。有向图：等于该顶点的入度
3、与出度之和。入度入度以该顶点为终点的边的数目和以该顶点为终点的边的数目和出度出度以该顶点为起点的边的数目和以该顶点为起点的边的数目和 度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。3 3、顶点的度、顶点的度 练习题练习题: : 1. 1. 假设我们用假设我们用d=(a1,a2,.,a5),d=(a1,a2,.,a5),表示无向图表示无向图G G的的5 5个顶点个顶点的度数，下面给出的哪（些）组的度数，下面给出的哪（些）组d d 值合理（值合理（ ）。）。 A A）55，4 4，4 4，3 3，1 B1 B）44，2 2，2 2，1 1，1
4、C1 C）33，3 3，3 3，2 2，22 D D）55，4 4，3 3，2 2，1 E1 E）22，2 2，2 2，2 2，222.2.无向图无向图G G有有1616条边，有条边，有3 3个个4 4度顶点、度顶点、4 4个个3 3度顶点，其余顶度顶点，其余顶点的度均小于点的度均小于3 3，则，则G G至少至少_个顶点。个顶点。4 4、 路径和连通集路径和连通集 在在图图G=G=（V V，E E）中中，如如果果对对于于结结点点a a，b b，存存在在满满足足下下述述条条件的结点序列件的结点序列x x1 1xxk k(k1)(k1) x x1 1=a=a，x xk k=b=b (x (xi i
5、，x xi+1i+1) )E i=1E i=1k-1k-1则则称称结结点点序序列列x x1 1=a=a，x x2 2，x xk k=b=b为为结结点点a a到到结结点点b b的的一一条条路路径径，而而路路径径上上边边的的数数目目k-1k-1（或或者者沿沿路路径径各各边边权权值值之之和和）称称为为该该路路径的长度，并称结点集合径的长度，并称结点集合xx1 1，x xk k 为连通集。为连通集。V1, v2, v5, v45 5、简单路径和回路、简单路径和回路如如果果一一条条路路径径上上的的结结点点除除起起点点x x1 1和和终终点点x xk k可可以以相相同同外外，其其它它结结点点均均不不相相同
6、同，则则称称此此路路径径为为一一条条简简单单路路径径。图图(a)(a)中中v v1 1vv2 2vv3 3是是一一条条简简单单路路径径，v v1 1vv3 3vv4 4vv1 1vv3 3不是简单路径。不是简单路径。x x1 1=x=xk k的的简简单单路路径径称称为为回回路路（也也称称为为环环）。例例如如图图(b)(b)中中，v v1 1vv2 2vv1 1为一条回路。为一条回路。例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，3
7、，1二、图的存储结构（教材二、图的存储结构（教材P79P79）图的邻接矩阵表示法图的邻接矩阵表示法 邻邻接接矩矩阵阵是是表表示示结结点点间间相相邻邻关关系系的的矩矩阵阵。若若G=G=（V V，E E）是是一一个个具具有有n n个个结结点点的的图图，则则G G的的邻邻接接矩矩阵阵是是如如下下定定义义的的二二维维数数组组a a，其其规规模模为为n*nn*n 1( 1(或权值或权值) ) 表示表示 顶点顶点i i和顶点和顶点j j有边有边(i(i和和j j的路程的路程) ) Aij =Aij = 0 0（或（或） 表示顶点表示顶点i i和顶点和顶点j j无边无边 二维数组的行、列号表示顶点编号上图中
8、的图上图中的图G G1 1和图和图G G2 2对应的相邻矩阵分别为：对应的相邻矩阵分别为： 无向带权图的邻接(代价)矩阵表示有向无权图的邻接矩阵表示邻接矩阵的特点：邻接矩阵的特点： 1)1)无向图的邻接矩阵是对称的，而有向图则不是。无向图的邻接矩阵是对称的，而有向图则不是。2)2)邻接矩阵方便度数的计算。用邻接矩阵表示图邻接矩阵方便度数的计算。用邻接矩阵表示图: : (1) (1)容易判定任意两个结点之间是否有边相联容易判定任意两个结点之间是否有边相联; ; (2) (2)容易求得各个结点的度数。容易求得各个结点的度数。 对于无权无向图的邻接矩阵，第对于无权无向图的邻接矩阵，第i i行元素值的
9、和就是行元素值的和就是ViVi的度数；的度数； 对于无权有向图的邻接矩阵，第对于无权有向图的邻接矩阵，第i i行元素值的和就是行元素值的和就是ViVi的出度，第的出度，第i i列元素值的和就是列元素值的和就是ViVi的入度；的入度； 对于有权无向图的邻接矩阵，第对于有权无向图的邻接矩阵，第i i行（或第行（或第i i列）中元列）中元素值素值00的元素个数就是的元素个数就是ViVi的度数；的度数； 对于有权有向图的邻接矩阵，第对于有权有向图的邻接矩阵，第i i行中元素值行中元素值00的元的元素个数就是素个数就是ViVi的出度；第的出度；第i i列元素值列元素值00的元素个数就是的元素个数就是Vi
10、Vi的入度。的入度。例1452375318642各顶点的度是多少？0618360240120078400530750读入数据构造邻接矩阵（P80）n n竞赛题中一般图的数据是以这种方式给出的：竞赛题中一般图的数据是以这种方式给出的：n n题中会指定顶点数的最大值，以便于定义一个全局二维数题中会指定顶点数的最大值，以便于定义一个全局二维数组作为邻接矩阵组作为邻接矩阵n n数据文件的第数据文件的第1 1行一般是图的顶点个数行一般是图的顶点个数N N以及边数以及边数MMn n接下来一般有接下来一般有MM行，每行有行，每行有2 2个或个或3 3个整数，描述了每条边个整数，描述了每条边的信息：的信息：
11、如果是如果是2 2个整数个整数i i，j j，则一般表示顶点，则一般表示顶点i i和顶点和顶点j j有一条边相连有一条边相连 如果是如果是3 3个整数个整数i i，j j，k k，则一般表示顶点，则一般表示顶点i i和顶点和顶点j j相连的权值为相连的权值为k kn n针对图数据的这种结构，我们会用如下的代码来构造邻接针对图数据的这种结构，我们会用如下的代码来构造邻接矩阵：矩阵：const int MAXN = 201; /const int MAXN = 201; /最大顶点数最大顶点数int aMAXNMAXN, n, m, i, j, k, x;int aMAXNMAXN, n, m,
12、i, j, k, x;scanf(%d%d, &n, &m);scanf(%d%d, &n, &m);for (i=1; i=m; i+) /for (i=1; i=m; i+) /读入读入mm条边条边scanf(%d%d, &j, &k);scanf(%d%d, &j, &k);ajk = 1; /ajk = 1; /若是有向图，则只赋值若是有向图，则只赋值ajkajkakj = 1; /akj = 1; /若是无向图，则一定要赋值若是无向图，则一定要赋值akjakj 如果是构造带权图，则上述如果是构造带权图，则上述for for 语句中的代码改为：语句中的代码改为： scanf(%d%d,
13、 &j, &k, &x);scanf(%d%d, &j, &k, &x);ajk = x; /ajk = x; /若是有向图，则只赋值若是有向图，则只赋值ajkajkakjl = x; /akjl = x; /若是无向图，则一定要赋值若是无向图，则一定要赋值akjakj邻接矩阵主对角线元素的处理n n在竞赛中很少有图数据是顶点带自环边的，因此邻接矩阵在竞赛中很少有图数据是顶点带自环边的，因此邻接矩阵的主对角线元素的主对角线元素aii(1=i=n)aii(1=i=n)一般都是一般都是0 0。n n在前面讲的邻接矩阵的构造方法中，如果顶点在前面讲的邻接矩阵的构造方法中，如果顶点i i，j j之间没
14、之间没有边，则有边，则aijaij也表示为也表示为0 0。在大多数图的算法中，不区。在大多数图的算法中，不区别这两种值为别这两种值为0 0的情况是可以的。的情况是可以的。n n而在某些图算法中，必须要区别主对角线元素和其它非主而在某些图算法中，必须要区别主对角线元素和其它非主对角线元素，这时就用另外的特殊值来表示无边相连的情对角线元素，这时就用另外的特殊值来表示无边相连的情况。特殊值一般取一个很大的正数（或负数），实现实现况。特殊值一般取一个很大的正数（或负数），实现实现代码如下：代码如下：const int BIG = 99999999; /const int BIG = 99999999;
15、 /表示无穷大表示无穷大for (i=1; i=n; i+) /for (i=1; i=n; i+) /初始化初始化 for (j=1; j=n; j+)for (j=1; j=n; j+) aij = BIG; aij = BIG;aii = 0;aii = 0; for (i=1; i=m; i+) /for (i=1; i=m; i+) /读入边数据读入边数据scanf(%d%d%d, &j, &k, &x);scanf(%d%d%d, &j, &k, &x);ajk = x;ajk = x;akj = x; /akj = x; /这句无向图才要这句无向图才要 邻接矩阵的优缺点见教材邻接
16、矩阵的优缺点见教材P80P80判断判断i i，j j有无边相连：有无边相连：O(1)O(1)找找i i的邻接点，计算入度、出度：的邻接点，计算入度、出度：O(n)O(n)空间复杂性高：空间复杂性高：O(n2)O(n2)边集数组表示法（教材P80）n n一个一维数组存储图一个一维数组存储图n n每个元素表示一条边：起点、终点、权值（如果有的话）每个元素表示一条边：起点、终点、权值（如果有的话）n n适用于：对边进行依次处理的算法，适合存储顶点多但边适用于：对边进行依次处理的算法，适合存储顶点多但边很少的稀疏图很少的稀疏图n n缺点：缺点： 判断判断i i，j j有无边相连：有无边相连：O(E)O
17、(E) 找找i i的邻接点，计算入度、出度：的邻接点，计算入度、出度：O(E)O(E)n n优点：结构简单优点：结构简单边集数组表示法的实现const int MAXEDGE = 2000;const int MAXEDGE = 2000;struct node struct node int s , t; /int s , t; /边的起点和终点边的起点和终点int w; /int w; /边的权值边的权值 node edgeMAXEDGE;node edgeMAXEDGE;int n, m, i, j, k, x;int n, m, i, j, k, x;scanf(%d%d, &n, &
18、m);scanf(%d%d, &n, &m);for (i=1; i=m; i+)for (i=1; i=m; i+)scanf(%d%d%d, &j, &k, &x);scanf(%d%d%d, &j, &k, &x);edgei.s = j;edgei.s = j;edgei.t = k;edgei.t = k;edgei.w = x;edgei.w = x; 邻接表表示法（P81）n n邻接表表示法是指对图中的每个顶点邻接表表示法是指对图中的每个顶点Vi(1=i=n)Vi(1=i=n)建立一个邻接关建立一个邻接关系的单链表，并把它们的表头指针用一维数组存储起来的一种表示方系的单链表，并把
19、它们的表头指针用一维数组存储起来的一种表示方法。法。n n为每个顶点为每个顶点ViVi建立的单链表，是表示以该顶点为建立的单链表，是表示以该顶点为起点起点的所有边的信息。的所有边的信息。以下图（教材图以下图（教材图5 52 2）为例，顶点）为例，顶点v1v1与与v2v2、v3v3、v5v5相邻，因此在相邻，因此在v1v1的单链表里就包含的单链表里就包含3 3条边的信息。条边的信息。v1v2v3v4v5524101183253853顶点v1的单链表有3个结点，表示有3条边与v1相接，有3个顶点（v2、v3、v5）是v1的邻接点不表示v2与v3相邻，v3与v5相邻邻接表表示法（P81）n n一维指
20、针数组存储了每个顶点的单链表的头指针。一般就用数组下标一维指针数组存储了每个顶点的单链表的头指针。一般就用数组下标表示了起点编号。例如表示了起点编号。例如v1v1单链表的头指针就存储在单链表的头指针就存储在adj1adj1中。中。n n下图的完整邻接表如下所示：下图的完整邻接表如下所示：v1v2v3v4v552410118325385315325618225431051113265114103412345邻接表的数据结构const int MAXV = 201; /const int MAXV = 201; /最大顶点数最大顶点数struct node struct node int v; /
21、 int v; /邻接点序号邻接点序号 int wt; /int wt; /权值，如果是带权图的话权值，如果是带权图的话 node *next; /node *next; /邻接单链表指针邻接单链表指针;node * adjMAXV; /node * adjMAXV; /每个顶点建一个单链表构造邻接表每个顶点建一个单链表构造邻接表int n, m; /nint n, m; /n表示读入的顶点个数，表示读入的顶点个数，mm表示读入的边条数表示读入的边条数创建邻接表void createlist() /void createlist() /创建邻接表创建邻接表 int i,j,k,x; int i
22、,j,k,x; node *p; node *p; scanf(%d%d, &n, &m); / scanf(%d%d, &n, &m); /读入顶点数和边数读入顶点数和边数 for (i=1; i=n; i+) /for (i=1; i=n; i+) /初始化每个顶点的边表为初始化每个顶点的边表为NULLNULL adji = NULL; adji = NULL; for (i=1; i=m; i+) for (i=1; iv = k; /jp-v = k; /j的邻接点是的邻接点是k k p-wt = x; / p-wt = x; /边的权值是边的权值是x x p-next = adjj;
23、 / p-next = adjj; /新节点插在顶点新节点插在顶点j j的边表的表头位置的边表的表头位置 adjj = p;adjj = p; / /以下是无向图需要构造的对称边以下是无向图需要构造的对称边 p = new node; p = new node; p-v = j; /k p-v = j; /k的邻接点是的邻接点是j j p-wt = x; p-wt = x; p-next = adjk; / p-next = adjk; /新节点插在顶点新节点插在顶点k k的边表的表头位置的边表的表头位置 adjk = p;adjk = p; 邻接表的优缺点（P82）n n便于查找后继顶点、以
24、该点为起点的边、出度。便于查找后继顶点、以该点为起点的边、出度。n n不便于查找前趋顶点、以该点为终点的边、入度。解决办不便于查找前趋顶点、以该点为终点的边、入度。解决办法：建立逆邻接表，即把以某顶点为终点的顶点放在一个法：建立逆邻接表，即把以某顶点为终点的顶点放在一个单链表中。单链表中。n n和邻接矩阵相比，构造邻接表的编程复杂性要高一些，但和邻接矩阵相比，构造邻接表的编程复杂性要高一些，但是查找后继顶点的效率要高是查找后继顶点的效率要高O(e/n) vs. O(n)O(e/n) vs. O(n)。如果边比。如果边比较稀疏，显然用邻接表存储图比较好。较稀疏，显然用邻接表存储图比较好。编程练习
25、n n求一个有向图中指定顶点的出度。求一个有向图中指定顶点的出度。n n输入数据：第输入数据：第1 1行：行：2 2个空格分开的整数个空格分开的整数n(2=n=200)n(2=n=200)和和m(10=m=20000)m(10=m=20000)，分别表示图的顶点数和边数。，分别表示图的顶点数和边数。n n第第2.m+12.m+1行：每行行：每行2 2个空格分开的整数个空格分开的整数i i，j j，i i表示一条边的起点，表示一条边的起点，j j表示终点。表示终点。n n第第mm2 2行：行：1 1个整数个整数k(2=k=n),k(2=k=n),表示指定的顶点。表示指定的顶点。n n输出数据：第
26、输出数据：第1 1行：行：1 1个整数个整数odod，表示顶点，表示顶点k k的出度。的出度。n n要求：分别用邻接矩阵和邻接表存储图。要求：分别用邻接矩阵和邻接表存储图。三、三、图的遍历图的遍历给出一个图给出一个图G G和其中任意一个结点和其中任意一个结点V V，从，从V V出发访问出发访问G G中所有结中所有结点，每一个结点被访问一次（不是只经过一次），这就叫图点，每一个结点被访问一次（不是只经过一次），这就叫图的遍历。的遍历。 通常有两种遍历方法：通常有两种遍历方法： 深度优先搜索深度优先搜索dfsdfs 广度优先搜索广度优先搜索bfsbfs 1 1、深度优先搜索、深度优先搜索DFSDF
27、S方法：从图的某一顶点V1出发，访问此顶点；然后依次从V1的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V1相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。为了避免重复访问某个顶点，设一个标志数组visit，顶点i未访问时，visiti的值为false，访问后就改为true。V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V5 V3 V6 V7可以从任一顶点出发进行DFSV1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1 V2 V4 V8 V5 V6 V
28、3 V7深度遍历：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V3 V6 V7 V5在程序中实现深度优先搜索n n算法算法: : 从图的某一顶点从图的某一顶点V1V1出发，访问此顶点；出发，访问此顶点；然后依次从然后依次从V1V1的未被访问的邻接点出发，深度的未被访问的邻接点出发，深度优先遍历图，直至图中所有和优先遍历图，直至图中所有和V1V1相通的顶点都相通的顶点都被访问到。被访问到。n n如何判别如何判别V V的邻接点是否被访问？的邻接点是否被访问？n n解决的办法是解决的办法是: :为每个顶点设立一个为每个顶点设立一个
29、 “ “访问标访问标志志 visiti”visiti”n n如果图不连通，则一次如果图不连通，则一次DFSDFS只能访问所有与只能访问所有与V1V1连连通的顶点。要对整个图进行遍历，则需要再任通的顶点。要对整个图进行遍历，则需要再任找一个尚未访问的顶点，再次找一个尚未访问的顶点，再次DFSDFS，直到所有顶，直到所有顶点均被访问为止。点均被访问为止。abchdekfg812345670FFFFFFFFF0 1 2 3 4 5 6 7 8T T T T T T T T Tach d kfe bgachkfedbg访问标志访问标志: :访问次序访问次序: :例如例如:achdkfe参考代码/从顶点
30、从顶点i i出发进行深度优先搜索出发进行深度优先搜索, ,邻接表实现邻接表实现/适用于有向图和无向图适用于有向图和无向图void dfs(int i)void dfs(int i) node *p; node *p; cout i; / cout v = false) / if (visitp-v = false) /如果邻接点未访问如果邻接点未访问 dfs(p-v); /dfs(p-v); /则对其递归则对其递归DFSDFS p = p-next; / p = p-next; /取下一个邻接点取下一个邻接点 参考代码void dfstravel() /void dfstravel() /对图
31、进行深度优先遍历对图进行深度优先遍历 int i; int i; memset(visit, 0, sizeof(visit); / memset(visit, 0, sizeof(visit); /清访问标志清访问标志 for (i=1; i=n; i+)for (i=1; i=n; i+) if (!visiti) if (!visiti) dfs(i); dfs(i); DFS的应用1 1、犯罪团伙、犯罪团伙 警察抓到了警察抓到了n n个罪犯，警察根据经验知道他们属于不同的个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知犯罪团伙，却不能判断有多
32、少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从号从1 1至至n n。输入：输入：第一行：第一行：n n（=5000,=5000,罪犯数量），罪犯数量），m m（5000050000，关系数量），关系数量）以下以下m m行：每行两个数：行：每行两个数：i i 和和j j，中间一个空格隔开，
33、表示罪犯，中间一个空格隔开，表示罪犯i i和罪犯和罪犯j j相互认识。相互认识。输出：输出：一个整数，犯罪团伙的数量。一个整数，犯罪团伙的数量。样例输入：11 8 1 24 35 41 35 67 105 108 9输出：3说明：共三个犯罪团伙。分析n n把人处理成顶点，把认识关系处理成边，犯罪团伙构成一个图（有向把人处理成顶点，把认识关系处理成边，犯罪团伙构成一个图（有向还是无向？）则根据输入数据可以构造一个邻接表（可以用邻接矩阵还是无向？）则根据输入数据可以构造一个邻接表（可以用邻接矩阵吗？如果不能请说明原因）。吗？如果不能请说明原因）。n n从从1 1到到n n枚举顶点枚举顶点ViVi，
34、从，从ViVi进行进行DFSDFS，则能找到一个团伙。然后再另选，则能找到一个团伙。然后再另选一个未访问的顶点，再次一个未访问的顶点，再次DFSDFS，直到所有顶点均被访问。最后，调用，直到所有顶点均被访问。最后，调用DFSDFS的次数就是团伙的个数。的次数就是团伙的个数。const maxn=1000;var a:array1.maxn,1.maxnof longint; visited:array1.maxnof 0.1; t:array1.maxnof char; n,m,i,s:longint; procedure init; var i,x,y:longint; begin assi
35、gn(input,group5.in);reset(input); readln(n); readln(m); for i:=1 to m do begin readln(x,y); ax,y:=1; ay,x:=1; end; close(input); end;procedure dfs(i:longint); var j:longint; begin visitedi:=1; for j:=1 to n do if (ai,j=1) and (visitedj=0) then dfs(j); end;Begin init; s:=0; for i:=1 to n do visitedi:
36、=0; for i:=1 to n do if visitedi=0 then begin dfs(i); inc(s); end; writeln(s); end.12354672 2、哈密顿路、哈密顿路 邮递员在送信时，为了节省路途，自己规定：每次总是从n个村子中选择其中一个合适的村子出发，途经每个村子仅且经过一次，送完所有的信。已知各个村子的道路连通情况。请你帮邮递员选择一条合适的路线。输入：第一行：整数n(2=n=200)：村子的个数。接下来是一个n*n的0、1矩阵，表示n个村子的连同情况，如：ai,j=1 ，表示第i和第j个村子之间有路可走，如果ai,j=0，表示他们之间无路可走。输
37、出：一条可行的路线输入：输入：70 1 0 1 1 0 01 0 1 0 1 0 00 1 0 0 0 0 11 0 0 0 0 0 01 1 0 0 0 1 00 0 0 0 1 0 10 0 1 0 0 1 0输出：输出：2 3 7 6 5 1 42 3 7 6 5 1 4分析分析n n题目的限制条件：题目的限制条件：“ “途经每个村子仅且经过一次途经每个村子仅且经过一次” ”，表明，表明在深搜的过程中，在深搜的过程中，ViVi的邻接点中必须要有至少一个顶点是的邻接点中必须要有至少一个顶点是没有被访问过的。这样才能沿着该点继续没有被访问过的。这样才能沿着该点继续DFSDFS下去。下去。n
38、n如果恰能遍历全部结点，则找到一条路径，输出这条路径如果恰能遍历全部结点，则找到一条路径，输出这条路径即可。怎样在即可。怎样在DFSDFS的过程中保存路径？的过程中保存路径？n n如果在如果在DFSDFS的某一层出现了所有邻接点都被访问过了，则的某一层出现了所有邻接点都被访问过了，则说明在上一层（以及更上层）的路由选择不正确，这时就说明在上一层（以及更上层）的路由选择不正确，这时就要回溯到上层，换一个未被访问的结点要回溯到上层，换一个未被访问的结点, ,再次进行再次进行DFSDFS，看能否走通。看能否走通。n n在换结点的时候，一定要清除前一个结点被访问过的标志在换结点的时候，一定要清除前一个
39、结点被访问过的标志信息，这就是所谓的信息，这就是所谓的“ “清理现场清理现场” ”的工作。如果不做这个的工作。如果不做这个操作，则求解几乎没有可能得到正确结果。操作，则求解几乎没有可能得到正确结果。const maxn=100;算法一var a:array1.maxn,1.maxnof integer; visited:array1.maxnof 0.1; b:array1.maxn of 1.maxn; n,m,i:integer; found:integer; procedure init; var i,j:integer; begin assign(input,a.in);reset(i
40、nput); readln(n); for i:=1 to n do for j:=1 to n do read(ai,j); close(input); end; procedure print; var i:integer; begin found:=1; for i:=1 to n-1 do write(bi, ); writeln(bn); end; procedure dfs(i:integer); var j,k:integer; begin /m是当前访问的结点个数 if m = n then begin print; exit; end; for j:=1 to n do if
41、 (aj,i=1) and (visitedj=0) then begin visitedj:=1; m:=m+1; bm:=j; dfs(j); visitedj:=0; m:=m-1; end; end; Begin init; found:=0; for i:= 1 to n do begin fillchar(visited,sizeof(visited),0); m:=1; b1:=i; visitedi:=1; dfs(i); end; if found=0 then writeln(no road); end.算法二算法二proceduredfs(i,k:integer);结点结
42、点i是路上的第是路上的第k个结点个结点varj:integer;beginifk=nthenprint;forj:=1tondoif(aj,i=1)and(visitedj=0)thenbeginvisitedj:=1;bk+1:=j;dfs(j,k+1);visitedj:=0;end;end;Begininit;found:=0;fori:=1tondobeginfillchar(visited,sizeof(visited),0);m:=1;b1:=i;visitedi:=1;dfs(i,1);end;iffound=0thenwriteln(noroad);end.3 3 、安排座位、
43、安排座位 n n个个客客人人围围着着一一个个桌桌子子吃吃饭饭，每每一一个个人人都都至至少少认认识识其其他他的的2 2个个客客人人。请请设设计计程程序序求求得得n n个个人人的的一一种种坐坐法法，使使得得每每个个人人都都认认识他左右的客人。识他左右的客人。输入输入: :第一行第一行:n:n（吃饭人的个数）。（吃饭人的个数）。以下以下n n行：第行：第i i行的第一个数行的第一个数k k表示第表示第i i个人认识的人数，后面个人认识的人数，后面k k个数依次为个数依次为i i认识的人的编号。认识的人的编号。输出：所有座法，要求第一个人为输出：所有座法，要求第一个人为1 1号作为起点，按顺时针输号作
44、为起点，按顺时针输出其它人的编号。出其它人的编号。样例输入：62 3 63 4 5 63 1 4 63 2 3 53 2 4 64 1 2 3 5样例输出：1 3 4 2 5 61 3 4 5 2 61 6 2 5 4 31 6 5 2 4 3分析分析: : 如如果果A A认认识识B,BB,B又又认认识识C,C,则则B B认认识识他他左左右右的的两两个个人人. .继继续续这这个个过过程程, ,如如果果C C又又认认识识D,D,则则C C认认识识他他左左右右的的两两个个人人;这这其其实实就就是一个是一个DFSDFS过程过程. .如如果果最最后后一一个个人人能能认认识识第第一一个个人人, ,则则最
45、最后后一一个个人人也也认认识识他他左左右右的两个人的两个人. .这样就找到一组满足要求的解了这样就找到一组满足要求的解了. .本题是求一个本题是求一个N N个顶点的简单回路问题个顶点的简单回路问题. .proceduredfs(i:integer);varj,k:integer;beginif(n=m)and(ab1,bm=1)thenprint;forj:=1tondoif(ai,j=1)and(visitedj=0)thenbeginvisitedj:=1;m:=m+1;bm:=j;dfs(j);visitedj:=0;m:=m-1;end;end;Begininit;fillchar(v
46、isited,sizeof(visited),0);found:=0;m:=1;b1:=1;visited1:=1;dfs(1);iffound=0thenwriteln(noroad);end.4、素数链设计程序将1,2,20排成一排，使任意两个相邻的数的和为素数。第1个和最后一个的和也为素数.输出:120个数的排列方式.const maxn=100;var visited:array1.maxnof 0.1; b:array1.maxn of 1.maxn; n,m,i:integer; found:integer; function check(i:integer):boolean; v
47、ar j:integer; begin for j:=2 to i-1 do if i mod j=0 then begin check:=false; exit; end; check:=true; end; procedure print; var i:integer; begin found:=1; for i:=1 to n-1 do write(bi, ); writeln(bn); halt; end; procedure dfs(i:integer); var j,k:integer; begin if (m=n)and(check(b1+bm) then print; for
48、j:=1 to n do if (visitedj=0) and (check(i+j) then begin visitedj:=1; m:=m+1; bm:=j; dfs(j); visitedj:=0; m:=m-1; end; end;Begin fillchar(visited,sizeof(visited),0); n:=20; found:=0; m:=1; b1:=1; visited1:=1; dfs(1); if found=0 then writeln(no road); end.2 2、广度（宽度）优先搜索、广度（宽度）优先搜索BFSBFS 广度优先搜索广度优先搜索按层
49、次按层次遍历的过程，其搜索过程如下：遍历的过程，其搜索过程如下：方法：从图的某一顶点V1出发，访问此顶点后，依次访问V1的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8广度遍历：V1 V2 V3 V4 V5 V6
50、V7 V8V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V6 V7 V8 V5在程序中实现BFSn n从图的某一顶点从图的某一顶点V1V1出发，访问此顶点后，依次访问出发，访问此顶点后，依次访问V1V1的各的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；被访问到；n n要解决的问题要解决的问题: :n n怎样依次访问怎样依次访问ViVi的邻接点的邻接点? ?n n怎样依次从它的邻接点出发怎样依次从它的邻接点出
51、发, ,广度优选遍历图广度优选遍历图? ?n n我们用到的主要的数据结构就是队列我们用到的主要的数据结构就是队列. .例142350 1 2 3 4 51fr遍历序列：10 1 2 3 4 54fr遍历序列：1 40 1 2 3 4 54 3fr遍历序列：1 4 30 1 2 3 4 5fr队列空结点在入队时进行访问，f指针指向当前扩展结点110 1 2 3 4 54 3 2fr遍历序列：1 4 3 20 1 2 3 4 5 3 2fr遍历序列：1 4 3 20 1 2 3 4 5 3 2 5fr遍历序列：1 4 3 2 511 41 40 1 2 3 4 5 2 5fr遍历序列：1 4 3
52、2 50 1 2 3 4 5 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 fr遍历序列：1 4 3 2 51 4 31 4 3 21 4 3 2 514356782输入：输入：81014151626273534375758编程实现：输入下图，按深度优先遍历和广度优先遍历输编程实现：输入下图，按深度优先遍历和广度优先遍历输出图的结点。出图的结点。图的图的dfsconstmax=100;vara:array1.max,1.maxofinteger;f:array1.maxof0.1;/标志数组标志数组n,m,i:integer;procedureinit;vari,j,x,y:int
53、eger;beginreadln(n,m);fillchar(f,sizeof(f),0);fori:=1tomdobeginreadln(x,y);ax,y:=1;ay,x:=1;end;end;proceduredfs(i:integer);深搜深搜varj:integer;beginwrite(i,);fi:=1;forj:=1tondoif(fj=0)and(ai,j=1)thendfs(j);end;procedurebfs(i:integer);广搜广搜varj,k:integer;beginfillchar(q,sizeof(q),0);f:=0;队首队首r:=1;尾尾q1:=i
54、;i进队列进队列write(i,);fi:=1;标志标志whilefrdo队列不空队列不空begininc(f);k:=qf;出队出队forj:=1tondoif(ak,j=1)and(fj=0)thenbeginwrite(j,);fj:=1;inc(r);进队进队qr:=j;end;end;end;BEGINInit; /读入图数据,初始化标志数组For i:=1 to n do if fi = 0 then dfs(i);Writeln;fillchar(f,sizeof(f),0); for i:=1 to n do if fi=0 then bfs(i);END. 问题描述问题描述
55、学校放暑假时，信息学辅导教师有学校放暑假时，信息学辅导教师有n n本书要分给参加培训的本书要分给参加培训的n n个学生。个学生。如：如：A A，B B，C C，D D，E E共共5 5本书要分给参加培训的张、刘、王、李、孙本书要分给参加培训的张、刘、王、李、孙5 5位学生，位学生，每人只能选每人只能选1 1本。教师事先让每个人将自己喜爱的书填写在如下的表中，然本。教师事先让每个人将自己喜爱的书填写在如下的表中，然后根据他们填写的表来分配书本，希望设计一个程序帮助教师求出可能的后根据他们填写的表来分配书本，希望设计一个程序帮助教师求出可能的分配方案，使每个学生都满意。分配方案，使每个学生都满意。
56、A AB BC CD DE E张张Y YY Y王王Y YY Y刘刘Y YY Y孙孙Y Y李李Y YY Y5 5、借书问题、借书问题输入格式：第一行一个数n（学生的个数，书的数量） 以下共n行，每行n个0或1（由空格隔开），第I行数据表示第i个同学对所有书的喜爱情况。0表示不喜欢该书，1表示喜欢该书。输出格式：依次输出每个学生分到的书号。样例：输入：book.in50 0 1 1 01 1 0 0 00 1 1 0 00 0 0 1 00 1 0 0 1输出：book.out3 1 2 4 5分析: a:array1.maxn,1.maxnof 0.1; b:array1.maxnof inte
57、ger; 方案:bi是第i个人借第bi本书 book:array1.maxnof boolean; booki:能否可以借第i本书, 初始:true,一旦有人借了:就改为:false算法设计:procedure try(i:integer);搜索第i个人可以借的书bi var j:integer; begin if i=n+1 then 输出结果 else for j:=1 to n do if 第i个人可以借第j 本书 then begin 记录下bi; 标记第j本数已被借; try(i+1); 删除书的被借标志; end; end;constmaxn=10;vara:array1.maxn
58、,1.maxnof0.1;b:array1.maxnofinteger;book:array1.maxnofboolean;n:integer;procedureinit;vari,j:integer;beginassign(input,book.in);reset(input);fillchar(b,sizeof(b),0);fillchar(book,sizeof(book),true);readln(n);fori:=1tondoforj:=1tondoread(ai,j);close(input);end;procedureprint;vari:integer;beginfori:=1
59、ton-1dowrite(bi,);writeln(BN);end;proceduretry(i:integer);varj:integer;beginifi=n+1thenprint;forj:=1tondoifbookjand(ai,j=1)thenbeginbi:=j;bookj:=false;try(i+1);bookj:=true;end;end;Begininit;try(1);end.火力中心布局(自习) 现有一张由现有一张由n n个堡垒组成的交通图，任意两个堡垒之间只有一条个堡垒组成的交通图，任意两个堡垒之间只有一条通行路线。为了确保路线畅通，必须在某些堡垒上建立火力中心，通行
60、路线。为了确保路线畅通，必须在某些堡垒上建立火力中心，每个火力中心都能够对其相连的所有交通线进行全天候的监控，每个火力中心都能够对其相连的所有交通线进行全天候的监控，防止敌人侵略。现在的问题是如何设置火力中心的布局，才能用防止敌人侵略。现在的问题是如何设置火力中心的布局，才能用最少的火力中心控制所有交通路线。最少的火力中心控制所有交通路线。输入：输入： 堡垒数堡垒数n(1n10000)n(1n10000)； 以下每行为以下每行为i i，j j，表示堡垒，表示堡垒i i与堡垒与堡垒j j连接。以连接。以0 00 0标志结束；标志结束； 输出：输出： w w行，每行为火力中心所在的堡垒号。行，每行
61、为火力中心所在的堡垒号。 火力中心数火力中心数w w数学模型和解题的基本思路数学模型和解题的基本思路数学模型和解题的基本思路数学模型和解题的基本思路 如果将堡垒设为顶点、堡垒间的交通线设为边的话，则交如果将堡垒设为顶点、堡垒间的交通线设为边的话，则交通图为一张无向图。由于任意两个堡垒之间只有一条通行路通图为一张无向图。由于任意两个堡垒之间只有一条通行路线，且没有明确出发点，因此这张无向图构成了一棵无根树。线，且没有明确出发点，因此这张无向图构成了一棵无根树。所谓支配集是图的一个满足下述条件的顶点子集：即图所谓支配集是图的一个满足下述条件的顶点子集：即图的任意顶点或属于该集合，或至少与该集合的一
62、个顶点相邻。的任意顶点或属于该集合，或至少与该集合的一个顶点相邻。显然，火力点就是支配集中的顶点。本题的数学模型就是在显然，火力点就是支配集中的顶点。本题的数学模型就是在交通图对应的无根树中，计算含顶点数最少的最小支配集。交通图对应的无根树中，计算含顶点数最少的最小支配集。 如果是一棵明确了顶点间父子关系的有根树的话，我们很如果是一棵明确了顶点间父子关系的有根树的话，我们很容易找到计算最小支配集的方法：容易找到计算最小支配集的方法： 按照自底而上、由右而左的顺序搜索每一条边。如果一条按照自底而上、由右而左的顺序搜索每一条边。如果一条边的两个端点为访问，则父顶点进入支配集，由其支配祖父边的两个端
63、点为访问，则父顶点进入支配集，由其支配祖父顶点和所有儿子。依次类推，直至根被访问为止。顶点和所有儿子。依次类推，直至根被访问为止。 第一步：建立边表。第一步：建立边表。由于交通图为一张无向图，因此我们将每条边拆分成方向互为由于交通图为一张无向图，因此我们将每条边拆分成方向互为相反的两条边，即相反的两条边，即(xi(xi，yi)yi)作为第作为第i i条边存储，条边存储，(yi(yi，xi)xi)作为作为第第n+in+i条边存储条边存储: :for i1 to n-1 dofor i1 to n-1 do建立边表。由于是无向图，因此将第建立边表。由于是无向图，因此将第i i条条边（边（k,jk,
64、j）分别存储于（）分别存储于（xi,yixi,yi）和（）和（xn+i-1,yn+i-xn+i-1,yn+i-11） begin begin readln(f,xi,yi); readln(f,xi,yi);读第读第i i条边的两个端点条边的两个端点 xi+n-1yi; yi+n-1xi xi+n-1yi; yi+n-1xi反向存储第反向存储第i i条边的两个条边的两个端点端点 end;end;forfor 第二步：通过深度优先搜索将无根树转化为明确顶点间父子关系的有根树。第二步：通过深度优先搜索将无根树转化为明确顶点间父子关系的有根树。第二步：通过深度优先搜索将无根树转化为明确顶点间父子关系
65、的有根树。第二步：通过深度优先搜索将无根树转化为明确顶点间父子关系的有根树。 首首先先从从顶顶点点1 1出出发发，按按照照纵纵深深搜搜索索的的策策略略构构造造一一棵棵深深度度优优先先搜搜索索树树，并并记记下下每每个个顶顶点点的的父父顶顶点点。由由于于树树边边的的父父子子关关系系未未明明确确, ,因因此此逐逐边边搜搜索索。方方向向是是由由左左而而右右、由由上上而而下下，对对于于第第i i个个被被访访问问的的顶顶点点来来说说，所所有有访访问问顺顺序序比比i i大大的的顶顶点，不是该顶点的后辈顶点就是位于该顶点的右方树枝上。例如点，不是该顶点的后辈顶点就是位于该顶点的右方树枝上。例如设设cdcd表为
66、按照深度优先搜索顺序存储的被访问顶点，即第表为按照深度优先搜索顺序存储的被访问顶点，即第i i个被个被访问的顶点为访问的顶点为cdicdi。在深度优先搜索树中，其父亲为。在深度优先搜索树中，其父亲为ptcdiptcdi。我们通过递归过程。我们通过递归过程encodeencode计算深度优先搜索的访问计算深度优先搜索的访问顺序表顺序表cdcd和父指针表和父指针表ptpt：procedure encode(nw,last:integer);procedure encode(nw,last:integer);输入当前顶点输入当前顶点nwnw和父顶和父顶点点lastlast，递归计算，递归计算cdcd
67、和和ptpt表表 varvar i:integer; i:integer;beginbegin inc(nm); cdnmnw;nw inc(nm); cdnmnw;nw进入深度优先搜索的访问顺序表进入深度优先搜索的访问顺序表 cvnwtrue;ptnw last; cvnwtrue;ptnw last; 设设nwnw已访问，其父顶点为已访问，其父顶点为lastlast for i1 to 2*n-2 do ) for i1 to 2*n-2 do )递归访问与递归访问与nwnw相连的未访问边，这相连的未访问边，这些边的另一端点为些边的另一端点为nwnw的儿子的儿子 if(xi=nw)and
68、not cvyithen encode(yi,nw if(xi=nw)and not cvyithen encode(yi,nw end;encode end;encode第三步：逆推深度优先搜索的访问顺序，计算最小支配集第三步：逆推深度优先搜索的访问顺序，计算最小支配集按按照照深深度度优优先先搜搜索索的的逆逆向向顺顺序序，即即由由右右而而左左、由由下下而而上上的的顺顺序序访访问问每每个个顶顶点点，依依次次将将每每条条未未访访问问边边（父父子子顶顶点点未未访访问问）的的父父顶顶点点设设为为火火力力点点, ,由由其其控控制制祖祖父父顶顶点点和和所所有有儿儿子子。例例如如图图，可可在第在第1 1、
69、3 3、5 5个被访问的顶点处布局火力点。个被访问的顶点处布局火力点。主程序主程序建立边表建立边表x x和和y y；fillchar(cv,sizeof(cv),0);nm0;fillchar(cv,sizeof(cv),0);nm0;访问表访问表cvcv和访问顺序表和访问顺序表cdcd的长度初始化的长度初始化 encode(1,1);encode(1,1);从顶点从顶点1 1出发进行深度优先搜索，计算访问顺序表出发进行深度优先搜索，计算访问顺序表cdcd和父指针和父指针表表pt pt fillchar(cv,sizeof(cv),0); w0; fillchar(cv,sizeof(cv),
70、0); w0; 访问表访问表cvcv和火力点数初始化和火力点数初始化 for in downto 2 dofor in downto 2 do按照由右而左、由下而上的顺序访问每个顶点，依次按照由右而左、由下而上的顺序访问每个顶点，依次将每条未访问边（父子顶点未访问）的父顶点设为火力点将每条未访问边（父子顶点未访问）的父顶点设为火力点 if not cvcdi and not cvptcdi if not cvcdi and not cvptcdi若深度优先搜索中第若深度优先搜索中第i i个被访问个被访问的顶点和其父亲当前未访问，则其父亲设为火力点的顶点和其父亲当前未访问，则其父亲设为火力点 t
71、hen begin then begin inc(w);write(ptcdi, ); inc(w);write(ptcdi, );在父端点处增设一个火力点，输出在父端点处增设一个火力点，输出该火力点序号该火力点序号 cvptcditrue cvptcditrue置火力点已访问标志置火力点已访问标志 end;then end;then writeln(w); writeln(w);输出火力点数输出火力点数 任务任务任务任务A:A:A:A: 题目给出一个完整路线（图），请编程找出所有必经之点。请注题目给出一个完整路线（图），请编程找出所有必经之点。请注意，输出必经之点时，应不包括起点和终点。意，
72、输出必经之点时，应不包括起点和终点。任务任务任务任务B:B:B:B: 假定赛跑必须在相邻的假定赛跑必须在相邻的2 2天来举行。因此，要把原来给定的完整路天来举行。因此，要把原来给定的完整路线（图）分成两个子路线（图）。第线（图）分成两个子路线（图）。第1 1天从点天从点0 0出发，结束于出发，结束于“分裂点分裂点”。第第2 2天从天从“分裂点分裂点”出发，结束于点出发，结束于点N N。 题目给出一个完整路线（图）题目给出一个完整路线（图）C C，请编程输出所有可能的，请编程输出所有可能的“分裂点分裂点”（任务（任务B B）。）。“分裂点分裂点”S S一定不是起点或终点。一定不是起点或终点。C
73、C可被可被S S分成两个完整的分成两个完整的子路线：这两个子路线没有公共的箭头线，并且子路线：这两个子路线没有公共的箭头线，并且S S是这两个子路线的唯是这两个子路线的唯一公共点。在上的例子中，仅点一公共点。在上的例子中，仅点3 3是是“分裂点分裂点”。输入数据输入数据输入数据输入数据 输入文件输入文件INPUTINPUTTXTTXT描述一个完整路线（最多描述一个完整路线（最多5050个点，最多个点，最多100100个箭头）个箭头），文件共（，文件共（n n1 1）行。前面）行。前面n n行（行（0 0（n-1n-1）描述箭头的终点。第）描述箭头的终点。第i i行行中的每一个数字表示从点中的每
74、一个数字表示从点i i（0in0in1 1）出发的每一个箭头的终点。）出发的每一个箭头的终点。以以2 2作为该行的结束。文件的最后一行（第作为该行的结束。文件的最后一行（第n n行）中有一个数字行）中有一个数字1 1，表示文件的结束。表示文件的结束。输出数据输出数据输出数据输出数据 你的程序向输出文件你的程序向输出文件OUTPUTOUTPUTTXTTXT写入两行数据，第写入两行数据，第1 1行表示必经点行表示必经点（子任务（子任务A A）首先是必经点的总数，其后是必经点的标号，标号的首先是必经点的总数，其后是必经点的标号，标号的顺序无关紧要。第顺序无关紧要。第2 2行表示行表示“分裂点分裂点”
75、：首先是分裂点的总数，其后是：首先是分裂点的总数，其后是分裂点的标号，标号出现的先后顺序无关紧要（子任务分裂点的标号，标号出现的先后顺序无关紧要（子任务B B）。）。必经点和分裂点的特征必经点和分裂点的特征 必经点必经点必经点必经点: : : :是指运动员从起点是指运动员从起点0 0出发，沿箭头方向跑，无论走哪条路线，都经由该点出发，沿箭头方向跑，无论走哪条路线，都经由该点到达终点到达终点N N。所有这些点组成必经点的集合。反之，在完整路线中去除必经点。所有这些点组成必经点的集合。反之，在完整路线中去除必经点集合中的任一个点，无论运动员选择哪条路线跑，都不可能从起点集合中的任一个点，无论运动员
76、选择哪条路线跑，都不可能从起点0 0跑至终点跑至终点N N。分裂点分裂点分裂点分裂点: : : :运动员从起点运动员从起点0 0出发沿箭头方向跑，无论走哪条路线，都不约而同地走到出发沿箭头方向跑，无论走哪条路线，都不约而同地走到某一个点上。而此时，所有从点某一个点上。而此时，所有从点0 0至该点路线上的点都不为余下的任一点的箭至该点路线上的点都不为余下的任一点的箭头终点。在这种情况下，从该点出发可到达终点头终点。在这种情况下，从该点出发可到达终点N N。这个点即所谓分裂点。具。这个点即所谓分裂点。具体地讲，分裂点具有如下特征：体地讲，分裂点具有如下特征： 某点是必经点；某点是必经点； 在完整路
77、线中去除这个必经点后，由起点出发的运动员无论如何也不会在完整路线中去除这个必经点后，由起点出发的运动员无论如何也不会跑到由这个必经点出发的任一箭头的终点；跑到由这个必经点出发的任一箭头的终点； 完整路线中去除这个必经点后的所有点，分成两个互为独立的集合完整路线中去除这个必经点后的所有点，分成两个互为独立的集合 可从出发点可从出发点0 0到达。这些点组成子路径到达。这些点组成子路径1 1； 无法从出发点无法从出发点0 0到达。这些点组成子路径到达。这些点组成子路径2 2； 两个集合中的点之间，无任何箭头相连；两个集合中的点之间，无任何箭头相连；满足上述满足上述3 3个条件的点为分裂点，所有这些点
78、组成分裂点的集合。个条件的点为分裂点，所有这些点组成分裂点的集合。( ( ( (一一一一) ) ) )运算顺序运算顺序运算顺序运算顺序 分裂点是在必经点的基础上产生；分裂点是在必经点的基础上产生； 无论是判别必经点还是分裂点，都必须预先无论是判别必经点还是分裂点，都必须预先在完整路线中删除判别点；在完整路线中删除判别点； 顺序设点顺序设点1 1、点、点2 2，点，点N N1 1为当前判别为当前判别点。对于每一个判别点，先设删除标志、其余点未点。对于每一个判别点，先设删除标志、其余点未达标志（即未能从出发点到达）。然后判别是否可达标志（即未能从出发点到达）。然后判别是否可从出发点从出发点0 0到
79、达终点到达终点N N。若能够，则该点为非必经点；。若能够，则该点为非必经点；否则该点为必经点。若判别出该点是必经点，则再否则该点为必经点。若判别出该点是必经点，则再判别该点是否同时满足分裂点的特征判别该点是否同时满足分裂点的特征2 2和特征和特征3 3。若。若满足条件，则该点又是分裂点。满足条件，则该点又是分裂点。 ( ( ( (二二二二) ) ) )采用广度优先搜索的方法采用广度优先搜索的方法采用广度优先搜索的方法采用广度优先搜索的方法 从点从点0 0开始，按逐层搜索的方法对删除当前判开始，按逐层搜索的方法对删除当前判别点后的路线重复进行访问，直至找不到可访问的点别点后的路线重复进行访问，直
80、至找不到可访问的点为止。广度搜索的结果，将路线上的所有点为止。广度搜索的结果，将路线上的所有点( (除当前除当前判别点外判别点外) )分为两个集合：分为两个集合： 广度优先搜索中访问到的点，即从出发点广度优先搜索中访问到的点，即从出发点0 0可可达的点集合，设这些点到达标志；达的点集合，设这些点到达标志； 广度优先搜索中未访问过的点，即不可从出发广度优先搜索中未访问过的点，即不可从出发点点0 0到达的点集合。这些点设未到达标志；到达的点集合。这些点设未到达标志； 若终点若终点N N在第二个集合中，则当前判别点是必在第二个集合中，则当前判别点是必经点，然后再判别两个集合是否互为独立。若与必经经点
81、，然后再判别两个集合是否互为独立。若与必经点相连的所有点都在第二个集合中，且两个集合中的点相连的所有点都在第二个集合中，且两个集合中的点之间无任何箭头相连，则这个必经点亦是分裂点。点之间无任何箭头相连，则这个必经点亦是分裂点。For iFor i1 to n-1 do1 to n-1 do顺序设点顺序设点1 1、点、点2 2，点，点N N1 1为当前判别点为当前判别点 Begin Begin 删除顶点删除顶点i i，构建新图的相邻矩阵，构建新图的相邻矩阵a a； BFS(0)BFS(0)； 宽度优先搜索出发点宽度优先搜索出发点0 0可达的点集可达的点集 if fn=false if fn=fa
82、lse 若出发点若出发点0 0不可达终点不可达终点n n，则顶点，则顶点i i为必经点为必经点 Then begin Then begin 输出顶点输出顶点i i为必经点；为必经点； FundFundtruetrue； 初始时假设顶点初始时假设顶点i i为分裂点为分裂点 For k For k0 to n-1 do0 to n-1 do搜索出发点搜索出发点0 0可达的点集合可达的点集合 For p For p0 to n do0 to n do搜索出发点搜索出发点0 0不可达的点集合不可达的点集合 if(fk=true)and(fp=false)and(ak,p0)or(ap,k0)Then
83、if(fk=true)and(fp=false)and(ak,p0)or(ap,k0)Then begin Fundbegin Fundfalse;break;end;false;break;end;若两个点集间有边相连，则退出若两个点集间有边相连，则退出forfor循环循环 if Fund then if Fund then输出顶点输出顶点i i为分裂点；为分裂点； EndEnd；thenthen End End；forfor宽度优先搜索的应用宽度优先搜索的应用1、计算连通子图2、计算无权图的单源最短路计算无权图的单源最短路深度优先搜索访问顶点的次序次序取决于图的存存储结构储结构，而广度优先
84、搜索访问顶点的次序是按“路径长度”渐增的次序。因此，求路径长度最短的路径可以基于广度求路径长度最短的路径可以基于广度优先搜索遍历进行优先搜索遍历进行，但需要修改队列的结修改队列的结点结构点结构例如:求右图中顶点 3 至顶点 5 的一条最短路径。321475689Q.front 312475Q.rear链队列的状态如下所示:1) 将队列的结点改为结构体，其中包含顶点编号将队列的结点改为结构体，其中包含顶点编号v、路径长度、路径长度len和父结点指针和父结点指针fa;2) 修改入队列的操作。修改入队列的操作。插入新的队尾结点时，令其fa域的指针记录刚刚出队列的结点，即当前的队头指针所指结点;len域则是将队头结点的len域13) 找到目标结点后，len域记录了目标结点的最短路长。沿fa域回溯，则可找出最短路径通过BFS找树的最长路n n二次BFS能找出树的最长路
