付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0
这次是自己仿写的 图的模板 而写的拓扑排序

和其他用矩阵的稍有不同

//采用临界表的形式 但是用数组来实现 其中要用C++ 的队列stl 尽量使代码的可用度提高
// 网上大多采用 临接矩阵的方式来做的
# include<cstdio>
# include
<iostream>
# include
<queue>
# include
<vector>
using namespace std;
const int maxn = 510;
struct graph
{
    
int edge[maxn][maxn];//edge[i][j] 表示第i个节点 第 j+1个边 其值表示该边的顶点
    int outdegree[maxn +1];//  顶点的出度
    int nvert ;//节点数
    int nedge;// 边数  注意定点我们是从1 开始算 然后边数我们是从0 开始的
};
typedef 
struct graph GRAPH;

struct graph g;// 图的全局变量

void init_graph()
{
    
int i;
    g.nedge 
= 0;
    g.nvert 
= 0;
    
for (i = 1; i <=maxn ; i ++ ) g.outdegree[i] = 0;
}
void inert_graph(int x,int y,bool flag )
{
    
//if(g.outdegree[x] > maxn )//容错
    g.edge[x][g.outdegree[x]] = y;
    g.outdegree[x] 
++;//出度 + 1
    if (flag == false)  inert_graph(y,x,true);//如果是无向图 反向也要加
    else g.nedge ++;//边数 ++

}
int read_graph(bool flag) //flag 用来控制 是否是有向图
{
    
//这里可以根据实际情况添加代码
    int n,i;
    
int x,y;
    init_graph();
    
if (scanf("%d%d",&g.nvert,&n)==EOF)
        
return 0;
    
for (i =1; i <= n; i ++)
    {
        scanf(
"%d%d",&x,&y);
        inert_graph(x,y,
true);//是有向图
    }
    
return 1;
}

//拓扑排序  下面是top 排序所需要的东东
int sorted[maxn];
int indegree[maxn]; //计算入度
int visted[maxn];
void topsorted()
{
    queue
<int> zeroin;
    
int x,y;
    
int i,j;
    
//初试化 入度数组
    for (i = 1; i <= maxn ; i ++)  indegree[i] = 0;
    
//计算入度
    for (i = 1; i <= g.nvert ; i++ )
        
for (j = 0; j < g.outdegree[i]; j++// 所以这里我们是从 0 开始
            indegree[g.edge[i][j]] ++;

    
for(i = 1; i <= g.nvert ; i ++)
    {
    
//for (i = g.nvert; i >= 1 ; i --)
        if (indegree[i] == 0) zeroin.push(i);
    }
    j 
= 0;
    memset(visted,
0,sizeof(visted));
    
for(j = 1;j <= g.nvert;j++)//  因为题目的原因 放弃队列
    {
        
for(i = 1;i<=g.nvert;i++ )
        {
            
if(visted[i] == 0 && indegree[i] == 0)
            {
                sorted[j] 
= i,visted[i] = 1;
                
for(int k = 0;k< g.outdegree[i];k++)
                    indegree[g.edge[i][k]]
--;
                
break;
            }
        }
    }

    
//if(j != g.nvert) ;//表明只有 j个定点找到
}

void print_graph()
{
    
int i,j;
    
for (i = 1; i <= g.nvert; i ++)
    {
        printf(
"%d: ",i);
        
for (j = 0; j < g.nvert ; j ++)
            printf(
" %d",g.edge[i][j]);
        printf(
"\n");
    }
}
int main()
{
    freopen(
"in.txt","r",stdin);

    
while (read_graph(true)==1)
    {

        topsorted();
        
//print_graph();
        for (int i = 1; i <= g.nvert; i ++)
            printf(i
==1?"%d":" %d",sorted[i]);
        printf(
"\n");
    }
    
return 0;
}



posted on 2010-05-19 23:56 付翔 阅读(1684) 评论(0)  编辑 收藏 引用 所属分类: ACM 图论

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



<2022年8月>
31123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜