图

图的存储结构

1. 邻接矩阵表示法

2. 邻接表表示法

3. 邻接多重表

4.十字链表

 

邻接矩阵表示法

优点：易于操作

缺点：对于稀疏图来讲，该方法极浪费

解决方法：邻接表表示法

 

邻接表表示法

优点：不必存储不存在的边（弧）

缺点：结构较复杂

         如建立逆邻接表，方便计算入度，但实际上，一条边需分别在邻接表与逆邻接表中存储

 

图的遍历

 从图中某一顶点出发，沿着一 些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历 ( Graph Traversal )。  深度优先搜索 DFS (Depth First Search) 广度优先搜索 BFS (Breadth First Search) 

图的应用

图的连通性问题----最小生成树

   普里姆（Prim）算法

   克鲁斯卡尔（Kruskal）算法

 

最小生成树

• 概念:在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树称为该连通网的最小生成树。