Chap9_算法与数据结构—C语言描述(第2版)张乃孝编课件1.ppt

第9章 图 图 定义和术语 图(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是顶点，v为弧尾，w为弧头 无向图——无向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v) 定义和术语 定义和术语 对于有n个顶点的无向图，边或弧e的取值范围是0到n(n-1)/2。 n(n-1)/2条边的无向图称为完全无向图 对于有n个顶点有向图，e的取值范围是0到n(n-1)。 有n(n-1)条弧的有向图称为完全有向图 定义和术语 有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做权。 这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网(Network)。 子图——如果图G(V,E)和图G‘(V’,E‘),满足： V’?V E’?E 则称G‘为G的子图 定义和术语 无向图： 顶点v的度(Dgeree)是和v相关联的边的数目，记为TD(V)。 有向图： 以顶点v为头的弧的数目称为v的入度，记为ID(v) 以v为尾的弧的数目称为v的出度，记为OD(v) 顶点v的度TD(v)=ID(v)+OD(v) 定义和术语 无向图G(V,{E})中从顶点v到顶点v‘的路径(Path)是一个顶点序列（v=vi,0,vi,1,…,vi,m=v’），其中(vij-1, vi,j) ∈E,1≤j≤m。i = 1, 2, …, k，表示v到v’间有k条路径。 如果G是有向图，则路径也是有向的，顶点序列应满足vi,j-1, vi,j∈E, 1≤j≤m。 路径的长度是路径上的边的数目。 第一个顶点和最后一个顶点相同的路径称为回路或环(Cycle)。 序列中顶点不重复的出现的路径称为简单路径。 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为简单回路或简单环。 定义和术语 在无向图G中，如果从顶点v到顶点v有路径，则称v和v是连通的。 如果对于图中任意两个顶点vi,vj和都是连通的，则称G是连通图(Connected Graph) 所谓连通分量(Connected Component)是指无向图中的极大连通子图。 定义和术语 有向图G中，如果对于每一对vi,vj∈V，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。 有向图中的极大强连通子图称作有向图的强连通分量。 定义和术语 图的遍历 图的遍历（Traversing Graph）:从图中某一个顶点出发，访问图中的其余顶点，且使每个顶点仅被访问一次。 方法： 深度优先有哪些信誉好的足球投注网站 广度优先有哪些信誉好的足球投注网站 图的遍历 图的遍历:深度优先有哪些信誉好的足球投注网站 深度优先有哪些信誉好的足球投注网站（Depth First Search） 1 从任一个顶点v出发，访问该顶点； 2 然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到； 3 此时若图中尚有顶点未被访问，则另选下中下一个未被访问的顶点作起始点，访问该顶点，继续过程2。 深度优先遍历算法 递归算法 图的遍历:深度优先有哪些信誉好的足球投注网站 int visited[MAXNODE] // 访问标志数组 void DFSTraverse(Graph G) { for(v=0；vG.vernum；v++) visited[v]=0； // 初始访问数组置未访问标志 for(v=0；vG.vernum；v++) if(!visited[v]) DFS(G, v)； // 对未访问过的顶点调用 DFS }// DFSTraverse ? void DFS(Graph G, int v) { // 从第 v个顶点出发递归地深度优先遍历图 G visited[v]=1； visit[v]； // 访问v顶点（输出v） for(w=GraphFirstAdj(G, v)； w； w=GraphNextAdj(G, v, w)) if(!visited[w]) DFS(G, w)； }// DFS 图的遍历:广度优先有哪些信誉好的足球投注网站 广度优先有哪些信誉好的足球投注网站 1 从图中某顶点v出发，在访问v之后， 2 依次访问v的各个未曾被访问过的邻接点，然后分别从这