文档章节

拓扑排序?

datacube
 datacube
发布于 2016/07/28 21:28
字数 286
阅读 9
收藏 0

http://blog.csdn.net/pigli/article/details/5777048

package com.lifeibigdata.algorithms.google;

/**
 * Created by lifei on 16/5/23.
 */
import java.util.ArrayList;
import java.util.List;

/**
 * 此处的拓扑排序是通过DFS的f[]降序排列。
 * 另一种实现方法是不断拿走入度为0的点
 * @author xiazdong
 *
 */
public class TopologicalSort_Algorithm {
    private static final int WHITE = 0;
    private static final int GRAY = 1;
    private static final int BLACK = 2;
    private int color[];
    private int size;
    private int f[];
    private int time;
    private Adjacent_List G;			//邻接表
    private List<String> resultList;	//存储拓扑排序的值的序列
    public TopologicalSort_Algorithm(Adjacent_List G){
        this.G = G;
        size = G.getSize();
        color = new int[size];
        f = new int[size];
        time = 0;
        resultList = new ArrayList<String>();
        for(int i=0;i<color.length;i++)
            color[i] = WHITE;
    }

    public List<String> getResultList() {
        return resultList;
    }

    public String[] TopologicalSort(){
        DFS();
        return resultList.toArray(new String[0]);
    }
    public void DFS(){
        for(int i=0;i<size;i++){
            if(color[i]==WHITE){
                DFS_VISIT(i);
            }
        }
    }
    private void DFS_VISIT(int i) {
        color[i] = GRAY;
        time++;
        for(int j=0;j<G.getListByVertexIndex(i).size();j++){
            String value = G.getListByVertexIndex(i).get(j);
            int index = G.getVertexIndex(value);
            if(color[index]==WHITE){
                DFS_VISIT(index);
            }
        }
        time++;
        f[i] = time;
        resultList.add(0, G.getVertexValue(i));	//将f[i]值加入到队列的头部
        color[i] = BLACK;
    }

    public static void main(String[] args) throws Exception {

        Adjacent_List adjacent_list  = GraphFactory.getAdjacentListInstance("/Users/lifei/myproject/algorithms/input/topo_input.txt");

        TopologicalSort_Algorithm alg = new TopologicalSort_Algorithm(adjacent_list);
        String[]result = alg.TopologicalSort();
        for(String e:result) System.out.print(e+" ");
    }
    /**
     *
     3 3
     1 2
     2 3
     1 3
     */
}

© 著作权归作者所有

datacube
粉丝 9
博文 607
码字总数 152394
作品 0
海淀
程序员
私信 提问
拓扑排序(Topological Sorting)

一、什么是拓扑排序 在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该序列必须满足下面两个条件: 每个顶点出现且只出...

临江仙卜算子
2018/06/20
0
0
图应用之拓扑排序(Topological Sort)

这一篇写有向无环图及其它的应用: 清楚概念: 有向无环图(DAG):一个无环的有向图。通俗的讲就是从一个点沿着有向边出发,无论怎么遍历都不会回到出发点上。 有向无环图是描述一项工程或者...

临江仙卜算子
2018/06/20
144
0
有向图问题1--深度优先、广度优先遍历和拓扑排序

有向图基础 术语定义: 一个顶点的出度为由该顶点指出的边的总数 一个顶点的入度为指向该顶点的边的总数 一条有向边的第一个顶点称为它的头,第二个顶点称为它的尾 数据结构: 使用邻接表来表...

SuperHeroes
2017/12/20
407
0
hdu 1285 确定比赛名次 拓扑排序

Problem Description 有N个比赛队(1<=N<=500),编号依次为1,2,3,。。。。,N进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排名,但现在裁判委员会不能直接获得每个队的...

阿豪boy
2017/11/20
10
0
拓扑排序(Topological Sort)

Graph 拓扑排序(Topological Sort) 假设一个应用场景:你用 C 编写了一个爬虫工具,其中有很多自定义的库:、、、、、 等等,且这些文件没有其他自定义库的依赖;另外还有一些基于上述自定...

LexLuc
03/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

java通过ServerSocket与Socket实现通信

首先说一下ServerSocket与Socket. 1.ServerSocket ServerSocket是用来监听客户端Socket连接的类,如果没有连接会一直处于等待状态. ServetSocket有三个构造方法: (1) ServerSocket(int port);...

Blueeeeeee
今天
6
0
用 Sphinx 搭建博客时,如何自定义插件?

之前有不少同学看过我的个人博客(http://python-online.cn),也根据我写的教程完成了自己个人站点的搭建。 点此:使用 Python 30分钟 教你快速搭建一个博客 为防有的同学不清楚 Sphinx ,这...

王炳明
昨天
5
0
黑客之道-40本书籍助你快速入门黑客技术免费下载

场景 黑客是一个中文词语,皆源自英文hacker,随着灰鸽子的出现,灰鸽子成为了很多假借黑客名义控制他人电脑的黑客技术,于是出现了“骇客”与"黑客"分家。2012年电影频道节目中心出品的电影...

badaoliumang
昨天
15
0
很遗憾,没有一篇文章能讲清楚线程的生命周期!

(手机横屏看源码更方便) 注:java源码分析部分如无特殊说明均基于 java8 版本。 简介 大家都知道线程是有生命周期,但是彤哥可以认真负责地告诉你网上几乎没有一篇文章讲得是完全正确的。 ...

彤哥读源码
昨天
15
0
jquery--DOM操作基础

本文转载于:专业的前端网站➭jquery--DOM操作基础 元素的访问 元素属性操作 获取:attr(name);$("#my").attr("src"); 设置:attr(name,value);$("#myImg").attr("src","images/1.jpg"); ......

前端老手
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部