JAVA—咖啡馆

——欢迎访问rogerfan的博客,常来《JAVA——咖啡馆》坐坐,喝杯浓香的咖啡,彼此探讨一下JAVA技术,交流工作经验,分享JAVA带来的快乐!本网站部分转载文章,如果有版权问题请与我联系。

BlogJava 首页 新随笔 联系 聚合 管理
  447 Posts :: 145 Stories :: 368 Comments :: 0 Trackbacks

图-拓扑排序

当每个任务有前后置关系时,需要找到一种满足前后置关系的路线,将任务完成。

如果将每个任务看成一个节点,任务之间的前后置关系表示为有向图时,这种路线顺序叫做为图进行拓扑排序。也叫关键路径分析。

这里的图用邻接矩阵法表示,算法的关键是:

1 找到一个没有后继的顶点

2 在图中删除它,放入结果数组中

3 重复 步骤 1 ,步骤 2 直到图中没有多余的节点。

如果图中出现环装结构,则算法无法进行,因为此时任务之间循环成为前置。

关于邻接矩阵法请参见:Graph 图-邻接表法。

要注意的是:满足前后置关系的路径可能不止一条。这里仅仅得到其中的一条。

关键API:

   int noNext():返回没有后继的节点的下标。

   remove(int index):删除指定下标的节点,同时在邻接矩阵中删除相对应的行与列。

   main:提供简单的测试。

代码如下:

 

 1class Vertex {    //图中的节点
 2    private Object value;
 3    Vertex(Object value) {
 4        this.value = value;
 5    }

 6    Object value() return value; }
 7    @Override public String toString() return "" + value; }
 8}

 9
10class Topology {    //用邻接矩阵法表示的图
11    private Vertex[] vertexs;
12    private Object[][] adjMat;    //记载是否联通    
13    private int length = 0;
14    private static Object CONN = new Object();    //标致是否联通
15
16    Topology(int size) {
17        vertexs = new Vertex[size];
18        adjMat = new Object[size][size];
19    }

20
21    void add(Object value) {
22        assert length <= vertexs.length;
23        vertexs[length++= new Vertex(value);
24    }

25
26    void connect(int from, int to) {
27        assert from < length;
28        assert to < length;
29        adjMat[from][to] = CONN;    //标志联通
30    }

31
32    void remove(int index) {    //移除指定的顶点
33        remove(vertexs,index);    //在顶点数组中删除指定位置的下标
34        for(Object[] bs: adjMat) remove(bs,index);    //邻接矩阵中删除指定的列
35        remove(adjMat,index);    //在邻接矩阵中删除指定的行
36        length--;
37    }

38
39    private void remove(Object[] a, int index) {    //在数组中移除指定的元素,后面的元素补上空位
40        for(int i=index; i<length-1; i++) a[i] = a[i+1];
41    }

42
43    int noNext() {    //寻找没有后继的节点
44        int result = -1;
45OUT:
46        for(int i=0; i<length; i++{
47            for(int j=0; j<length; j++{
48                if(adjMat[i][j] == CONN)continue OUT;    //如果有后继则从外循环继续寻找
49            }

50            return i;    //如果没有与任何节点相连,则返回该节点下标
51        }

52        return -1;    //否则返回-1
53    }

54
55    Object[] topo() {
56        Object[] result = new Object[length];    //准备结果数组
57        int index;
58        int pos = length;
59        while(length > 0{
60            index = noNext();    //找到第一个没有后继的节点    
61            assert index != -1 : "图中存在环";
62            result[--pos] = vertexs[index]; //放入结果中
63            remove(index);    //从图中把它删除
64        }

65        return result;
66    }

67
68    public static void main(String[] args) {
69        Topology g = new Topology(20);
70        g.add('a');
71        g.add('b');
72        g.add('c');
73        g.add('d');
74        g.add('e');
75        g.add('f');
76        g.add('g');
77        g.add('h');
78
79        g.connect(0,3);
80        g.connect(0,4);
81        g.connect(1,4);
82        g.connect(2,5);
83        g.connect(3,6);
84        g.connect(4,6);
85        g.connect(5,7);
86        g.connect(6,7);
87
88        for(Object o: g.topo()) System.out.print(o + " ");
89        System.out.println();
90    }

91}
posted on 2008-05-28 15:57 rogerfan 阅读(1071) 评论(0)  编辑  收藏 所属分类: 【JAVA算法】

只有注册用户登录后才能发表评论。


网站导航: