数据结构图

图基本概念

• 总结：

  图的存储

• 邻接矩阵法：
• 邻接表法：
• 比较：
• 十字链表法：（只存储有向图）
• 邻接多重表：（只存储无向图）
• 总结：

  图的广度优先遍历BFS

  对比树的层序遍历： 遍历所有连通分量，每个分量BFS： 根据BFS遍历得出序列->广度优先生成树，广度优先生成森林：

  图的深度优先遍历DFS

  对比图的先根遍历。 根据DFS遍历得出序列->深度优先生成树，深度优先生成森林：

  最小生成树

  
• Prim算法（加入顶点）
• Kruskal算法（加入边）
• 每个图的最小生成树的最小边权唯一，而树不唯一（不同起点和不同走法都会产生不同树），非连通图产生最小连通森林。

  最短路径

  分为单源，各顶点间最短路径。
• BFS法：（不适用带权图）
• Dijkstra法：（不适用负权图）
• Floyd法：
• 总结：

  有向无环图

  描述表达式：

  拓扑排序

  DAG的另一个应用。
  拓扑排序，和逆拓扑排序可能不唯一，图中有环则不存在。
• 逆拓扑排序： 也可以用DFS直接实现。

  关键路径

  源点到汇点路径可能有多条，最大路径长度的路径为关键路径，该条路径上的活动称为关键活动。整个工程最短时间就说关键路径的长度。 特性：