這次是自己仿寫的 圖的模板 而寫的拓撲排序
和其他用矩陣的稍有不同
//采用臨界表的形式 但是用數組來實現 其中要用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
付翔 閱讀(1744)
評論(0) 編輯 收藏 引用 所屬分類:
ACM 圖論