Deletion order

问题描述

　　给定一个连通的图，确定一个删除节点的顺序，使得每次删除节点之后图的剩余部分依然是连通的。要求算法的时间复杂度是O(V + E)。

 

分析

　　这个问题粗看起来比较复杂。因为对于一个图来说，假设我们要删除一个节点，那么它所对应的边都要被删掉。光去遍历所有的节点找到所有包含某个要删除节点的边都要费很大的劲。所以不能单纯的用一个个查找然后删除的方法。

　　我们来看这个问题的要求，既然是希望删除了某个节点之后保证图还是连通的，我们在当前要删除的节点就可能是图中间某个独立的边上的节点，或者是一个环上面的节点。因为删除了这个节点之后，并不会破坏图的连通性。但是这个节点不能在图的bridge上。因为图的桥边表示一旦它被删除就将使得图被划分成两个独立的部分。只是说，在图里面去专门查找和判断这些边或者点的过程还是很复杂。似乎也没有什么具体可行的办法。

　　看来上述的两个思路都不可行，尤其是在要求时间复杂度为O(V+E)的情况下。这里，可能需要一点联想的应用了。在一些问题的场景里，我们经常看到一些问题的依赖关系图。比如说，我们要做事情a，那么就需要首先完成事情b，而同时要完成事情b，又需要若干其他的事情完成...这样就构成了一个依赖关系图。一个典型的依赖图如下：

 

　　在上述图中，我们可以看到，虽然这种依赖关系构成了一个有向图，但是有这么一个有趣的特性。每个元素和它所依赖的元素构成了一个边。而对于最终那个不依赖于任何元素的节点，它就是那个我们可以删除的节点。为什么呢？因为它之前的所有边都是由一个节点扩展来的，那么它把它删除之后，它之前的所有节点依然是连通的。嗯，在这一步我们似乎找到了一个突破口。 

　　可是问题的要求是找到一个删除所有元素的顺序。那么顺着前面的推导来看，当我们删除了这个节点之后。和它直接相连的那些依赖节点里也可能出现一个和最终节点一样的状态，它没有别的依赖了。也就是说，它也可以符合我们之前可以删除的节点的条件了。只是这次符合这个条件的节点还不止一个。想上图中，如果我们删除了节点f之后，节点g1, g2都可以删除。这样类推，我们就可以得到一个符合问题描述里条件的元素删除序列了。

　　在这里，我们得到的办法是基于一个依赖关系图得到的。对于一个普通的连通无向图来说，有没有可以同样运用的地方呢？对于依赖关系图来说，它可以说是一个有向图，节点和节点之间有依赖关系才构成这个图。而对于无向图来说，节点和一些节点之间有一个连通关系。如果我们把这些连通关系也看成是一个依赖关系的话，这样不也就构成了一个类似的关系了吗？对于某个给定的节点来说，它有若干个和它直接连通的节点。如果我们让它按照某种方式去遍历去访问，它就相当于一个类似的依赖关系构造。而对图的常用遍历方式有广度优先遍历和深度优先遍历。在任何一个遍历的过程中，最后被访问到的节点可以说是可以最先删除的。因为它之前的所有的节点都是连通的。

　　讨论到这里，我们就发现了原来这个问题的本质就是找到图的任何一种遍历的方式，但是将它访问的元素按照遍历访问的顺序相反的过程输出。而我们常用的两种遍历方式分别是BFS和DFS，因此我们就有两种问题的解决方法。

 

DFS

　　我们先看深度优先遍历的过程该怎么取得这个序列。我们首先取一个节点进行遍历，在每次访问一个节点的时候，将它标记为已访问，这样剩下的节点里继续递归的去访问直到某个节点它周边所有的节点都已经被访问过。那么从这个节点这里就要返回了。这个节点就是一个我们可以优先删除的对象。

 

public class DepthFirstPaths {
    private boolean[] marked;
    private int s;
    private LinkedList<Integer> accessPath;

    public DepthFirstPaths(Graph g, int s) {
        marked = new boolean[g.vertices()];
        this.s = s;
        this.accessPath = new LinkedList<>();
        dfs(g, s);
    }

    private void dfs(Graph g, int v) {
        marked[v] = true;
        accessPath.add(v);
        for(int w : g.adj())
            if(!marked[w]) {
                edgeTo[w] = v;
                dfs(g, w);
            }
    }

    private void dfs(Graph g, int v) {
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(v);
        marked[v] = true;
        accessPath.add(v);
        while(!stack.isEmpty()) {
            int u = stack.pop();
            for(int w : g.adj(u)) {
                if(!marked[w]) {
                    marked[w] = true;
                    accessPath.add(w);
                    stack.push(w);
                }
            }
        }
    }
    
    public List<Integer> accessSequence() {
        Collections.reverse(accessPath);
        return accessPath;
    }
}

　　在上述代码实现里，我们采用了递归和非递归两种实现。基本的思路是每次我们访问某个节点的时候，需要将该节点对应的位置marked[v] 设置为true。这个时候我们将该元素加入到一个列表中。在访问结束后，将列表倒置一下就得到期望的结果。

 

BFS

　　广度优先遍历的思路类似，我们每次访问的时候需要注意设置元素访问标记，并将元素加入到列表中。详细实现代码如下：

public class BreadthFirstPaths {
    private boolean[] marked;
    private LinkedList<Integer> accessPath;
    private int s;

    public BreadthFirstPaths(Graph g, int s) {
        this.marked = new boolean[g.vertices()];
        this.accessPath = new LinkedList<>();
        this.s = s;
        bfs(g, s);
    }

    private void bfs(Graph g, int s) {
        Queue<Integer> queue = new LinkedList<>();
        marked[s] = true;
        queue.add(s);
        accessPath.add(s);
        while(!queue.isEmpty()) {
            int v = queue.remove();
            for(int w : g.adj(v))
                if(!marked[w]) {
                    accessPath.add(w);
                    marked[w] = true;
                    queue.add(w);
                }
        }
    }

    public List<Integer> accessSequence() {
        Collections.reverse(accessPath);
        return accessPath;
    }
}

 

总结

　　深度优先或者广度优先遍历图的过程相对来说对于大家都很常见。它们其实就是一种对图遍历访问的一种策略。而不管用哪种策略，它从某个节点延伸出来所覆盖的节点是和之前的子图连通的。因此，如果我们按照遍历访问的顺序从后往前的保存元素，得到的就是一个符合问题描述中的序列了。这个序列和依赖关系图也有很密切的关系。

 

参考材料

Algorithms