博客

1

图的定义和术语

2 图的存储结构

• 
  数组表示法
  
• 
  邻接表
  
• 
  十字链表
  
• 
  邻接多重表
  

3 图的遍历

• 
  深度优先遍历和广度优先遍历
  

4 图的连通性问题

• 
  无向图的连通分量和生成树
  
• 
  有向图的强连通分量
  
• 最小生成树

1. 
   普里姆算法
   
2. 
   克鲁斯卡尔(Kruskal)算法
   

• 
  关节点和重连通分量
  

5 有向无环图及其应用

• 
  拓扑排序
  
• 
  关键路径
  

6 最短路径

• 从某个源点到其余各顶点的最短路径

1. 
   迪杰斯特拉算法Dijkstra
   

• 每一对顶点之间的最短路径

1. 
   弗洛伊德(Floyd)算法