这次是自己仿写的 图的模板 而写的拓扑排序
和其他用矩阵的稍有不同
//采用临界表的形式 但是用数组来实现 其中要用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
付翔 阅读(1718)
评论(0) 编辑 收藏 引用 所属分类:
ACM 图论