​ Dijkstra算法解决了有向图上带正权值的单源最短路径问题，其运行时间要比Bellman-Ford算法低，但适用范围比Bellman-Ford算法窄。

​ 单源最短路径指的是从一个顶点到其它顶点的具有最小权值的路径。我们之前提到的广度优先搜索算法就是一种无权图上执行的最短路径算法，即在所有的边都具有单位权值的图的一种算法。单源最短路径算法可以解决图中任意顶点间的最短路径。

​ 关于最小生成树的概念，在前一篇文章中已经讲到，就不在赘述了。下面介绍Prime算法：

​ 其基本思想为：从一个顶点出发，选择由该顶点出发的最小权值边，并将该边的另一个顶点包含进来，然后找出由这两个顶点出发的最小边，依此类推，直至包含所有的顶点。如果期间构成环，就舍弃该边，继续寻找最小边。

​ 在图论中，树是指无回路存在的连通图。一个连通图的生成树是指包含了所有顶点的树。如果把生成树的边的权值总和作为生成树的权，那么权值最小的生成树就称为最小生成树。因为最小生成树在实际中有很多应用，所以我们有必要了解怎样生成最小生成树。构造最小生成树的两种常用方法：Kruskal算法、Prim算法。本文介绍Kruskal算法，Prim算法在下篇文章中介绍。

在前面的文章中，我已经讨论了无向图的遍历，现在发现在有向图中，可能会发生无法遍历到所有节点的情况。因此在经历一次深度优先搜索遍历后，如果还存在未被搜索到的节点，则需要再从新的节点开始进行深度优先搜索遍历，直到访问完所有节点。

​ 在很多应用中，很多事情都是按照一定的次序来进行的，比如说起床穿衣时，不可能先穿鞋再穿袜子，但是穿袜子和穿裤子可以不分先后次序。这种按照一定顺序进行的活动，可以使用顶点表示活动，顶点之间的有向边表示活动间的先后关系，这种有向无回路图说明了活动的先后次序。

​ 关于图的存储在上一篇文章中已经讲述，在这里不在赘述。下面我们介绍图的深度优先搜索遍历（DFS）。

​ 深度优先搜索遍历实在访问了顶点$v_i$后，访问$v_i$的一个邻接点$v_j$；访问$v_j$之后，又访问$v_j$的一个邻接点，依次类推，尽可能向纵深方向搜索，所以称为深度优先搜索遍历。显然这种搜索方法具有递归的性质。图的BFS和树的搜索遍历很类似，只是其存储方式不同。

​ 图的存储方法：邻接矩阵、邻接表

​ 链表队列很简单，之前看到过，没有用程序实现。其原理就是遵循FIFO原则,只能从队首取元素，从队尾插入元素，就和排队模型一样。因此只需要队首指针和队尾指针就可以方便的进行队列操作。因为在最近看的图论算法中，经常用到队列，在这里就先用程序实现链表队列。

一棵B树T是具有如下性质的有根树（设根为root）:

• 每个节点x有一下域：

  • num,当前存储在节点x的关键字个数,关键字以非降序存放，因此$key[i]\le key[i+1]\le\cdots \le key[n]$;
  • isleaf,是一个bool值，如果x为叶子节点，则isleaf=true；
  • 每个节点包括$num+1$个指向其子女的指针$p[0], p[1], \cdots ,p[num]$。如果$x$为叶子，则$p=NULL$；
  • 每个节点包括$num$个关键字$key[0], key[1], \cdots, key[num-1]$。各关键字$key[i]$对存储在各子树中的关键字范围加以分隔： $k1\le key[1]\le k2\le key[2]\le\cdots$

• 每个叶节点具有相同的深度；

• 每一个节点包含的关键字有上下界。这些界可以用一个称为B树的最小度数的固定整数$M\ge2$来表示。每个非根节点的个数$n$必须满足$M-1\le n\le 2M-1$。根节点至少包括 一个关键字。如果一个节点是满的，则它恰好有$2M-1$个关键字。

  阅读全文 »