数据结构 图总结

数据结构 图总结

一、图的基本概念

1. 简单图：不存在重复边、不存在顶点到自身的边。

2. 有n个顶点的无向图最多有n(n-1)/2条边、有n个顶点的有向图最多有n(n-1)条边。

3. 连通图、连通分量是无向图的说法，强连通图、强连通分量是有向图的说法。

4. 无向图中的极大连通子图称为连通分量。极大要求该连通图包含其所有的边；极小连通子图是既要保持图连通，又要使得边数最少的子图。

5. 边最少的问题：连通无向图：n-1条边（树）；强连通有向图：n条边（环）。

6. 连通图的生成树是包含图中全部顶点的一个极小连通子图。（无环的）

7. 无向图的全部顶点的度之和等于边数的两倍。

8. 有向图的全部顶点的入度之和和出度之和相等并且等于边数。

9. 简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。

二、图的储存

1. 无向图的邻接矩阵一定是一个对称矩阵（并且唯一）。

2. 邻接矩阵存储图的局限性：必须按行、按列对每个元素进行检测，所花费的时间代价很大。稠密图适合使用邻接矩阵表示。

3. 有向图，顶点i的出度等于第i行中1的个数，入度等于第i列中1的个数。

4. 图的邻接表结合了顺序存储和链式存储方式。

5. 邻接表：顶点表结点由顶点域（data）和指向第一条邻接边的指针（firstarc）构成，边表结点由邻接点域（adjvex）和指向下一条邻接边的指针域（nextarc）构成。

6. 如果G为无向图，则所需的存储空间为O（|V|+2|E|），如果G为有向图，则所需的存储空间为O（|V|+|E|）。

7. 如果要确定给定的两个顶点间是否存在边，在邻接矩阵里可以立刻查到，在邻接表中效率较低。

8. 求有向图结点的度，必须遍历整个邻接表

9. 十字链表是有向图的一种链式存储结构。顶点结点之间是顺序存储。

10. 邻接多重表是无向图的一种链式存储结构。

三、图的遍历

1. 广度优先遍历使用了队列，深度优先遍历使用了栈。

2. 广度优先遍历和深度优先遍历算法，采用邻接矩阵存储时总的时间复杂度为O(|V|2)，采用邻接表存储时中的时间复杂度为O（|V|+|E|）。

3. 深度优先生成树的树高总是大于等于广度优先生成树的树高。

四、最小生成树

1. 一个连通图的生成树是图的极小连通子图。

2. 最小生成树不唯一，但最小生成树的边的权值之和总是唯一的。

3. Prim算法的时间复杂度为O（|V|2），不依赖于|E|，所以适用于求解边稠密的图的最小生成树。

4. Kruskal算法的时间复杂度为O（|E|log|E|）,所以适合于边稀疏而顶点较多的图。

5.广度优先搜索查找最短路径只是对无权图而言。

6. Dijkstra算法的时间复杂度为O（|V|3）。若边上带有负权值，Dijkstra算法并不适用。

7. Floyd算法的时间复杂度为O（|V|3）.允许图中有带负权值的边，但不允许有带负权值的边组成的回路。

8. 拓扑序列：在图论中，由一个有向无环图的顶点组成的序列。每个顶点出现且只出现一次。

9. 关键路径上的活动延期完成：必将延期整个工程完成时间。

10.关键路径上的活动提前完成：不一定使整个工程提前完成。

课后题易错：

1. 所有权值最小的边不一定会出现在所有的最小生成树中。
2. 最短路径一定是简单路径。
3. 深度优先遍历和拓扑排序可以判断一个有向图是否有环，关键路径是否可以存在争议。
4. 含有顶点数目大于1的强连通分量一定有环。
5. 拓扑序列唯一，并不能唯一确定该图。