数据结构C语言版常用算法思想汇总

dijkstra 迪杰斯特拉 单源最短路径，必须给出源点V0

邻接矩阵cost存储有向网；使用一个集合S存储那些已经找到最短路径的顶点，初始只包含源点v0；设置两个数组dis[n]、pre[n]，数组dist记录从源点到其余各顶点当前的最短路径，初始时dis[i]=cost[v0][i];数组pre存储最短路径上终点v之前的那个顶点，初始时pre[i]=v0;具体过程是从v-s中找一个w,使dis[w]最小，将w加入到s中，然后以w作为新考虑的中间点，对s集合以外的每个顶点I,比较dis[w]+cost[w][j]与dis[i]的大小,若前者小于后者，表明加入了新的中间点w之后，从v0通过w到i的路径比原来的短，应该用它替换dis[i]的原值，使dis[i]始终保持目前为止最短的路径，若dis[w]+cost[w][j]floyd 弗洛伊德算法 求每一对顶点间的最短路径

基本思想

设立两个矩阵用来从图的带权邻接矩阵cost出发

设立两个矩阵引来记录各顶点间的路径和路径长度。矩阵path表示路径，矩阵D表示路径长度。

初始时，将cost复制到D中，即顶点vi到顶点vj的最短路径长度D[i][j]就是弧所对应的权值，将其记为D（-1）,其数组元素不一定是vi到vj的最短路径，要想求得最短路径，还需进行n次试探。

在矩阵D（-1）的基础上，对于要从顶点vi到vj的最短路径，首先考虑让路径经过顶点vo，比较和的路径长度，取其短者为当前求得的最短路径。对每一对顶点都做这样的试探，可求得矩阵D0。然后在D0的基础上，让路径通过v1，得到新的矩阵D1.以此类推，一般的，如果顶点vi到vj的路径经过顶点vk时的路径缩短，则修改Dk[i][j]=D(k-1)[i][k]+D(k-1)[k][j]，所以D(k)[i][j]就是当前求得的从顶点vi到vj的最短路径，且其路径上的顶点，除了源点和终点外，序号都不大于k。这样经过n次试探，最后求得的矩阵D（n-1）就一定是各顶点间的最短路径。

floydputpath 弗洛伊德算法floyd函数中用到的函数

矩形path是用来存储最短路径上的顶点信息的。矩阵path初始时都赋值为-1，表示vi到vj的最短路径是直接可达的，中间不需经过其他顶点。以后，当考虑路径经过某个顶点vk时，如果使路径更短，在修改D(k-1)[i][j]的同时修改path[i][j]为k，即path[i][j]中存放的是从vi到vj路径上所经过的某个顶点(若path[i][j]!=-1)。经过n次探查后，path[i][j]=k,即从vi到vj的最短路径经过顶点vk，该路径上还有哪些顶点呢，需要去查看path[i][j],以次类推，直到所查元素为-1为止。

prim 普里姆算法 最小生成树算法，比如要在n个城市间建立通信网，则连接n个城市需要n-1条线路，如何在最节省经费的情况下建立这个通信网？

基本思想：假设G=(V,E)是连通网，T=(U,TE)为欲构造的最小生成树

（1） 初始时令U={1}(即构造最小生成树时，从顶点1出发)，TE=空

（2） 从所有u属于U,v属于V-U的边中，选取具有最小权值的边(u,v)，将顶点v

加入集合U中，将(u,v)加入集合TE中。

（3） 重复(2)，直到U=V为止。

AOV拓扑排序的算法：

（1）：从Aov网中选择一个入度为0的顶点，并且输出它

（2）：从Aov网中删去该顶点和该顶点发出的全部有向边。

（3）：重复（1）和（2）知道找不到入度为0的顶点。

此时，若网中仍有定点没有输出，则说明AOV网中有环路。为实现拓扑排序算法，我们采用邻接链表作为AOV网的存储结构，在一维数组中增设一个入度域id，以存放各个顶点当前的入度值。算法中设置一个栈，用来存储入度为0的顶点。拓扑排序算法的步骤为：

（1）将id为0的顶点入栈。

（2）从栈中弹出栈顶元素并输出，并把该顶点发出的所有有向边删去，即把他的各个邻接顶点的入度减1.

（3）将新的id为0的顶点入栈。

（4）重复（2）（3），直到栈空为止。此时若输出的顶点数小于n，则输出“有回路”；否则拓扑排序正常结束。

从上面的步骤可以看出，栈在这里的作用只是起到一个保存当前入度为0的顶点，并使之处理有序。这种有序可以后进先出，也可以是先进先出，故此也可用队列来辅助实现。