MemoryGarden's Blog

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

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
导论上的方法是dfs的方法,是dfs的一个应用,我以前些的是用栈来模拟dfs的。

这里只输出一种序列,当然是多种的,如果要全部的序列,那就只能dfs + 回溯来硬做了。

贴个代码  有错误请改正

栈模拟 :
#include <stdio.h>
#include 
<string.h>
#include 
<stack>
using namespace std;
stack
<int> st, ss;
int m, n, map[100][100], degree[100];
int main(){
    freopen(
"topsort.in""r", stdin);
    freopen(
"topsort.out""w", stdout);
    
int i, j,tn, u,t, v, out[100], s, outlen;
    
while(scanf("%d%d"&n, &m) != -1){
        memset(map, 
0sizeof(map));tn = outlen = 0;
        
for(i = 0; i < m; i++){
            scanf(
"%d%d"&u, &v);
            map[u][v] 
= 1;degree[v]++;
        }
        
for(i = 0; i < n; i++)if(!degree[i])st.push(i);
        
while(true){
            s 
= st.size();
            
if(!s)break;
            tn
++;t = st.top();st.pop();
            
out[outlen++= t;
            
for(i = 0; i < n; i++){
                
if(map[t][i] && !(--degree[i]))st.push(i);
            }
        }
        
if(tn != n)puts("have circle");
        
else{
            puts(
"after topsort : ");
            
for(i = 0; i < outlen; i++)printf("%d "out[i]);
            puts(
"");
        }
    }
    
return 0;
}
dfs
#include <stdio.h>
#include 
<string.h>

int n, m, map[100][100], judge[100], time, f[100];

void dfs(int v){
    
int i, t;
    judge[v] 
= true;
    
for(i = 0; i < n; i++){
        
if(map[v][i] && !judge[i]){
            judge[i] 
= true;
            dfs(i);
        }
    }
    time
++;f[v] = time;//完成时间
}

int main(){
    freopen(
"topsort_dfs.in""r", stdin);
    freopen(
"topsort_dfs.out""w", stdout);
    
int i, j, u, v, s[100];
    
while(scanf("%d%d"&n, &m) != -1){
        memset(map, 
0sizeof(map));
        memset(judge, 
0sizeof(judge));
        
for(i = 0; i < m; i++){
            scanf(
"%d%d"&u, &v);
            map[u][v] 
= true;
        }
        time 
= 0;
        
for(i = 0; i < n; i++)if(!judge[i])dfs(0);
        
for(i = 0; i < n; i++)s[f[i]] = i;//按完成时间的从达到小输出即可
        printf("one kind of topsort is : \n");
        
for(i = n; i > 0; i--)printf("%d", s[i]);
        puts(
"");
    }
    
return 0;
}


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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理