分类 灵魂思想 下的文章

    堆是一种特殊的完全二叉树,是树的一种常见的应用,最简单的便是解决将无序的数列从大到小排列或者从小到大排列。性能极佳。

    堆分两种,一种是最大堆,即所有的父节点都大于它的两个子节点。另一种是最小堆,即所有的父节点都小于它的两个子节点。

    如果一组数列,是无序的,要将它有序的排列,那么:

min = 9999;

for(i=0; i<n; i++){

    if(num[i] < min){

        min = num[i];

    }

}

    这是最简单也是最高效的算法。可是,如果现在要删除最小数,在数列中插入一个任意一个数,此时再求最小值呢?那么就要重复上面的操作。那么问题来了,如果这个动作要重复100亿次呢?此时,时间复杂度就要100亿×数列的长度。即O(num.count*100亿)。这是不科学的,这个时候,我们引入了堆。

    最小堆的根节点永远是最小值!此时我们删掉了最小值,也就是根节点,在根节点的位置插入一个任意值,这个时候这个树就不是堆了,我们要把根节点向下移动,找到他合适的位置,也就是他要比他父节点大,比他的根节点小。此时这个树又恢复成了堆。

    现在有如下堆:

无标题.jpg


    堆的黑色数组表示节点的编号,在圈圈里。红色数组表示这个节点的值。我们现在要从小到大排列一个数列。也就是对红色数组进行排序。

    1、1号节点是根节点,永远是最小值,这是最小堆的特性。反之最大堆的根节点是最大值。

    2、将1号节点的值改变为新插入的任意值。

    3、将新插入的值向下移动,使树恢复为最小堆。和它的左子节点还有右子节点比较,若大,则交换位置。如此反复,直到不能再交换位置了。

    使用最小堆来从小到大排列一个无序数列的全部代码如下,时间复杂度为O(NLogN):

#include <stdio.h>

//存放堆

int h[100];

//存储堆的元素个数

int n;

//交换元素

void swap(int x, int y){

    int t;

    t = h[x];

    h[x] = h[y];

    h[y] = t;

}

//向下调整

void siftdown(int i){

    int t, flag=0;

    //判断该点的做儿子是否存在

    while(i*2 <= n && flag == 0){

        //如果左儿子存在,则判断是否交换值

        if(h[i] > h[i*2])

            t = i * 2;

        else

            t = i;

        //右儿子是否存在

        if(i*2+1 <= n && h[t] > h[i*2+1]){

            t = i*2+1;

        }

        //如果需要交换则交换

        if( t!= i){

            swap(t, i);

            i = t;

        //如果不需要交换,则准备退出while

        }else{

            flag = 1;

        }

    }

}

//向上调整,本函数本次将不会用到。

void siftup(int i){

    int flag = 0;

    while(i != 1 && flag == 0){

        if(h[i] < h[i/2]){

            swap(i, i/2);

            i = i/2;

        }else{

            flag = 1;

        }

    }

}

//创建堆

void create(){

    int i;

    for(i=n/2; i>=1; i--){

        siftdown(i);

    }

}

//获取最小的元素

int getMin(){

    int t;

    //堆顶(根节点)为最小值

    t = h[1];

    //删除根节点,把堆的最后一个元素赋给根节点

    h[1] = h[n];

    n--;

    //把根节点向下移动,使堆恢复最小堆

    siftdown(1);

    return t;

}

int main(){

    int i, num;

    scanf("%d", &num);

    for(i=1; i<=num; i++){

        scanf("%d", &h[i]);

    }

    n = num;

    //创建堆

    create();

    //讲堆从小到大排列

    for(i=1; i<=num; i++){

        printf("%d ", getMin());

    }

    return 0;

}


输入:

14

99 5 36 7 22 17 46 12 2 19 25 28 1 92

//输出:

1 2 5 7 12 17 19 22 25 28 36 46 92 99


    若使用最大堆,根节点就是整个数列的最大值,那么将h[1]和h[n]交换位置,此时h[n]就是最大值,然后将h[1]向下移动已恢复新的堆。此时将堆的大小减一,重复上面的操作。时间复杂度将会从O(NLogN)降低到O(NLogK)

    完整代码如下:

#include <stdio.h>

//存放堆

int h[100];

//存储堆的元素个数

int n;

//交换元素

void swap(int x, int y){

    int t;

    t = h[x];

    h[x] = h[y];

    h[y] = t;

}

//向下调整

void siftdown(int i){

    int t, flag=0;

    //判断该点的做儿子是否存在

    while(i*2 <= n && flag == 0){

        //如果左儿子存在,则判断是否交换值

        if(h[i] < h[i*2])

            t = i * 2;

        else

            t = i;

        //右儿子是否存在

        if(i*2+1 <= n && h[t] < h[i*2+1]){

            t = i*2+1;

        }

        //如果需要交换则交换

        if( t!= i){

            swap(t, i);

            i = t;

        //如果不需要交换,则准备退出while

        }else{

            flag = 1;

        }

    }

}

//创建堆

void create(){

    int i;

    for(i=n/2; i>=1; i--){

        siftdown(i);

    }

}

//从小到大排序

int minToMaxSort(){

    while(n>1){

        swap(1, n);

        n--;

        siftdown(1);

    }

}

int main(){

    int i, num;

    scanf("%d", &num);

    for(i=1; i<=num; i++){

        scanf("%d", &h[i]);

    }

    n = num;

    //创建堆

    create();

    //排序

    minToMaxSort();

    for(i=1; i<=num; i++){

        printf("%d ", h[i]);

    }

    return 0;

}

输入:

14

99 5 36 7 22 17 46 12 2 19 25 28 1 92

//输出:

1 2 5 7 12 17 19 22 25 28 36 46 92 99

Ps:本算法参考《啊哈!算法》一书。

   什么是Bellman-Ford算法?Bellman-Ford算法是一种堪称完美的解决一个点到其他各点的最短路径的算法。Bellman-Ford算法的核心代码只有4行,可以解决负权边的问题。

    Bellman-Ford算法的核心代码只有四行,如下

for(k=1; k<=n-1; k++)

    for(i=1; i<=m; i++)

        if(dis[v[i]] > dis[u[i]] + w[i])

            dis[v[i]] = dis[u[i]] + w[i];

    Bellman-Ford算法的核心代码意思是:遍历每一个点,其中每一次遍历时,遍历所有的边,对每个边进行一次松弛操作。

    松弛什么?请点击查看。算法十一:Dijkstra算法 - 一个点到各个点的最短路径

    现在有如下图,共5个点5条边,边都是有向边,其中点1到点2的距离为负数。如下:

无标题.jpg


    为什么会进行n-1次的循环呢?因为在不包含负权回路的路径中,n个点最多有n-1条边。在负权边中,负权回路会使最短路径不断的变小,永无止境。

完整代码如下:

#include <stdio.h>

int main(){

    int dis[10], i, k, m, n, u[10], v[10], w[10];

    int maxValue = 9999;

    //源点为1

    int start = 1;

    //读入点的个数n,边的个数m

    scanf("%d %d", &n, &m);

    //读入边

    for(i=1; i<=m; i++){

        scanf("%d %d %d", &u[i], &v[i], &w[i]);

    }

    //初始化dis数组。dis数组表示源点到各个点的初始距离,初始化时都为无穷大

    for(i=0; i<=n; i++){

        dis[i] = maxValue;

    }

    //源点到源点的距离为0

    dis[start] = 0;

    //Bellman-Ford算法的核心语句

    for(k=1; k<=n-1; k++){

        for(i=1; i<=m; i++){

            if(dis[v[i]] > dis[u[i]] + w[i]){

                dis[v[i]] = dis[u[i]] + w[i];

            }

        }

    }

    for(i=1; i<=n; i++){

        printf("%d ", dis[i]);

    }

    return 0;

}

输入:

5 5

2 3 2

1 2 -3

1 5 5

4 5 2

3 4 3

//输出:

0 -3 -1 2 4

    Bellman-Ford算法的时间复杂对为O(MN)。

    我们可以更加完善上面的代码。比如我们已经知道了使用Bellman-Ford算法不能包含负权回路,那么我们需要检测图中是否包含负权回路:

sign = 0

for(i=1; i<=m; i++)

    if(dis[v[i]] > dis[u[i]] + w[i])

        flag = 1;

if(sign == 1)

    printf("此图有负权回路");

    另外,在n-1轮循环中,若n-3轮已经松弛完毕,那么n-2和n-1两次循环便毫无意义,因此增加判断,若第x轮dis数组已经不再发生变化了,则不在继续进行循环。

    新版的完整代码如下:

#include <stdio.h>

int main(){

    int dis[10], i, k, m, n, u[10], v[10], w[10], sign, check;

    int maxValue = 9999;

    //源点为1

    int start = 1;

    //读入点的个数n,边的个数m

    scanf("%d %d", &n, &m);

    //读入边

    for(i=1; i<=m; i++){

        scanf("%d %d %d", &u[i], &v[i], &w[i]);

    }

    //初始化dis数组。dis数组表示源点到各个点的初始距离,初始化时都为无穷大

    for(i=0; i<=n; i++){

        dis[i] = maxValue;

    }

    //源点到源点的距离为0

    dis[start] = 0;

    //Bellman-Ford算法的核心语句

    for(k=1; k<=n-1; k++){

        //本轮dis数组是否发生变化

        ckeck = 0;

        for(i=1; i<=m; i++){

            if(dis[v[i]] > dis[u[i]] + w[i]){

                dis[v[i]] = dis[u[i]] + w[i];

                check = 1;

            }

        }

        //本轮没有发生松弛,则不再继续进行了。

        if(ckeck == 0){

            break;

        }

    }

    sign = 0

    for(i=1; i<=m; i++)

        if(dis[v[i]] > dis[u[i]] + w[i])

            sign = 1;

    if(sign == 1){

        printf("此图有负权回路");

    }else{

        for(i=1; i<=n; i++){

            printf("%d ", dis[i]);

       }

    }

    return 0;

}



    在第每一轮循环中,其实只对上一次发生了松弛的边的相邻边判断是否需要松弛,因此,没有必要每次都进行m次循环(遍历所有的边判断是否需要松弛)。比如第一轮松弛了1->2和1->5,那么第二次仅仅判断2->3和5->4这两个边是否需要松弛,而不需要遍历所有的边。

    在这种情况下,我们引入队列,将需要松弛的点加入队列。每个点仅仅需要入队一次即可,因为入队多次是没有意义的。初始时我们将1号点(源点)加入队列。然后开始遍历队列,对队列中每个点的边进行松弛。队列为空时所得结果便是一个点到其他所有点的最短路径。这是对上述的Bellman-Ford算法一种极大的优化。当然,在最坏的情况下,和Bellman-Ford算法的时间复杂度是一样的,即O(MN)。此优化也可以解决负权边。

    完整代码如下:

#include <stdio.h>

int main(){

    int dis[10] = {0}, i, j, k, m, n, u[10], v[10], w[10];

    int book[10] = {0};

    //first数组和next数组用来建立领接表,即first记录一个边的开头,比如第2号边的开头是点a,那么first[a]=2,a开头的下一个边是第5号边,则next[5]=a,组成一个链表的形式

    int first[10], next[10];

    int queue[100] = {0}, head = 1, tail = 1;

    int maxValue = 9999;

    //源点为1

    int start = 1;

    //读入点的个数n,边的个数m

    scanf("%d %d", &n, &m);

    //初始化dis数组。dis数组表示源点到各个点的初始距离,初始化时都为无穷大

    //book用来标记那个点已经入队了,因为队列中同时出现同一个点多次是没有意义。

    //first用来标记第i条边的起点

    for(i=0; i<=n; i++){

        dis[i] = maxValue;

        book[i] = 0;

        first[i] = -1;

    }

    //源点到源点的距离为0

    dis[start] = 0;

    //读入边

    for(i=1; i<=m; i++){

        scanf("%d %d %d", &u[i], &v[i], &w[i]);

        //使用first和next两个数组建立领接表

        next[i] = first[u[i]];

        first[u[i]] = i;

    }

    //源点入队

    queue[tail] = start;

    tail++;

    //标记已经入队的点

    book[i] = start;

    while(head < tail){

        //当前需要处理的点,是队首的点,处理队首开头的所有边

        k = first[queue[head]];

        //扫描这个点开头的所有边

        while( k != -1){

            if(dis[v[k]] > dis[u[k]] + w[k]){

                dis[v[k]] = dis[u[k]] + w[k];

                if(book[v[k]] == 0){

                    queue[tail] = v[k];

                    tail++;

                    book[v[k]] = 1;

                }

            }

            k = next[k];

        }

        //这个点开头的所有边都处理完了,就出队

        book[queue[head]] = 0;

        head++;

    }

    for(i=1; i<=n; i++){

        printf("%d ", dis[i]);

    }

    getchar();getchar();

    return 0;

}

输入:

5 5

2 3 2

1 2 -3

1 5 5

4 5 2

3 4 3

//输出:

0 -3 -1 2 4

Ps:本算法参考《啊哈!算法》一书。

    Dijkstra算法是指定一个源点,求得这个源点到各个点的最短路径。Dijkstra算法通过不断的松弛边,每次更新相邻点的路径,使之两点之间的距离成为最短的路径。Dijkstra算法缺点是不能有负权边的值。

    松弛边:点A到点B的距离是10,点A到点C的距离是15,点B到点C的距离是3,那么点A到点C的最短距离就是13。此时15这个值将会被废弃,永不使用,以后谈论点A到点C的距离都是直接说13。这就是松弛边。

    现在有如下图,6个点,9条边,边是有方向的哦。


无标题.jpg


    Dijkstra算法的步骤,假设源点为点(1):

    1、先求得源点到各个点的距离。则数组为dis['1'=>0, '2'=>1, '3'=>12, '4'=>'∞', '5'=>'∞', '6'=>'∞'];并且用数组e[i][j]表示点i到点j的距离。

    2、将各个点分为2个部分,P部分是已知的点1到该点距离为最短路径的点的集合,此时P部分只有点1到点1的距离为0是已知的,点1到点2,点1到点3的距离是不是最短路径暂时不可是,所以他们不属于这部分。Q部分是未知的点1到该点距离为最短路径的点的集合。

    3、在集合Q中选择一个点,这个点距离源点(1)号点最近,即步骤一得出的dis数组中该key所对应的值最小,此时这个点为2号点,因为dis[2]最小,为1。则点1到点2的距离dis[2]是最短的路径,已经已知了,所以将(2)号点加入到集合P中。此时以(2)好点为源点,对所有的边松弛一次,看看有没有一个点X,可以使得点1到点2再到点X的距离小于点1到点X的距离,如果有,则点1到点X的最短路径就是点1到点2再到点X的值。即如果dis[3] > dis[2] + e[2][x],则dis[3] = dis[2] + e[2][x]。

    4、重复第三步,知道集合Q为空。


Dijkstra算法的代码如下:

#include <stdio.h>

int main(){

    int startPoint = 1;

    int limitValue = 999;

    int e[10][10], dis[10], book[10], i, j, m, n, point1, point2, length, u, v, min;

   //n是点数,m是边数

    scanf("%d %d", &n, &m);

   //如果i=j,就是自己到自己的距离,那么就是0,否则,就初始化非正无穷

    for(i=1; i<=n; i++){

        for(j=1; j<=n; j++){

            if(i==j)

                e[i][j] = 0;

            else

                e[i][j] = limitValue;

        }

    }

   //边的长度,即点到点的距离

    for(i=1; i<=m; i++){

        scanf("%d %d %d", &point1, &point2, &length);

        e[point1][point2] = length;

    }

   //初始化源点到各点的距离的数组,我们的源点为1

    for(i=1; i<=n; i++){

        dis[i] = e[startPoint][i];

    }

   //book数组用来标记那个点是已经走过了的。

    for(i=1; i<=n; i++){

        book[i] = 0;

    }

   //从源点开始

    book[startPoint] = 1;

   //以下就是Dijkstra算法的重点,是核心思想

    for(i=1; i<=n-1; i++){

       //找到离远点最近的点

        min = limitValue;

        for(j=1; j<=n; j++){

            if(book[j] == 0 && dis[j] < min){

                min = dis[j];

                u = j;

            }

        }

        book[u] = 1;

        for(v=1; v<=n; v++){

           //如果小于limitValue,则证明点u到点v是有路走的

            if(e[u][v] < limitValue){

                if(dis[v] > dis[u] + e[u][v]){

                    dis[v] = dis[u] + e[u][v];

                }

            }

        }

    }

    //输出

    for(i=0; i<=n; i++){

        printf("%d ", dis[i]);

    }

    return 0;

}


输入:

6 9

1 2 1

1 3 12

2 3 9

2 4 3

3 5 5

4 3 4

4 5 13

4 6 15

5 6 4

输出

0 1 8 4 13 17

这个输出便是点1到各个点的最短距离。


Ps:本算法参考《啊哈!算法》一书。

   任意两点最短路径被称为多源最短路径,即给定任意两个点,一个出发点,一个到达点,求这两个点的之间的最短路径,就是任意两点最短路径问题,多源最短路径,而Floyd-Warshall算法最简单,只有5行代码,即可解决这个问题。

    比如三个城市,城市1,城市2,城市3。从城市1到城市3需要10公里,从城市1到城市2需要3公里,从城市2到城市3需要4公里,如下图:

4F966EED-1AD1-4FD9-ABB4-0448137A13E4.png


那么从城市1到城市3,如何走更近?1到3是直达,但是却10公里,而1到2到3,虽然转一下,但是距离短了,只要7公里。

这就引出了我们的观念,一个点到另一个点要变短,就要引入第三个点,甚至第四个点,第五个点。


假设在map数组里存储了点i到点j的距离map[i][j],那么我们引入第三个点k,则如果点i到点j的距离比点i到点k加点k到点j,则点i到点j的最短距离是点i到点k加点k到点j。

即如果map[i][j]<map[i][k]+map[k][j],则map[i][j]=map[i][k]+map[k][j]


这就是Floyd-Warshall算法。核心代码如下:

//只能从k中转

    for(k=1; k<=cityCount; k++){

        //从i出发

        for(i=1; i<=cityCount; i++){

            //到j结束

            for(j=1; j<=cityCount; j++){

                if(map[i][j] > (map[i][k] + map[k][j])){

                    map[i][j] = map[i][k]+ map[k][j];

                }

            }

        }

    }

三个for循环,加一个if,加一个赋值,简简单单的五行代码,就实现了任意一个点到任意另一个点的最短距离。

显而易见,时间复杂度是O(n3).


完整代码如下

#include <stdio.h>

int map[11][11] = {{0}};

int book[11] = {0};

int main(){

    int i, j, k, cityCount, roadCount, length, x, y;

    scanf("%d %d", &cityCount, &roadCount);

    for(i=1; i<=cityCount; i++){

        for(j=1; j<=cityCount; j++){

            map[i][j] = 0;

        }

    }

    for(i=1; i<=roadCount; i++){

        scanf("%d %d %d", &x, &y, &length);

        map[x][y] = length;

    }

   //只能从k中转

    for(k=1; k<=cityCount; k++){

        //i出发

        for(i=1; i<=cityCount; i++){

            //j结束

            for(j=1; j<=cityCount; j++){

                if(map[i][j] == 0 || map[i][k] == 0 || map[k][j] == 0) continue;

                if(map[i][j] > (map[i][k] + map[k][j])){

                    map[i][j] = map[i][k]+ map[k][j];

                }

            }

        }

    }

   //现在的map里就是从一个点i到另一个点j的最短距离map[i][j]

    printf("点1到点5的最短路径是:%d", map[1][5]);

}


输入

5 8

1 2 3

1 3 2

1 5 10

2 3 1

3 5 3

3 4 5

4 5 1

2 4 8


输入,5

图的遍历,我们用深度优先搜索遍历图和广度优先搜索遍历图。最简单的一种图的遍历-穷举!

如下的图:

F1062065-133F-4EB8-AD78-3E7168FF00C7.png

点1和点2,3,5有边,点3和点5有边,点2和点4有边。mac画的好累。。没有鼠标。。


输入:第一行是点的总数和边的总数,下面几行都是那几个点有边。

        5 5

        1 2

        1 3

        1 5

        2 4

        3 5


深度优先搜索来遍历图,代码如下:

#include <stdio.h>

int a[101][101];

int book[101];

int m, n, sum=0;

void dfs(int node);

int main(){

    int i, j, x, y;

    scanf("%d %d", &m, &n);

    for(i=1; i<=n; i++){

        for(j=1; j<=n; j++){

            a[i][j] = 0;

        }

    }

    for(i=0; i<m; i++){

        scanf("%d %d", &x, &y);

        a[x][y] = 1;

        a[y][x] = 1;

    }

    book[1] = 1;

    dfs(1);

}

void dfs(int node){

    printf("%d ", node);

    sum++;

    if(sum == n){

        return;

    }

    int i = 0;

    for(i=1; i<=n; i++){

        if(book[i] != 0 || a[node][i] != 1) continue;

        book[i] = 1;

        dfs(i);

    }

}

输出:1,2,4,3,5



广度优先搜索来遍历图,代码如下:

输入:第一行是点的总数和边的总数,下面几行都是那几个点有边。


#include <stdio.h>

int a[101][101];

int book[101];

int m, n;

void dfs(int node);


int main(){

    int i, j, x, y;

    scanf("%d %d", &m, &n);

    for(i=1; i<=n; i++){

        for(j=1; j<=n; j++){

            a[i][j] = 0;

        }

    }

    for(i=0; i<m; i++){

        scanf("%d %d", &x, &y);

        a[x][y] = 1;

        a[y][x] = 1;

    }

    book[1] = 1;

   //广度优先搜索

    int head = 0, tail = 0;

    int queue[25];

    for(i=0; i<25; i++) queue[i] = 0;

    queue[tail] = 1;

    tail++;

    while(head<tail){

        printf("%d ", queue[head]);

        for(i=1; i<=n; i++){

            if(book[i] != 0 || a[queue[head]][i] != 1) continue;

            book[i] = 1;

            queue[tail] = i;

            tail++;

        }

        head++;

    }

}

输出:1,2,3,5,4