十二单元图论剖析.doc

第十二单元　图与图论算法 导入：七桥问题【Seven Bridges Problem 】 在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？ 1736年欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的论文，他用抽像分析法将这个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个“图”。 在解答问题的同时，开创了数学的一个新的分支---图论与几何拓扑。图论本身是应用数学的一部分。 12.1图的基本概念 （1）图的定义 图是由一个顶点的集合V和一个顶点间关系的集合E组成，记为 G=（V，E） V：顶点的有限非空集合。 E：顶点间关系的有限集合（边集）。 存在一个结点v，可能含有多个前驱结点和后继结点。 （2）无向图和有向图 无向图（如图1.2）： 在图G=（V，E）中，如果对于任意的顶点a，b∈V， 当(a,b)∈E时，必有（b,a）V={1, 2, 3, 4, 5} E={(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)} 有向图 (如图1.3)： 如果对于任意的顶点a,b∈V,当(a,b)∈E时 ,(b,a)∈E未必成立，则称此图为有向图。 在有向图中，通常用带箭头的边连接两个有关联的结点。 V={1, 2, 3, 4,5} E={1,2,1,4,2,3,2,5,3,1,5,3,5,4} （3）顶点的度、入度和出度 在无向图中：顶点v的度是指与顶点v相连的边的数目D(v)。D(2)=3 在有向图中：入度——以该顶点为终点的边的数目和 . ID(3)=2 出度——以该顶点为起点的边的数目和 . OD(3)=1 度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。 度：等于该顶点的入度与出度之和。 D(5)=ID(5)+OD(5)=1+2=3 无向图： 无向完全图: （4）路径、简单路径、回路 在图G=（V，E）中，如果对于结点a，b，存在满足下述条件的结点序列x1……xk(k1) x1=a，xk=b (xi，xi+1)∈E i=1‥k-1 则称结点序列x1=a，x2，…，xk=b为结点a到结点b的一条路径，而路径上边的数目（k-1）称为该路径的长度。 图1.4: 1.(1,2,3,5) 长度=3 2.(1,2,3,5,2) 长度=4 3.(1,2,5,4,1) 长度=4 图1.5: (1,2,5,4) 长度=3 1.如果一条路径上的结点除起点x1 和终点xk可以相同外，其它结点均不相同，则称此路径为一条简单路径。 2.x1=xk的简单路径称为回路（也称为环） （5）连通、连通图、连通分量(无向图) 连通：“连成一片”。 连通图：“能连成一片的图”。 连通：如果存在一条从顶点u到v有路径，则称u和v是连通的。 连通图：图中任意的两个顶点u和v都是连通的，称为连通图（如图1.4）。否则称为非连通图（如图1.6）。 连通分量：无向图中的极大连通子图。图1.6中有3个连通分量：{1 2 4 5} {3 6} {7 8} （6）带权图 一般的图边上没有数字，边仅表示两个顶点的相连接关系（ 图1.4,1.5,1.6… ） 图中的边可以加上表示某种含义的数值，数值称为边的权，此图称为带权图。也称为网。 (如图1.7)  12.2图的存储结构 我们可以认为图的结构为：G=( V,E ) V是顶点：数组或记录。E是边：邻接矩阵/邻接表 图的存储结构类型： 1.邻接矩阵 2.邻接表 3.边集数组 4.前向星（可以被邻接表代替） （1）邻接矩阵(空间复杂度O(n*n)) 邻接矩阵是表示结点间相邻关系的矩阵。若G=（V，E）是一个具有n个结点的图，则G的邻接矩阵是如下定义的二维数组 a[1..n][1..n]。（注意：n尽量稍微大点） 优点：代码书写简单,便于操作 缺点：内存空间占用太大, 找邻接点慢 格式： 对角线为0：自身不相连。 无向图：是对称矩阵。有向图一般不是。 第i行非0 的个数是结点i的度 具体到题目时，数据的给出格式多种多样： 1、直接给出邻接矩阵，直接读即可。 如：输入文件内容： 50 2 2 3 02 0 1 0 32 1 0 0 23 0 0 0 40 3 2 4 0 2、给出边的顶点。 如输入文件：两个顶点及权值 5 71 2 21 3 21 4 32 3 12 5 33 5 24