图论基础(修改).ppt

图论基础 A图为无向图，它的领接表为： B图为有向图，它的领接表为： 对下面两个图分别从a和V1出发进行宽度优先遍历，写出遍历结果。 2、图的广度优先遍历 左图从顶点a出发，进行广度优先遍历的结果为： a，b，d，e，f，c，g 右图从V1出发进行广度优先遍历的结果为： V1，V2，V3，V4，V5，V6，V7，V8 深度优先遍历与宽度优先遍历的比较： 深度优先遍历实际上是尽可能地走“顶点表”； 而广度优先遍历是尽可能沿顶点的“边表”进行访问，然后再沿边表对应顶点的边表进行访问，因此，有关边表的顶点需要保存(用队列，先进先出)，以便进一步进行广度优先遍历。 下面是广度优先遍历的过程： 时间：O（n*n） Procedure bfs(i:integer)； {宽度优先遍历，图用邻接矩阵表示} Begin 访问顶点i；Visited[i]:=true;顶点i入队q； while 队列q非空 do begin head:=head+1;v:=q[head]v； for j:=1 to n do begin if (not Visited[j]) and (a[v,j]=1) then begin 访问顶点j；Visited[j]:=true;顶点j入队q; end; end; end; End； 四、欧拉图和哈密尔顿图 哥尼斯堡七桥问题 1、欧拉图 1）定义： 欧拉通路——通过图中每条边一次且仅一次，并且过每一顶点的通路。 欧拉回路——通过图中每条边一次且仅一次，并且过每一顶点的回路。 欧拉图——存在欧拉回路的图。 2）定理1： 存在欧拉路的条件：图是连通的，且存在0个或2个奇点。 如果存在2个奇点，则欧拉路一定是从一个奇点出发，以另一个奇点结束。 定理2： 存在欧拉回路的条件：图是连通的，且不存在奇点。 习题1、以下图形能否一笔画成？ 练习： 习题2、“两只蚂蚁比赛问题”。两只蚂蚁甲、乙分别处在图 G中的顶点a，b处，并设图中各边长度相等。甲提出同乙比赛：从它们所在顶点出发，走过图中所有边最后到达顶点c处。如果它们速度相同，问谁最先到达目的地？ 3)寻找欧拉回路的算法 寻找欧拉回路的算法有多种， 下面介绍一种基于递归的经典算法框架： find_circuit(结点i)； { 当结点i有邻居时 { 选择任意一个邻居j；删除边(i,j)； find_circuit（结点j）； } circuit[circuitpos] := 结点i； circuitpos := circuitpos+1； } 如果寻找欧拉回路，对任意一个点执行find_circuit；如果是寻找欧拉路径，对一个奇点执行find_circuit；算法的时间复杂度为O(m+n)。 周游世界游戏问题 2、哈密尔顿图 1）定义： 哈密尔顿通路——通过图中每个顶点一次且仅一次的通路。 哈密尔顿回路——通过图中每个顶点一次且仅一次的回路。 哈密尔顿图——存在哈密尔顿回路的图。 2）判定： 遗憾的是至今尚未找到一个判别哈密尔顿回路和通路的充分必要条件。 判断下图是否具有哈密尔顿回路，通路。 练习： 3）寻找哈密尔顿环的算法 到现在为止，寻找哈密尔顿环并没有一种有效的算法，一般只能用有哪些信誉好的足球投注网站解决。 图论试题的分析思路： 1、建图 2、决定采用什么样的算法 3、编写程序 五、应用举例 1、一笔画问题（one.???） [问题描述]编程对给定的一个图，判断能否一笔画出，若能请输出一笔画的先后顺序，否则输出“No Solution！”。 [输入格式] 输入文件共n+1行，第1行为图的顶点数n，接下来的n行（每行n个数据）为图的邻接矩阵， G[i,j]=1表示顶点i和顶点j有边相连，G[i,j]=0表示顶点i和顶点j无边相连。 ?[输出格式] 若能一笔画出，则输出一笔画出的顶点先后顺序，否则输出“No Solution！”。 ?[样例输入] 6 0 1 0 0 1 1 1 0 1 1 0 1 0 1 0 1 0 0