数据结构-图

数据结构-图

一、图的基本概念

1.图不可以是空图，图的顶点集V一定非空，但边集E可以为空。

2.简单图：不存在重复边且不存在顶点到自身的边，称图G为简单图。

3.并非V和E的任何子集都能构成G的子图，因为这样的子集可能不是图，即E的子集中的某些边关联的顶点可能不在这个V的子集中。

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

5.生成树：连通图的生成树是包含图中全部顶点的一个极小连通图。

6.有向树：一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树。

二、图的存储

1.图的存储结构：邻接矩阵、邻接表、十字链表、邻接多重表和边集数组。

2.稠密图适合使用邻接矩阵的存储表示。

3.稀疏图适合使用邻接表的存储表示。

4.十字链表是有向图的一种链式存储结构。

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

6.边集数组：通过数组存储每条边的起点和终点。如果是网，则增加一个权值域。

三、图的遍历

1.在遍历图的过程中，需要设置一个辅助数组来标记顶点是否被访问过。

2.广度优先搜索：类似于二叉树的层序遍历算法，不是一个递归的算法。必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

3.深度优先搜索：类似于树的先序遍历，是一个递归算法，需要借助一个递归动作栈。

4.对于同样的一个图，基于邻接矩阵的遍历得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历得到的DFS序列和BFS序列是不唯一的。

四、图的应用

1.求最小生成树算法：Prim算法和Kruskal算法。

2.图的最小生成树首先必须是带权连通图。

3.Prim（普里姆）算法：选择一个与当前T中顶点集合距离最近的顶点，适合于求解边稠密的图的最小生成树。

4.Kruskal（克鲁斯卡尔）算法：选取当前未被选取过且权值最小的边，适合于边稀疏而顶点较多的图。

5.最短路径：把带权路径长度最短的那条路径称为最短路径。

6.求最短路径的算法：Dijkstra算法和Floyd算法。

7.Dijkstra（迪杰斯特拉）算法：求单源最短路径问题，边的权值不能为负。

8.Floyd（弗洛伊德）算法：求各顶点之间最短路径问题，不允许图中有包含负权值的边组成的回路。

9.AOV网：顶点表示活动的有向图。

10.AOE网：用边表示活动的有向图。