求一个有向图的所有拓扑序列

1月2日 · 2018年

求一个有向图的所有拓扑序列。

深搜+回溯。

/**
 * 输出所有的拓扑序列,利用深搜+回溯
 * @param depth 当前已经在拓扑序列中的元素个数
 */
void dfs(int depth) {
    // 如果深度大于n,说明找齐了n个元素,可以输出
    if (depth>n) {
        printf("Output topol order [%d]: \n",++counter);
        for (int i=1; i<=n; ++i) { // 打印结果
            printf("%3d",tpv[i]);
        }
        printf("\n");
    } else {
        int i;
        for (i=1; i<=n; ++i) {
            // 如果第i个点入度为0,且没有访问过,就访问这个点
            if (ch[i].count==0 && ch[i].visited ==0) {
                VL_NODE * t = ch[i].head;
                while (t!=NULL) {
                    int k=t->ver;
                    --ch[k].count;
                    t=t->link;
                }
                ch[i].visited = 1;
                tpv[depth]=i;
                dfs(depth+1);

                // 下面开始回溯
                t = ch[i].head;
                while (t!=NULL) {
                    int k = t->ver;
                    ++ch[k].count;
                    t=t->link;
                }
                ch[i].visited = 0;
            }
        }
    }
}
4 条回应
验证码
输入运算符及数字使等式成立
{{comment.validate_num1}} = {{comment.validate_num2}}
点赞确定
退出登录?
取消 确定
  1. jxtxzzw2018-1-2 · 23:54

    评论支持Markdown

    System.out.println("Hello");
    • 陆 轩韬2018-1-23 · 21:21

      看文章竟然要消耗积分了

      • jxtxzzw2018-1-28 · 22:09

        是的,并且今后用户中心会提供更多功能。(虽然我不确定自己能不能搞得出来)

    • 陆 轩韬2018-1-23 · 21:22

      竟然还要等待管理员审核