LaneBlog

蝼蚁虽小,也有梦想

PHP Socket服务 | PHP微信开发框架 | 开源博客

算法九:深度优先搜索和广度优先搜索来遍历图

Clicks: 37287 Date: 2014-11-14 18:25:34 Power By 李轩Lane

    

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

如下的图:

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

©2014 www.lanecn.com , All rights reserved. Power By Li Xuan.  京ICP备14005030号