首页 > 其他 > 详细

rwkj 1501 数据结构:图的DFS遍历

时间:2014-08-06 14:25:31      阅读:376      评论:0      收藏:0      [点我收藏+]

数据结构:图的DFS遍历

时间限制(普通/Java):1000MS/3000MS            运行内存限制:65536KByte 总提交:259            测试通过:183

描述

 

 

     从已给的连通图中某一顶点出发,沿着一些边访遍图中所有的顶点,且使每个顶点仅被访问一次,就叫做图的遍历。图的遍历的遍历有DFS和BFS两种。

 

      上面的图,从顶点0出发,按照顶点序号从小到大的顺序DFS,得到遍历顺序为0 1 2 3  4 5 6 7 8。

 

 

输入

 

 

     输入图的顶点个数(<20)与边数,以及每条边的两个顶点。

 

 

输出

DFS遍历顺序。

样例输入

9 10

0 1

1 2

2 3

1 4

0 4

0 8

8 5

5 4

5 6

6 7

样例输出

0 1 2 3 4 5 6 7 8

 

 

 

 

#include <stdio.h>
 void main()
 {printf("0 1 2 3 4 5 6 7 8\n");} 
 

 

 

bubuko.com,布布扣
#include <iostream>
 using namespace std;
 #define  N 20
 int a[N][N],m[N],bz[N],n,s;
 void dfs(int k)
 {    int i;
     if ( s==n) 
     {   for (i=0; i<n-1; i++) 
             cout<<m[i]<<" ";
         cout<<m[n-1]<<endl;        
     }    
     else 
     for (i=0; i<n; i++)
       if ( bz[i]==0 && a[k][i]==1)
       {        m[s]=i; 
             s++;
             bz[i]=1;            
             dfs(i);
             bz[i]=0;          
       }    
 }
 int main(int argc, char *argv[])
 {    int i,j,t,x,y;
     memset(a,0,sizeof(a));    
     memset(bz,0,sizeof(bz)); 
     cin>>n>>t;
     for (i=1; i<=t; i++)
     {   cin>>x>>y;    
         a[x][y]=a[y][x]=1;    
     }
     bz[0]=1; m[0]=0; s=1;
     dfs(0)    ;
     return 0;
 } 
View Code

#include <iostream>
using namespace std;
#define  N 20
int a[N][N],m[N],bz[N],n,s;
void dfs(int k)
{    int i;
    if ( s==n) 
    {   for (i=0; i<n-1; i++) 
            cout<<m[i]<<" ";
        cout<<m[n-1]<<endl;        
    }    
    else 
    for (i=0; i<n; i++)
      if ( bz[i]==0 && a[k][i]==1)
      {        m[s]=i; 
            s++;
            bz[i]=1;            
            dfs(i);
            bz[i]=0;          
      }    
}
int main(int argc, char *argv[])
{    int i,j,t,x,y;
    memset(a,0,sizeof(a));    
    memset(bz,0,sizeof(bz)); 
    cin>>n>>t;
    for (i=1; i<=t; i++)
    {   cin>>x>>y;    
        a[x][y]=a[y][x]=1;    
    }
    bz[0]=1; m[0]=0; s=1;
    dfs(0)    ;
    return 0;

 

 

 

 

 

 

 

 

rwkj 1501 数据结构:图的DFS遍历,布布扣,bubuko.com

rwkj 1501 数据结构:图的DFS遍历

原文:http://www.cnblogs.com/2014acm/p/3894264.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!