数据结构导论-总结 5章 数据结构导论02142

紧接上一篇

第五章： 图

无向完全图 任何两点之间都有边的无向图。具有n个顶点的五项无安全图的边数 n(n-1)/2。

有向完全图 任何两点都有弧的有向图。具有n个顶点的有向完全图的弧数为n(n-1).

图的边附带的数值，这个数值叫权。每条边都带权的图称为带权图。

顶点的度，入度，出度 无向图中顶点v的度是与该顶点相关联的边的数目。

路径上边（弧）的数目称为路径长度。

简单路径、回路、简单回路。序列中顶点不重复出现的路径称为简单路径。第一个顶点和最后一个顶点相同的路径称为回路。

除了第一个顶点和最后一个顶点外，其余顶点都不重复的回路，称为简单回路。

连通、连通图、连通分量 在无向图中，从顶点v到顶点v1有路径则称v v1是连通的。如果图中任意两个顶点都是连通的则称为连通图。存在不连通的顶点，称为非连通图，连通分量是无向图中极大连通子图。

强连通图、强连通分量 两个顶点间双向连通 称为有向图是强连通图，有向图的的极大连通子图称为强连通分量。

生成树 、生成森林 生成树是含有该连通图的全部顶点的一个连通子图。若连通图的顶点个数为n，则该连通图的生成树的边数为n-1。若连通图的边数大于n-1，则图中一定有环，如果图的边数小于n-1，则图一定不是连通图。

图的存储结构

邻接矩阵 无向图的邻接矩阵是一个对称矩阵。

邻接表 是顺序存储与链式存储相结合的存储方法。

图的遍历 从图的某个顶点出发，系统的访问图中的每个顶点，并且每个顶点只被访问一次。

方法 深度优先遍历 与 广度优先遍历。

深度优先类似与树的先序遍历。

邻接表为存储结构，深度优先搜索算法时间复杂度是O(n+e),采用邻接矩阵存储结构，深度优先算法时间复杂度O(n平方)。

广度优先遍历类似与树的按层次遍历的过程，根据先进先出的特点，可以采用队列的暂存刚访问过的顶点。

最小生成树

连通图一次遍历所经过边的集合及图中多有顶点的集合就构成该图的一颗生成树，由于连通图的遍历序列不是唯一的，所以能得到不同的生成树。

一个图的最小生成树是图所有生成树中权总和最小的生成树。

构成最小生成树的算法 ：prim算法 克鲁斯卡尔方法。

单源最短路径算法：dijkstra算法。

拓扑排序 找一个有向图的一个拓扑序列的过程，完成拓扑排序的前提条件是aov 网中不允许有回路。算法的复杂度O(n+e)