用深度优先搜索进行拓扑排序的疑问???
我是用邻接矩阵建的图,顶点是g->data[0]到g->data[(g->n)-1],顶点个数是g->n,若存在顶点i到j的有向边则g->edges[i][j]=1,否则等于0.dfstop(graph *g,int i)
{
int j;
int k=0;
visited[i]=1;
for(j=0;j<g->n;j++)
{
if(!visited[j]&&g->edges[i][j]==1)
{
dfstop(g,j);
}
}
int k=0;
top[k++]=g->data[j-1];
}
我做的代码top[ ]中只top[0]存储了深度优先搜索的最后的一个顶点,我们老师说的算法是用回溯将深度优先搜索最后的一个顶点存储在top[0],然后回溯到倒数第二个存储到top[1]……继续回溯到第一个顶点,最后反向输出top[ ]即是拓扑排序的结果,但那个回溯的算法不知道该怎么写???
我在<<算法导论>>里看到的算法的是:
procedure Topological_Sort(G);
begin
1.调用DFS(G)计算每个顶点的完成时间f[v];
2.当每个顶点完成后，把它插入链表前端;
3.返回由顶点组成的链表;
end;
但这个算法里的f[v]我总是编得总有问题,总是有些特例运行的结果不对
希望各位高手能指导一下上面两种算法该怎么实现!!!!
