09年自考《数据结构》各章要点二[4]

图的存储结构

·邻接矩阵表示法用一个n阶方阵来表示图的结构是唯一的适合稠密图

·无向图邻接矩阵是对称的

·有向图行是出度列是入度

建立邻接矩阵算法的时间是O(n+n^+e)其时间复杂度为O(n^)

·邻接表表示法用顶点表和邻接表构成不是唯一的适合稀疏图

·顶点表结构 vertex | firstedge指针域存放邻接表头指针

·邻接表用头指针确定

·无向图称边表

·有向图又分出边表和逆邻接表

·邻接表结点结构为 adjvex | next时间复杂度为O(n+e)空间复杂度为O(n+e)

图的遍历

·深度优先遍历借助于邻接矩阵的列使用栈保存已访问结点

·广度优先遍历借助于邻接矩阵的行使用队列保存已访问结点

生成树的定义若从图的某个顶点出发可以系统地访问到图中所有顶点则遍历时经过的边和图的所有顶点所构成的子图称作该图的生成树

最小生成树图的生成树不唯一从不同的顶点出发可得到不同的生成树把权值最小的生成树称为最小生成树(MST)

[] [] [] [] [] [] [] [] [] [] [] []