图和其最小生成树

1. 图的表示

• 邻接表：为每个顶点存储一个保存该顶点相邻顶点的链表。
  1.存储空间：O（V+E)
  2.将权值和顶点一同存入链表节点能够很方便地表示带权图
  3.不足，要确定某条边（v,u）是否存在的话需要从v顶点的链表中去搜索u，假如v有很多相邻顶点的话，搜索开销较大。

• 邻接矩阵：假设图有n个顶点，构造一个n*n的矩阵，每个元素都是0或1，表示横坐标和纵坐标顶点是否是一条边的两个顶点。
  1.存储空间 O（n*n），对于无向图，可以只存储上三角矩阵或下三角矩阵
  2.将0和1替换成NAN和权值可以方便地表示带权图
  3.能够较快判断边是否存在

2. 图的搜索

广度优先(BFS)：对于一个特定源顶点s,算法会首先搜索和s距离为1的所有顶点，然后是距离为2的所有顶点，以此类推。

深度优先（DFS）：对一个给定顶点来说s来说，选择任意一个相邻的没有被访问过的顶点u，然后选择一个没有访问过的u的临近点v，以此类推，如果到v之后没有未被访问的临近顶点，那么返回v的上级u选择其他未被访问的临近顶点。

3. 拓扑排序

将有向无环图中的顶点以线性方式进行排序。即对于任何连接自顶点u到顶点v的有向边{u, v}，在最后的排序结果中，顶点u总是在顶点v的前面.
我们可以通过DFS实现一个拓扑排序。伪代码：
Java
//其实就是深度优先遍历，每当一个节点深度优先遍历结束的话,将它插入一个链表的头部
L ← Empty list that will contain the sorted nodes
S ← Set of all nodes with no outgoing edges
for each node n in S
do
visit(n)
function visit(node n)
if n has not been visited yet then
mark n as visited
for each node m with an edge from m to n
do
visit(m)
add n to L head

## 4. 最小生成树算法
**KrusKal算法**：
1. 将顶点集合V中的每个元素单独成一个集合（set）；
2. 将边按照集合排序，取一条权值最小的边{u,v}
3. 检测u和v在不在一个set中，若不在，将边加入选定的边集合，将两个顶点的set合并。否则舍弃该边。

**Prim算法**：
1).  输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).  初始化：Vnew= {x}，其中x为集合V中的任一节点（起始点），Enew = {}
3). 重复下列操作，直到Vnew= V：
   1. 在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
   2. 将v加入集合Vnew中，将<u, v>边加入集合Enew中；

4). 输出：使用集合Vnew和Enew来描述所得到的最小生成树