《图论(C++版).ppt》由会员分享，可在线阅读，更多相关《图论(C++版).ppt（53页珍藏版）》请在三一文库上搜索。
1、图论算法c+,一对一和一对多的结构： 在前边讲解的线性表中，每个元素之间只有一个直接前驱和一个直接后继，在树形结构中，数据元素之间是层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。 图结构：是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。 图的应用极为广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯、计算机科学以及数学的其它分支。,一、图的定义及其术语 图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是
2、图G中顶点的集合，E是图G中边的集合。,对于图的定义，我们需要明确几个注意的地方： 线性表中我们把数据元素叫元素，树中叫结点，在图中数据元素我们则称之为顶点(Vertex)。 线性表可以没有数据元素，称为空表，树中可以没有结点，叫做空树，而图结构在国内大部分的教材中强调顶点集合V要有穷非空。 线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图结构中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。,图的各种定义,无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边(Edge)，用无序偶数对(Vi,Vj)来表示。 无向图：图中
3、所有顶点间的边均是无向的。,上图G1是一个无向图，G1=V1,E1，其中 V1=A,B,C,D， E1=(A,B),(B,C),(C,D),(D,A),(A,C) 无序对(A,B) 表示A和B之间的一条边(Edge)，因此(A,B) 和(B,A)代表的是同一条边。,上图G2是一个无向图，G2=V2,E2，其中 V2=A,B,C,D， E2=,有向边：若从顶点Vi到Vj的边有方向，则称这条边为有向边，也称为弧(Arc)，用有序偶数对来表示，Vi称为弧尾，Vj称为弧头。 有向图：图中所有顶点间的边均是有向的。,简单图：在图结构中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图
4、。以下两个则不属于简单图：,稀疏图、稠密图、权 有很少边或弧的图（enn）的图称为稀疏图，反之称为稠密图。 权(Weight)：与图的边和弧相关的数。权可以表示从一个顶点到另一个顶点的距离或耗费。带权的图通常称为网(Network)。,无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n*(n-1)/2条边。,有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。 含有n个顶点的有向完全图有n*(n-1)条边。,假设有两个图G1=(V1,E1)和G2=(V2,E2)，如果V2V1，E2E1，则称G2为G
5、1的子图(Subgraph)。,图的顶点与边之间的关系,对于无向图G=(V,E)，如果边(V1,V2)E，则称顶点V1和V2互为邻接点(Adjacent)，即V1和V2相邻接。 边(V1,V2)依附(incident)于顶点V1和V2，或者说边(V1,V2)与顶点V1和V2相关联。 顶点V的度(Degree)是和V相关联的边的数目，记为TD(V)，如下图，顶点A与B互为邻接点，边(A,B)依附于顶点A与B上，顶点A的度为3。,对于有向图G=(V,E)，如果有E，则称顶点V1邻接到顶点V2，顶点V2邻接自顶点V1。以顶点V为头的弧的数目称为V的入度(InDegree)，记为ID(V)，以V为尾的
6、弧的数目称为V的出度(OutDegree)，记为OD(V)，因此顶点V的度为TD(V)=ID(V)+OD(V)。下图顶点A的入度是2，出度是1，所以顶点A的度是3。,路径(Path)、路径长度、回路(Cycle) ：对无向图G=(V，E)，若从顶点vi经过若干条边能到达vj，称顶点vi和vj是连通的，又称顶点vi到vj有路径。 对有向图G=(V，E)，从顶点vi到vj有有向路径，指的是从顶点vi经过若干条有向边(弧)能到达vj。在一条路径中，若没有重复相同的顶点，该路径称为简单路径；第一个顶点和最后一个顶点相同的路径称为回路(环)；在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现的
7、回路称为简单回路(简单环)。,如果G是有向图，则路径也是有向的。下图用红线列举顶点B到顶点D的两种路径，而顶点A到顶点B就不存在路径。,路径的长度是路径上的边或弧的数目。 第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle)。,右图用红线列举了从顶点B到顶点D的四种不同路径：,连通图在无向图G中，如果从顶点V1到顶点V2有路径，则称V1和V2是连通的，如果对于图中任意两个顶点Vi和Vj都是连通的，则称G是连通图(ConnectedGraph)下图左侧不是连通图，右侧是连通图：,无向图中的极大连通子图称为连通分量。 注意以下概念： 首先要是子图，并且子图是要连通的； 连通子图含有极大顶点
8、数； “极大”的含义：指的是对子图再增加图G中的其它顶点，子图就不再连通。 具有极大顶点数的连通子图包含依附于这些顶点的所有边。,在有向图G中，如果对于每一对Vi到Vj都存在路径，则称G是强连通图。有向图中的极大强连通子图称为有向图的强连通分量。,下图左侧并不是强连通图，右侧是。并且右侧是左侧的极大强连通子图，也是左侧的强连通分量。,二、图的存储结构图的存储结构比较复杂，其复杂性主要表现在： 任意顶点之间可能存在联系，无法以数据元素在存储区中的物理位置来表示元素之间的关系。 图中顶点的度不一样，有的可能相差很大，若按度数最大的顶点设计结构，则会浪费很多存储单元，反之按每个顶点自己的度设计不同的
9、结构，又会影响操作。 图的常用的存储结构有：邻接矩阵、邻接链表、十字链表、邻接多重表和边表。,1.二维数组邻接矩阵存储 基本思想：对于有n个顶点的图，用一维数组vexsn存储顶点信息，用二维数组Ann存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，邻接矩阵中的元素Aij存放的是顶点i到顶点j之间关系的信息。 定义int G101101; Gij的值，表示从点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
10、0 0 1 0 G（C）= 8 2 10 4 1 1 0 0 10 11 3 6 4 11 ,另外有向图是有讲究的，要考虑入度和出度，顶点V1的入度为1，正好是第V1列的各数之和，顶点V1的出度为2，正好是第V1行的各数之和。,下面是建立图的邻接矩阵的参考程序段： #include using namespace std; int i,j,k,e,n; double g101101; double w; int main() int i,j; for (i = 1; i e; for (k = 1; k i j w; /读入两个顶点序号及权值 gij = w; /对于不带权的图gij=1 gj
11、i = w; /无向图的对称性,如果是有向图则不要有这句！ return 0; ,建立邻接矩阵时，有两个小技巧: 初始化数组大可不必使用两重for循环。 1) 如果是int数组，采用memset(g, 0 x7f, sizeof(g)可全部初始化为一个很大的数(略小于0 x7fffffff)， 使用memset(g, 0, sizeof(g)，全部清为0， 使用memset(g, 0 xaf, sizeof(g)，全部初始化为一个很小的数。 2)如果是double数组，采用memset(g,127,sizeof(g);可全部初始化为一个很大的数1.38*10306， 使用memset(g, 0
12、, sizeof(g)全部清为0.,2.数组模拟邻接表存储 邻接矩阵看上去是个不错的选择，首先是容易理解，第二是索引和编排都很舒服 但是我们也发现，邻接矩阵适合于结点数较少的稠密图。如果用来表示稀疏图，则会造成很大的空间浪费。 因此我们可以考虑另外一种存储结构方式，例如把数组与链表结合一起来存储，这种方式在图结构也适用，我们称为邻接表(AdjacencyList)。 基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。 每一个单链表设一个表头结点。 第i个单链表表示依附于顶点Vi的边(对有向图是以顶点Vi为头或尾的弧)。 图的邻接表存储法，又叫链式存储法。本来是要用链表
13、实现的，但大多数情况下只要用数组模拟即可。,邻接表（有向图） 邻接表的处理方法是这样： 图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。 图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储。,若是有向图，邻接表结构就是这样定义的。,有向图的邻接表：我们先来看下把顶点当弧尾建立的邻接表，这样很容易就可以得到每个顶点的出度：,但也有时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立一个有向图的逆邻接表：,此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。,对
14、于带权值的网图，可以在边表结点定义中再增加一个数据域来存储权值即可：,邻接表（网）,在进行邻接表的输入时，可以直接使用邻接表的定义方式直接输入； 也可由别的输入方式进行演变，课本上的就是利用边的顶点及其权值进行输入的,以下是用数组模拟邻接表存储的参考程序段：,const int N=maxn； / maxn表示图中最大顶点数const int E=maxe ； / maxe图中最大边数struct Edgeint u,v; /边所邻接的两个顶点int w; /边的权值int next; /边指针，指向下一条边的内存地址edgeE; / 静态内存，用于分配边int headN; / 表头int
15、num; / 内存的指针void init()for(int i=0;iE;i+) headi=-1; /这里为什么要设为-1num= 0;void addedge(int b,int e,int w)edgenum.u=b;edgenum.v=e;edgenum.w=w;edgenum.next=headb;headb=num+;,int main() num_edge=0; scanf(%d %d, 两种方法各有用武之地，需按具体情况，具体选用。,【例题】求一个有向图中指定顶点的出度,【问题描述】如题 【文件输入】 第1行：2个空格分开的整数n(2=n=200)和m(10=m=20000)
16、，分别表示图的顶点数和边数。 第2.m+1行：每行2个空格分开的整数i，j，i表示一条边的起点，j表示终点。 第m2行：1个整数k(2=k=n),表示指定的顶点。 【文件输出】只有一行为1个整数，表示顶点k的出度。 【样例输入】 5 8 3 5 4 5 4 3 2 3 5 4 4 1 4 2 2 4 4 【样例输出】4,【参考代码】,【方法1】邻接矩阵存储图 #include using namespace std; int a201201,n,m,ans=0,x; void init() int i,j,k; cinnm; for(i=1;ijk;ajk=1; int main() init
17、(); cink; for(int i=1;i=n;i+)if(aki)ans+; coutansendl; ,【方法2】邻接表存储图 #include using namespace std; struct Edge int to,next; w20005; int hMaxn=0,i,x,y,z,n,e,k,cnt,ans=0; void AddEdge(int x,int y) cnt+; wcnt.to=y; wcnt.next=hx; hx=cnt; int main() cinne;/读入顶点数目和边数 for(i=1;ixy; AddEdge(x,y); /建图 cink; fo
18、r(int p=hk;p!=0;p=wp.next) ans+; coutansendl; ,第二节 图的遍历,一、深度优先与广度优先遍历 从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组visitedi，未访问时值为false，访问一次后就改为true。 图的遍历分为深度优先遍历和广度优先遍历两种方法，两者的时间效率都是O(n*n)。,1.深度优先遍历 深度优先搜索(Depth First Search-DFS)遍历类似树的先序遍历，是树的先序遍历的推广。 1 算法思想 设初始状态时图中的所有顶点未被
19、访问，则： ：从图中某个顶点vi出发，访问vi；然后找到vi的一个邻接顶点vi1 ； ：从vi1出发，深度优先搜索访问和vi1相邻接且未被访问的所有顶点； ：转 ，直到和vi相邻接的所有顶点都被访问为止 ：继续选取图中未被访问顶点vj作为起始顶点，转(1)，直到图中所有顶点都被访问为止。,例如对右边的这个无向图深度优先遍历，假定先从1出发 程序以如下顺序遍历： 125，然后退回到2，退回到1。 从1开始再访问未被访问过的点3 ，3没有未访问的邻接点，退回1。 再从1开始访问未被访问过的点4，再退回1 。 起点1的所有邻接点都已访问，遍历结束。,下面给出的深度优先遍历的参考程序，假设图以邻接表存
20、储 void dfs(int i) /图用数组模拟邻接表存储，访问点i visitedi = true; /标记为已经访问过 for (int j = 1; j = numi; j+) /遍历与i相关联的所有未访问过的顶点 if (!visitedgij) dfs(gij); 主程序如下: int main() memset(visited,false,sizeof(visited); for (int i = 1; i = n; i+) /每一个点都作为起点尝试访问，因为不是从任何 /一点开始都能遍历整个图的，例如下面的两个图。 if (!visitedi) dfs(i); return 0
21、; ,广度优先搜索BFS,广度优先搜索(Breadth First Search-BFS)遍历类似树的按层次遍历的过程。 1 算法思想 设初始状态时图中的所有顶点未被访问，则： ：从图中某个顶点vi出发，访问vi； ：访问vi的所有相邻接且未被访问的所有顶点vi1，vi2，vim； ：以vi1，vi2， ，vim的次序，以vij(1jm)依此作为vi ，转； ：继续选取图中未被访问顶点vk作为起始顶点，转，直到图中所有顶点都被访问为止。,下图是有向图的广度优先搜索遍历示例(浅色箭头)。上述图的BFS次序是：v1 v2 v4 v3 v5,用广度优先搜索算法遍历图与深度优先搜索算法遍历图的唯一区别
22、是邻接点搜索次序不同，因此，广度优先搜索算法遍历图的总时间复杂度为O(n+e) 。 图的遍历可以系统地访问图中的每个顶点，因此，图的遍历算法是图的最基本、最重要的算法，许多有关图的操作都是在图的遍历基础之上加以变化来实现的。,【例题】无向图的BFS,【问题描述】一个无向图，从指定顶点出发进行BFS，求遍历得到的顶点序。 【文件输入】 第1行：2个空格分开的整数n(2=n=200)和m(10=m=20000)，分别表示图的顶点数和边数。 第2.m+1行：每行2个空格分开的整数i，j，i表示一条边的起点，j表示终点。 第m2行：1个整数k(1=k=n),表示指定的顶点。 【文件输出】只一行顶点序。
23、要求在同一层上，顶点序号从小到大输出。,#include using namespace std; int a101101,f101,q101,n,m,i,st; void init() int i,j,x,y; cinnm; memset(f,0,sizeof(f); for(i=1;ixy;axy=1;ayx=1; cinst; void dfs(int i)/深搜DFS int j; couti ;fi=1; for(j=1;j=n;j+)if(fj=0) ,二、欧拉图,1、欧拉路： 欧拉路径：图G中每条边经过一次且仅一次的路径称作欧拉路径。如下图中存在一条从顶点1到顶点6的欧拉路。一笔
24、画问题其实本质上就是判断一个图是否存在欧拉路。 无向图欧拉路存在的充要条件：图是连通的；图中有且仅有0个或2个度数为奇数的点。若存在2个奇点，则欧拉路一定是从一个奇点出发，以另一个奇点结束。 2、欧拉回路：图G中每条边经过一次且仅一次的回路称作欧拉回路。著名的柯尼斯堡七桥问题(图论起源),本质上就是讨论一个图的欧拉回路问题。,一个无向图有欧拉回路的必要条件是： 图是连通的；图中所有点的度均为偶数。,求欧拉路的算法很简单，使用深度优先遍历即可。 根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行DFS，时间复杂度为O(m+n)，m为边数，n是点数。
25、以下是寻找一个图的欧拉路的算法实现： 样例输入:第一行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 #include using namespace std; #define maxn 101 int gmaxnmaxn; /此图用邻接矩阵存储 int dumaxn; /记录每个点的度，就是相连的边的数目 int circuitmaxn; /用来记录找到的欧拉路的路径 int n,e,circuitpos,i,j,x,y,start;
26、 void find_circuit(int i) /这个点深度优先遍历过程寻找欧拉路 int j; for (j = 1; j = n; j+) if (gij = 1) /从任意一个与它相连的点出发 gji = gij = 0; find_circuit(j); circuit+circuitpos = i; /记录下路径 ,int main() memset(g,0,sizeof(g); cin n e; for (i = 1; i x y; gyx = gxy = 1; dux+; /统计每个点的度 duy+; start = 1; /如果有奇点，就从奇点开始寻找，这样找到的就是 fo
27、r (i = 1; i = n; i+) /欧拉路。没有奇点就从任意点开始， if (dui%2 = 1) /这样找到的就是欧拉回路。(因为每一个点都是偶点) start = i; circuitpos = 0; find_circuit(start); for (i = 1; i = circuitpos; i+) cout circuiti ; cout endl; return 0; ,注意以上程序具有一定的局限性，对于下面这种情况它不能很好地处理： 上图具有多个欧拉回路，而本程序只能找到一个回路。读者在遇到具体问题时，还应对程序作出相应的修改。,三、哈密尔顿环 欧拉回路是指不重复地走过
28、所有路径的回路，而哈密尔顿环是指不重复地走过所有的点，并且最后还能回到起点的回路。 哈密顿通路（回路）与哈密顿图 （Hamilton图） 通过图G的每个结点一次，且仅一次的通路（回路），就是哈密顿通路（回路）. 存在哈密顿回路的图就是哈密顿图 美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密顿图。闭合的哈密顿路径称作哈密顿圈，含有图中所有顶点的路径称作哈密顿路径。,【例题1】哈密顿路问题,【问题描述】邮递员在送信时，为了节省路途，自己规定：每次总是从n个村子中选择其中一个合适的村子出发，途经每
29、个村子仅且经过一次，送完所有的信。 已知各个村子的道路连通情况。请你帮邮递员选择一条合适的路线。 【文件输入】 第1行：整数n(2=n=200)：村子的个数。 接下来是一个n*n的0、1矩阵（每2个数之间有1个空格），表示n个村子的连通情况，如：ai,j=1 ，表示第i和第j个村子之间有路可走，如果ai,j=0，表示他们之间无路可走。 【文件输出】只有一行为1个整数表示可行的方案总数。,#include #include using namespace std; int a201201,visit201,found,n,sum; void init() int i,j; scanf(%d, ,
30、int main() int i; init(); found=0;sum=0; for(i=1;i=n;i+) memset(visit,0,sizeof(visit); visiti=1; dfs(i,1); if(found=0)printf(%d,0); else printf(%d,sum); return 0; ,使用简单的深度优先搜索，就能求出一张图中所有的哈密尔顿环。下面给出一段参考程序：,#include #include using namespace std; int start,length,x,n; bool visited101,v1101; int ans101,
31、 num101; int g101101; void print() int i; for (i = 1; i = length; i+) cout “ ” ansi; cout endl; ,void dfs(int last,int i) /图用数组模拟邻接表存储，访问点i，last表示上次访问的点 visitedi = true; /标记为已经访问过 v1i = true; /标记为已在一张图中出现过 ans+length = i; /记录下答案 for (int j = 1; j = numi; j+) if (gij=x /这里是回溯过程，注意v1的值不恢复。 ,int main()
32、 memset(visited,false,sizeof(visited); memset(v1,false,sizeof(v1); for (x = 1; x = n; x+) /每一个点都作为起点尝试访问，因为不是从任何一点开始都能找过整个图的 if (!v1x) /如果点x不在之前曾经被访问过的图里。 length = 0; /定义一个ans数组存答案，length记答案的长度。 dfs(0，x); return 0; ,【上机练习】,1、珍珠BEAD 【问题描述】 有n颗形状和大小都一致的珍珠，它们的重量都不相同。n为整数，所有的珍珠从1到n编号。你的任务是发现哪颗珍珠的重量刚好处于正
33、中间，即在所有珍珠的重量中，该珍珠的重量列(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轻，所以我们可以移走这两颗珍珠。 写一个程序统计出共有多少颗珍珠肯定不会是中
34、间重量。 【输入格式】 输入文件第一行包含两个用空格隔开的整数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辆铲雪车。铲雪车只能把它开过的地方（车道）的雪铲干净，无论哪儿有雪
35、，铲雪车都得从停放的地方出发，游历整个城市的街道。现在的问题是：最少要花多少时间去铲掉所有道路上的雪呢？ 【输入格式】 输入数据的第1行表示铲雪车的停放坐标（x,y），x，y为整数，单位为米。下面最多有100行，每行给出了一条街道的起点坐标和终点坐标，所有街道都是笔直的，且都是双向一个车道。铲雪车可以在任意交叉口、或任何街道的末尾任意转向，包括转U型弯。铲雪车铲雪时前进速度为20 km/h，不铲雪时前进速度为50 km/h。 保证：铲雪车从起点一定可以到达任何街道。 【输出格式】 铲掉所有街道上的雪并且返回出发点的最短时间，精确到分种。 【输入样例】 1 0 0 0 0 10000 10000
36、 5000 -10000 5000 10000 5000 10000 10000 10000 【输出样例】 3:55 【注解】 3小时55分钟,3、骑马修栅栏 【问题描述】 农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。 John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。 每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接
37、任意多(=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行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。,