MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
利用宽度优先搜索  和  深度优先搜索来遍历图

矩阵存储bfs

#include <stdio.h>
#include 
<string.h>
#include 
<queue>
using namespace std;
queue 
<int> qu, qq;
int map[100][100], m, n, judge[100], path[100];
void bfs(){//和导论上的染色的方法差不多,judge[0] == 0 时候代表白色节点   在队列里面的节点是灰色的 出队列的是黑色的。
    int w, s,t,i, j;
    
while(true){
        s 
= qu.size();
        
if(!s)return;
        
while(s--){
            t 
= qu.front();
            
for(i = 0; i < n; i++){
                
if(map[t][i] && !judge[i]){
                    judge[i] 
= true;
                    qu.push(i);
                    path[i] 
= t;//记录宽度优先搜索树中的当前节点的父亲
                    
//printf("path[%d] = %d\n", i, t);
                }
            }
            qu.pop();
        }
    }
}
void printpath(int n){ //递归的输出路径
    if(path[n] == -1)printf("%d ", n);
    
else{
        printpath(path[n]);
        printf(
"%d ", n);
    }
}
int main(){
    freopen(
"bfs.in""r", stdin);
    freopen(
"bfs.out""w", stdout);
    
int i, j, u, v;
    
while(scanf("%d%d"&n, &m) != -1){
        memset(judge, 
0sizeof(judge));
        
for(i = 0; i < m; i++){
            scanf(
"%d%d"&u, &v);
            map[u][v] 
= map[v][u] = 1;
        }
        judge[
0= true;qu = qq;
        qu.push(
0);memset(path, -1sizeof(path));
        bfs();
        
for(i = 1; i < n; i++){
            printf(
"from 0 to %d : ", i);
            printpath(i);puts(
"");
        }
    }
    
return 0;
}


 链表存储bfs


#include <stdio.h>
#include 
<string.h>
#include 
<queue>
using namespace std;
queue
<int> qu, qq;
struct e{
    
int v;
    e
* next;
};
e
* edge[100];int m, n, judge[100], path[100];
void bfs(){
    
int w, i, j, t, s;e* l;
    
while(true){
        s 
= qu.size();
        
if(!s)return;
        
while(s--){
            w 
= qu.front();
            l 
= edge[w];
            
while(l){
                t 
= l->v;
                
if(!judge[t]){
                    judge[t] 
= true;
                    qu.push(t);
                    path[t] 
= w;
                }
                l 
= l->next;
            }
            qu.pop();
        }
    }
}
void printpath(int x){
    
if(path[x] == -1)printf("%d ", x);
    
else{
        printpath(path[x]);
        printf(
" %d", x);
    }
}
int main(){  //个人不推荐动态开辟存储空间,建议静态。
    freopen("bfs_link.in""r", stdin);
    freopen(
"bfs_link.out""w", stdout);
    
int u, v, i, j;e* node;
    
while(scanf("%d%d"&n, &m) != -1){
        memset(judge, 
0sizeof(judge));
        memset(path, 
-1sizeof(path));
        
for(i = 0; i < m; i++){
            scanf(
"%d%d"&u, &v);
            node 
= new e;
            node
->= v;
            node
->next = edge[u];
            edge[u] 
= node;
            node 
= new e;
            node
->= u;
            node
->next = edge[v];
            edge[v] 
= node;
        }
        judge[
0= true;qu = qq;qu.push(0);
        bfs();
        
for(i = 1; i < n; i++){
            printf(
"path from 0 to %d : ", i);
            printpath(i);puts(
"");
        }
    }
    
return 0;
}


矩阵存储dfs

#include <stdio.h>
#include 
<string.h>
int map[100][100], m, n, d[100], f[100], time, path[100];
bool judge[100];
void dfs(int v){
    
int i;judge[v] = true;
    time
++;d[v] = time;//开始时间
    for(i = 0; i < n; i++){
        
if(map[v][i] && !judge[i]){
            path[i] 
= v;//记录深度优先搜索树中的父亲节点
            dfs(i);
        }
    }
    time
++;f[v] = time;//结束时间
}

void printpath(int v){
    
if(path[v] == -1)printf("%d ", v);
    
else{
        printpath(path[v]);
        printf(
" %d", v);
    }
}

int main(){
    freopen(
"dfs_m.in""r", stdin);
    freopen(
"dfs_m.out""w", stdout);
    
int i, j, u, v;
    
while(scanf("%d%d"&n, &m) != -1){
        memset(map, 
0sizeof(map));
        memset(judge, 
0sizeof(judge));
        memset(path, 
-1sizeof(path));
        
for(i = 0; i < m; i++){
            scanf(
"%d%d"&u, &v);
            map[u][v] 
= map[v][u] = true;
        }
        time 
= 0;dfs(0);
        
for(i = 0; i < n; i++){
            printf(
"d[%d] = %d   f[%d] = %d\n", i, d[i], i, f[i]);
        }
        
for(i = 1; i < n; i++){
            printf(
"path from 0 to %d : ");
            printpath(i);puts(
"");
        }
    }
    
return 0;
}


链表存储dfs
#include <stdio.h>
#include 
<string.h>
struct e{
    
int v;
    e
* next;
};
e
* link[100];e edge[10000];//静态的
int m, n, el, judge[100], d[100], f[100], time, path[100];
void dfs(int v){
    
int i, t;e* l;
    judge[v] 
= true;
    time
++;d[v] = time;
    l 
= link[v];
    
while(l){
        t 
= l->v;
        
if(!judge[t]){
            judge[t] 
= true;
            path[t] 
= v;
            dfs(t);
        }
        l 
= l->next;
    }
    time
++;f[v] = time;
}

void printpath(int v){
    
if(path[v] == -1)printf("%d", v);
    
else{
        printpath(path[v]);
        printf(
" %d", v);
    }
}

int main(){
    freopen(
"dfs_link.in""r", stdin);
    freopen(
"dfs_link.out""w", stdout);
    
int i, j, u, v;
    
while(scanf("%d%d"&n, &m) != -1){
        memset(judge, 
0sizeof(judge));
        memset(link, 
0sizeof(edge));
        memset(path, 
-1sizeof(path));
        
for(i = 0, el = 0; i < m; i++){
            scanf(
"%d%d"&u, &v);
            edge[el].v 
= v;
            edge[el].next 
= link[u];
            link[u] 
= &edge[el++];
            edge[el].v 
= u;
            edge[el].next 
= link[v];
            link[v] 
= &edge[el++];
        }time 
= 0;
        
for(i = 0; i < n; i++){
            
if(!judge[i])dfs(i);
        }
        
for(i = 0; i < n; i++){
            printf(
"d[%d] = %d  f[%d] = %d\n", i, d[i], i, f[i]);
        }
        
for(i = 1; i < n; i++){
            printf(
"path form 0 to %d : ", i);
            printpath(i);puts(
"");
        }
    }
    
return 0;
}



posted on 2009-10-06 23:19 memorygarden 阅读(827) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理