1 #include<cstdio>  2 #include<vector>  3 #include<cstring>  4 #include<queue>  5 #include<stack>  6 using namespace std;  7   8 const int maxn=1e3+10;  9  10 int n,m; 11  12 struct picture 13 { 14     int node[maxn]; 15     vector<int>edge[maxn]; 16     void addedge(int a,int b) //向图中加一条a到b的边 17     { 18         edge[a].push_back(b); 19     } 20 }; 21  22  23  24 void bfs(picture map,int start) //广搜遍历图 25 { 26     queue<int>ans,ha; 27     int vis[maxn]; 28     memset(vis,0,sizeof(vis)); 29     ha.push(start); 30     ans.push(start); 31     vis[start]=1; 32     while(!ha.empty()) //广度遍历 33     { 34         int point=ha.front(); 35         ha.pop(); 36         for(int i=0;i<map.edge[point].size();i++) 37         { //遍历point上的每一条边 38             int x=map.edge[point][i]; 39             if(!vis[x]) 40             { 41                 ha.push(x); 42                 ans.push(x); 43                 vis[x]=1; 44             } 45         } 46     } 47     while(!ans.empty()) 48     { 49         printf("%d ",ans.front()); 50         ans.pop(); 51     } 52     printf("\n"); 53 } 54  55 void dfs(picture map,int start) //深度遍历图 56 { 57     queue<int>ans; 58     stack<int>haha; 59     vector<int>vis[maxn]; 60     for(int i=1;i<=n;i++) //初始化邻接表vis 61     { 62         int _size=map.edge[i].size(); 63         while(_size--) 64         { 65             vis[i].push_back(0); 66         } 67     } 68     haha.push(start); 69     ans.push(start); 70     while(!haha.empty()) //深搜 71     { 72         int x=-1; 73         int point=haha.top(); 74         int _size=map.edge[point].size(); 75         for(int i=0;i<_size;i++) //遍历每一条边 76         { 77             int tmp=map.edge[point][i]; 78             if(!vis[point][i]) //如果point的第i条边没有被访问过 79             { 80                 vis[point][i]=1; 81                 x=tmp; 82                 ans.push(x); 83                 haha.push(x); 84                 break; 85             } 86         } 87         if(x==-1) //如果point的所有边都被访问过 88         { 89             haha.pop(); 90         } 91     } 92     while(!ans.empty()) 93     { 94         printf("%d ",ans.front()); 95         ans.pop(); 96     } 97     printf("\n"); 98 } 99 100 int main()101 {102     while(~scanf("%d%d",&n,&m)) //输入一个n个点m条边的图103     {104         picture map;105         for(int i=0; i<m; i++) //向图中加入m条边106         {107             int a,b;108             scanf("%d%d",&a,&b);109             map.addedge(a,b);110         }111         int start; 112         scanf("%d",&start); //输入源点113         printf("dfs:\n");114         dfs(map,start);115         printf("bfs:\n");116         bfs(map,start);117     }118     return 0;119 }120 /*121 122 7 6123 1 2124 1 3125 2 4126 2 5127 3 6128 3 7129 1130 131           1132        2    3133      4  5  6  7134 135 */