图这章内容读的好累 手写了很多草稿都没怎么弄明白,主要看得有点乱了(了。。。)


最小生成树

普里姆(Prim)算法
先将一个起点加入最小生成树,之后不断寻找与最小生成树相连的 权值最小的边,并将其加入最小生成树,直至所有顶点都在最小生成树中。

//看看代码的实现--思想
void Prim(邻接矩阵 G) {
    int min;  /*一个在循环顶点中保存最小权值的一个临时变量*/
    int i,j;   /*控制循环次数的变量*/
    int k;   /*一个保存  与当前顶点相邻的顶点 的最小权值的变量*/

    int xiabiao[G.size]  /*保存顶点的下标 >=g.size就行*/
    int quanzhi[G.size]  /*保存相关顶点间的权值*/

/*首先将第一个顶点加入最小树中*/
    quanzhi[0] = 0;  /*权值为0 表示该顶点 加入最小树*/
    xiabiao[0] = 0;  /*初始化第一个顶点的下标--因为G是一个矩阵(二维滴)*/

/*将与第一个顶点相连的其他顶点 的权值放入quanzhi组中(比较大小)*/
    for(i=1;i < G.size;i++) {
        quanzhi[i] = G.arc[0][i];  /*arc[][]为图G的邻接表权值*/
        xiaobiao[i] = 0;    /*表示当前只有0这个下标的顶点加入了最小树中*/
    }

/*比较与之相连的各顶点权值大小,选出下一个顶点*/
    for(i=1;i<G.size;i++) {
        min = 无穷大; /*先初始化一个数,让它和权值做比较*/
        j = 1;k = 0;  /*还记得k是做什么的吗 微笑脸 */

/*开始循环了yo--目的:找到quanzhi[j]中的最小值,把它的值保存在min中 并 把它的下标保存在k中*/
        while(j < G.size) {
            if(quanzhi[j] != 0 && quanzhi[j] < min) {  /*为什么要非零ya--因为为零表示已经加入了最小树了ya--已经加入就不用再比较了*/
                min = quanzhi[j];
                k = j;
            }
            j++;
        }
        printf("(%d,%d)",xiaobiao[k],k);  /*找都找出来了,就显示一下吧,不然人类看不到--记得xiaobiao初始化的时候都是零吗,现在得到的k肯定不为零--没错(%d,%d)表示的是一条边--起点到终点*/
       quanzhi[k] = 0; /*记得之前说过--权值为零表示将该定点加入最小树?好了,终于搞定一个点了xiabiao[0]喝完茶了,找到了0->k,轮到xiabiao[k]喝茶了*/ 

#把与顶点k相邻的顶点的权值加入quanzhi中比较--找到k的下一个最小权值
       for(j = 1;j<G.size;j++) {
           if(quanzhi[j]!=0 && G.arc[k][j] < quanzhi[j]){   /*还记得quanzhi[j]里面都有什么吗?--有与上一个顶点的相连的那些边的 权值*/
               quanzhi[j] = G.arc[k][j];
               xiabiao[j] = k;
           }
       }    

    }    /*好了,第一遍循环结束--开始第二遍循环(自己去慢慢推吧)*/
}
#问题(没想通):在最后那个循环G.arc[k][j] < quanzhi[j],如果G.arc[k][j]的值都是大于quanzhi[j]呢??
##问题解决:那些与0相连的顶点的权值可能会比k小,但是如果与k相连就肯定比0大--em意思大概就是"与顶点0相连的不一定与顶点k相连,不相连的权值在之前定义为无穷大"。
so只要找到那些与0不相连与k相连的顶点就肯定要加进quanzhi数组中 参与下次循环的比较。

克鲁斯卡尔(Kruskal)算法
直接在所有未选取的边中,找最小边(就需要一个边的数据结构--Edge),如果和已选取的边构成回路,则放弃,选取次小边。(与prim不同,prim直接将一个随机顶点加入最小树,然后把该顶点 周围 的权值最小边选出来,...)

/*对边组Edge结构的定义*/
typedef struct {
    int begin;  /*边的起点*/
    int end;   /*边的终点*/
    int weight;  /*边的权值*/
}Edge;
//看看代码的实现--思想--建议画一个简单的图做比较
void Kruskal(Edge中定义的边集 G) {
    int i;  /*定义循环每条边*/
    int n,m;  /*临时存储边的begin和end*/
    Edge edge[biansize];   /*定义图的边集--biansize表示边数*/
    int parent[G.size];   /*判断边与边是否形成回路--parent数组存放着对应边的终点*/

    /*G边集edge数组按权值小到大排好 */

/*连接权值小的边,放进parent数组就表示该边加入最小树 */    
    for(i=0;i<G.biansize;i++)  /*循环每一条边*/
        n = Find(parent,edge[i].begin);
        m = Find(parent,edge[i].end);
        if(n != m) {      /*如果n = m就说明选择的顶点形成了一条回路*/
            parent[n] = m;  /*比如1-->2这条边 则得到parent[1]=2*/
            print("(%d,%d) %d",edge[i].begin,edge[i].end,edge[i].weight);
        }
/*将边的起点和终点比较--主要判断是否存在回环(n=m)--如果存在回环,在Find方法中退回上一个顶点*/        
    }
}
int Find(int *parent,int f) {
    while(parent > 0) 
        f = parent[f];    
    return f;
}

最短路径

迪杰斯特拉(Dijkstra)
 检查与始点到终点中所有相连的顶点,计算权值大小,选择权值小的相连

顶点V0到其余顶点V的最短路径P[v]--(前驱顶点下标),带权长度D[v]

#define MAXVEX = 9  /*顶点数*/
#define INFINITY = 65535 
typedef int Patharc[MAXVEX ];  /*用于存储最短路径下标的数组--记录最短路径经过的顶点*/
typedef int ShortPathTable[MAXVEX ];  /*用于存储到各点最短路径的权值和*/

void ShortestPath(Graph G,int v0,Patharc *P,ShortPathTable *D) {
    int v,w,k,min;
    int final[MAXVEX];  /*取值为0和1--1表示取得当前顶点的最小路径;0表示未知路径*/

    for(v=0;v<G.size;v++) {  /*初始化*/
        final[v] = 0;
        (*D)[v] = G.arc[v0][v];   /*初始化与顶点相连之间的权值*/
        (*P)[v] = 0;
    }
    (*D)[v0] = 0;
    final[v0] = 1;

/*比较相连的权值,找到最小权值*/
    for(v=1;v<G.size;v++) {
        min = INFINITY;
        for(w=0;w<G.size;w++) {
            if(!final[w] && (*D)[w] < min) {
                k = w;
                min = (*D)[w];
            }
        }

        final[k] = 1;  /*起点与k之间连线为最小权值*/
        for(w=0;w<G.size;w++) {
            if(!final[w] && (min+G.arc[k][w]<(*D)[w])) {
/*min+G.arc[k][w]为 与k之前所有最短权值的和,找到与k相连的点的权值 存放在*D中(获取下一个顶点的权值的方法与Prim类似)*/
                (*D)[w] = min+G.arc[k][w];
                (*P)[w] = k;
            }
        }
    }
}

弗洛伊德(Floyd)


拓扑排序

拓扑排序算法

对一个有向无环的图进行拓扑排序,是将图中的所有顶点排成一条线性序列 使得图中的任意边的起点在线性序列中出现在边的终点v之前--称为AOV网 (顶点可以看做一个个活动--线性序列就是一个有序的活动)

实现步骤:
1.在有向图中选择一个没有前驱的顶点 输出
2.删除与这个顶点相连的所有边
3.重复直至输出所有顶点,如果当前图中不存在无前驱的顶点则说明这是一个环(一个判断图是否成环的方法)


关键路径

关键路劲算法
AOE网 :顶点表示事件,弧表示活动,弧上的权值表示活动持续的时间的有向图 特点只有一个起点(入度为0的顶点)和终点(出度为0的顶点)
关键路径 :在AOE网中从起点到终点的最长路径(最长指的是 路径的权值最大),如果这个活动的最早开工时间 = 最晚开工时间 该活动为关键活动

Ref:
http://blog.csdn.net/Ontheroad_/article/details/72739380
http://blog.csdn.net/qq_35644234
http://wiki.mbalib.com/wiki/%E5%85%B3%E9%94%AE%E8%B7%AF%E5%BE%84