深搜广搜遍历图

今天学习了一下如何用深搜和广搜遍历图。

下面是广度优先搜索

#include <iostream>
using namespace std;
int main(){//广度优先搜索
    int i,j,n,m,a,b,cur,book[101] = {0},e[101][101];
    int que[10001],head,tail;
    scanf("%d %d",&n,&m);
    for(i = 1;i <= n;i++)
        for(j = 1;j <= n;j++){
            if(i == j) e[i][j] = 0;//对角线赋值为0
            else e[i][j] = 9999999;//定义9999999为∞
        }
    for(i = 1;i <= m;i++){
        scanf("%d %d",&a,&b);
        e[a][b] = 1;
        e[b][a] = 1;//无向图双向赋值
    }
    head = 1;
    tail = 1;
    que[tail] = 1;
    tail++;
    book[1] = 1;
    while(head < tail && tail <= n){
        cur = que[head];
        for(i = 1;i <= n;i++){
            if(e[cur][i] == 1 && book[i] == 0){
                que[tail] = i;
                tail++;
                book[i] = 1;
            }
            if(tail > n) break;
        }
        head++;
    }
    for(i = 1;i < tail;i++)
        printf("%d ",que[i]);

}

运行结果如下：

深度优先搜索

#include<iostream>
#include<algorithm>
using namespace std;
int book[101],sum,n,e[101][101];
void dfs(int cur){
    int i;
    printf("%d ",cur);
    sum++;
    if(sum == n) return ;//访问所有节点
    for(i = 1;i <= n;i++){
        if(e[cur][i] == 1&& book[i] == 0){
            book[i] = 1;
            dfs(i);
        }
    }
    return ;

}
int main(){
    int i,j,m,a,b;
    scanf("%d %d",&n,&m);
    for(i = 1;i <= n;i++)
        for(j = 1;j <= n;j++){
            if(i == j) e[i][j] = 0;
            else e[i][j] = 9999999;
        }

    for(i = 1;i <= m;i++){
        scanf("%d %d",&a,&b);
        e[a][b] = 1;
        e[b][a] = 1;
    }
    book[1] = 1;
    dfs(1);
    return 0;
}

运行结果如下：