本篇内容介绍了“c++怎么实现拓扑排序”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
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
*/
}
“c++怎么实现拓扑排序”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/datacube/blog/719787