数据结构第七章图.ppt

图的基本概念 图的存储表示 图的遍历 图的应用 §7.1 图的基本概念 图(Graph) 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph＝( V, E ) 其中:V = { x | x ? 某个数据对象}是顶点的有穷非空集合； E = {(x, y) | x, y ? V } 或 E = {x, y | x, y ? V}是顶点之间关系的有穷集合。 完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有 n 个顶点的有向图有n(n-1) 条边, 则此图为完全有向图。 子图 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。若 V’? V 且 E‘?E, 则称 图G’ 是 图G 的子图。 路径 在图 G＝(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, …, vpm，到达顶点vj。则称顶点序列 (vi vp1 vp2 ... vpm vj) 为从顶点vi 到顶点 vj 的路径。 连通图与连通分量 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。 §7.2 图的存储表示 邻接表 (Adjacency List) 基本思想：在无向图中，将依附于某个顶点的所有边（边结点）以单链表形式链接，每个链表设立一个表头结点。 §7.2 图的遍历 ( Graph Traversal ) 图的遍历从图中某一顶点出发，沿着一 些边访遍图中所有的顶点，且使每个顶点仅被访问一次。 广度优先有哪些信誉好的足球投注网站BFS ( Breadth First Search ) 广度优先有哪些信誉好的足球投注网站的示例 对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。 最小生成树 ( minimum cost spanning tree ) 最小生成树----在一个连通网得到的所有生成树中, 权值之和最小的生成树称为最小生成树. 最短路径 (Shortest Path) 最短路径问题： 从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。 问题解法: 边上权值非负情形的单源最短路径问题— Dijkstra算法 边上权值为任意值的单源最短路径问题— Bellman和Ford算法 所有顶点之间的最短路径— Floyd算法 5 5 4 6 1 3 5 6 2 4 2 3 6 1 6 5 7 7 5 6 6 4 3 2 5 5 3 5 6 4 2 5 7 1 5 6 1 4 6 3 5 2 ? 6 1 5 ? ? 6 ? 5 ? 3 ? 1 5 ? 7 5 4 5 ? 7 ? ? 2 ? 3 5 ? ? 6 ? ? 4 2 6 ? fromvex endvex length 1 2 3 4 5 1 5 ? 1 4 5 1 3 1 1 2 6 1 6 ? 最小 1 2 6 1 3 1 1 3 1 1 2 6 1 2 6 3 2 5 1 5 ? 3 5 5 1 6 ? 3 6 4 最小 3 6 4 3 2 5 3 2 5 3 6 4 1 4 5 6 4 2 最小 6 4 2 最小 3 5 5 3 2 5 5 2 3 5 2 3 3 5 6 4 2 5 7 1 5 6 1 4 6 3 5 2 克鲁斯卡尔 (Kruskal) 算法 基本思想： 设有有 n 个顶点的连通网络 N = { V, E }, 最初先构造一个只有 n 个顶点, 没有边的非连通图 T = { V, ? }, 图中每个顶点自成一个连通分量。当在 E 中选到一条具有最小权值的边时, 若该边的两个顶点落在不同的连通分量上，则将此边加入到 T 中; 否则将此边舍去，重新选择一条权值最小的边。如此重复下去, 直到所有顶点在同一个连通分量上为止。 5 4 6 1 3 2 1 2 3 4 5 回路 7 4 6 1 3 2 5 7 3 6 11 10 1 4 2 2 * 1 2 5 6 3