资源描述：
《图论问题和算法ppt课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图论问题和算法秦高德2014.11图V1V4V2V3V5V4V3V2V1结点之间的关系：多对多，任两个结点之间都可能有关系存在.定义和术语v1图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对或有序对有向图——有向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头无向图——无向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)
2、是边的有限集合，边是顶点的无序对，记为(v,w)或(w,v)，并且(v,w)=(w,v)v3v2v1v1v2v4v3定义和术语图G1中：V(G1)={V1,V2,V3}E(G1)={,,}图G2中：V(G2)={V1,V2,V3,V4}E(G1)={(V1,V2),(V1,V3),(V1,V4),(V2,V3),(V2,V4),(V3,V4)}v3v2v1v1v2v4v3定义和术语例213213完全有向图完全无向图定义和术语有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这
3、种带权的图通常称为网(Network)。子图——如果图G(V,E)和图G‘(V’,E‘),满足：V’VE’E则称G‘为G的子图356例245136图与子图683定义和术语无向图：顶点v的度(Dgeree)是和v相关联的边的数目，记为TD(V)。有向图：以顶点v为头的弧的数目称为v的入度，记为ID(v)以v为尾的弧的数目称为v的出度，记为OD(v)顶点v的度TD(v)=ID(v)+OD(v)157324G26245136G1顶点5的度：3顶点2的度：4顶点2入度：1出度：3顶点4入度：1出度：0定义和术语无向图G(V,{E})中从顶点v到顶点v‘的路径(Path)是一个顶点序列
4、（v=vi,0,vi,1,…,vi,m=v’），其中(vij-1,vi,j)∈E,1≤j≤m。i=1,2,…,k，表示v到v’间有k条路径。如果G是有向图，则路径也是有向的，顶点序列应满足∈E,1≤j≤m。路径的长度是路径上的边的数目。第一个顶点和最后一个顶点相同的路径称为回路或环(Cycle)。序列中顶点不重复的出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为简单回路或简单环。例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路
5、：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1定义和术语在无向图G中，如果从顶点v到顶点v'有路径，则称v和v'是连通的。如果对于图中任意两个顶点vi,vj和都是连通的，则称G是连通图(ConnectedGraph)所谓连通分量(ConnectedComponent)是指无向图中的极大连通子图。CABDEFBDEFCA定义和术语有向图G中，如果对于每一对vi,vj∈V，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连
6、通分量。v3v2v1v3v2v1定义和术语连通图例245136强连通图356例非连通图连通分量例245136图的遍历图的遍历（TraversingGraph）:从图中某一个顶点出发，访问图中的其余顶点，且使每个顶点仅被访问一次。方法：深度优先搜索DFS广度优先搜索BFS图的遍历深度优先搜索：V1->V2->V4->V8->V5->V6->v3->v7广度优先搜索V1->V2->V3->V4->v5->v6->v7->v8v2v4v1v5v3v6v7v8图的遍历:深度优先搜索深度优先搜索（DepthFirstSearch）1从任一个顶点v出发，访问该顶点；2然后依次从v的未被访问的
7、邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；3此时若图中尚有顶点未被访问（不与v连通的点），则另选下中下一个未被访问的顶点作起始点，访问该顶点，继续过程2。深度优先遍历算法递归算法开始访问V0,置标志求V0邻接点有邻接点w求下一邻接点wV0W访问过结束NYNYDFS开始标志数组初始化Vi=0Vi访问过DFSVi=Vi+1Vi==Vexnums结束NNYY图的遍历:深度优先搜索intvisited[MAXNODE]//访问标志数组voidDFSTrave
