转置图

Question

如何在java中编写程序来查找图G的转置,其中程序的输入和输出表示为邻接列表结构.例如:

输入:1> 2> 3> 4> 1

输出:1> 4> 3> 2>

Answer 1

假设给定一个图形G,并且顶点V是Vertices(G),G[V]则是邻接列表V.

在伪代码中:

FUNCTION transpose(Graph G) : Graph
   INIT Graph GT

   FOR EVERY Vertex U IN Vertices(G) DO
      FOR EVERY Vertex V IN G[U] DO
          append(GT[V], U)

   RETURN GT

这是O(|V|+|E|).

Java实现

以下实现紧跟伪代码.唯一补充的是null检查append.顶点标签是String,并且图表表示为aMap<String,List<String>>

import java.util.*;
public class Transpose {
    public static void main(String[] args) {
        Map<String,List<String>> g = new HashMap<String,List<String>>();
        g.put("A", Arrays.asList("B", "C"));
        g.put("B", Arrays.asList("A", "D"));
        g.put("C", Arrays.asList("D"));

        System.out.println(g);
        // prints "{A=[B, C], B=[A, D], C=[D]}"
        //
        // .--- A <--> B --> D <--.
        // |                      |
        // '---------> C ---------'

        Map<String,List<String>> gT = new HashMap<String,List<String>>();
        for (String u : g.keySet()) {
            for (String v : g.get(u)) {
                List<String> gTv = gT.get(v);
                if (gTv == null) {
                    gT.put(v, gTv = new ArrayList<String>());
                }
                gTv.add(u);
            }
        }
        System.out.println(gT);
        // prints "{D=[B, C], A=[B], B=[A], C=[A]}"
        //
        // .--> A <--> B <-- D ---.
        // |                      |
        // '---------- C <--------'     
    }
}

警告:这个核心算法不保留顶点既不是入境边界也不是出界边缘,但这只需要一个简单的处理.