java - 转置图

Question

我如何用 java 编写程序来找到图 G 的转置，其中程序的输入和输出表示为邻接表结构。 例如:

input: 1>2>3>4>1

output: 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 , 并且图形表示为 Map<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 <--------'     
    }
}

警告:此核心算法不会保留既没有入站边也没有出站边的顶点，但这只需要一个简单的处理。