数据结构与算法_图

• 图（graph）

图的存储结构

邻接矩阵（稀疏性）

邻接表

十字链表

 

图的遍历（traversing graph）

深搜(Depth_First_search)

广搜(Breadth_First_Search)

最小生成树（Minimum Cost Spanning Tree)

1.Prim算法

 

 

 

 

 

 

 

 

 

2.Kruskal算法 

Prim算法是以结点为起点，找该点权值最小的边

Kruskal算法以边开始，直接找最小权值的边

边集数组按权由小到大

最短路径（shortest paths）

单源最短路径（single-source shortest paths) —— Dijkstra算法

 

所有顶点对之间之间的最短路径（all-pairs shortest paths）

想知道所有顶点到所有顶点的最短路径，循环v[0]，O(n3)    同样O(n3)的算法

Floyd算法

拓扑排序（topological sorting）

有向无环图（directed acyclic graph）

AOV（Activity On Vertex Network）描述一个过程，顶点表示活动，弧表示先后顺序（活动之间制约关系）

拓扑序列（topological order）存在v[i]到v[j]的一条路径，在序列中v[i]必须在v[j]之前

拓扑排序（topological sorting）根据有向图建立拓扑序列

结果若全部结点都输出，说明不存在回路，否则说明存在

采用的数据结构：邻接表

最小生成树和最短路径对边操作，用邻接矩阵；拓扑排序对结点操作，用邻接表

关键路径（Critical Path）

AOE（Activity On Edge Network）描述一个过程，顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间

某顶点代表的事件发生，从该顶点出发的活动才能开始；进入某顶点的活动结束，该顶点代表的事件才能发生