Digraph.java

package com.aiddroid.algo;

import java.util.HashMap;
import java.util.HashSet;

/**
 * 有向图
 */
public class Digraph {

    // 节点数
    private int V = 0;

    // 边数
    private int E = 0;

    // 邻接表，存放边(节点间的连接关系)
    private HashMap<String, HashSet<String>> adj;

    /**
     * 构造函数
     */
    public Digraph() {
        this.adj = new HashMap<String, HashSet<String>>();
    }

    public int V() {
        return this.V;
    }

    public int E() {
        return this.E;
    }

    /**
     * 添加节点
     * @param from
     * @param to
     */
    public void addEdge(String from, String to) {
        // 如果添加边时节点不存在，则初始化节点
        if (!this.adj.keySet().contains(from)) {
            this.adj.put(from, new HashSet<String>());
            this.V++;
        }
        if (!this.adj.keySet().contains(to)) {
            this.adj.put(to, new HashSet<String>());
            this.V++;
        }
        
        HashSet<String> s = this.adj.get(from);
        s.add(to);
        this.adj.put(from, s);
        this.E++;
    }

    private Iterable<String> adj(String key) {
        return this.adj.get(key);
    }

    /**
     * 获取反转的有向图
     *
     * @return
     */
    public Digraph reverse() {
        Digraph R = new Digraph();
        for (String key : this.adj.keySet()) {
            for (String w : this.adj(key)) {
                R.addEdge(w, key);
            }
        }
        return R;
    }

    /**
     * 转化为doT图
     * @return 
     */
    public String toDoT() {
        String doT = "strict digraph G {\n";
        String nodes = "";
        String links = "";
        for (String key : this.adj.keySet()) {
            nodes += "\t\"%s\" [ label=\"%s\" ];\n".formatted(key, key);
            for (String to: this.adj(key)) {
                links += "\t\"%s\" -> \"%s\";\n".formatted(key, to);
            }
        }
        doT += nodes;
        doT += links;
        doT += "}";
        
        return doT;
    }
}


Application.java

package com.aiddroid.algo;

import java.util.List;

/**
 * 测试代码
 */
public class Application {

    public static void main(String[] args) {
        // 初始化有向图，并添加边      
        Digraph digraph = new Digraph();
        digraph.addEdge("中国", "广东");
        digraph.addEdge("广东", "广州");
        digraph.addEdge("广东", "深圳");
        
        digraph.addEdge("中国", "湖北");
        digraph.addEdge("湖北", "武汉");
        digraph.addEdge("武汉", "广州");
        
        digraph.addEdge("中国", "北京");
        digraph.addEdge("北京", "深圳");
        
        System.out.println(digraph.toDoT());
    }

}

输出结果（doT图）：

strict digraph G {
	"广州" [ label="广州" ];
	"广东" [ label="广东" ];
	"中国" [ label="中国" ];
	"湖北" [ label="湖北" ];
	"武汉" [ label="武汉" ];
	"深圳" [ label="深圳" ];
	"北京" [ label="北京" ];
	"广东" -> "广州";
	"广东" -> "深圳";
	"中国" -> "广东";
	"中国" -> "湖北";
	"中国" -> "北京";
	"湖北" -> "武汉";
	"武汉" -> "广州";
	"北京" -> "深圳";
}

doT渲染结果如下（https://dreampuf.github.io ）：

---

实际上，我们并不需要手工实现有向图，jgrapht库已经提供了很好的支持，在maven项目中直接引用就行(pom.xml)

        <dependency>
            <groupId>org.jgrapht</groupId>
            <artifactId>jgrapht-core</artifactId>
            <version>1.5.0</version>
        </dependency>
        
        <dependency>
            <groupId>org.jgrapht</groupId>
            <artifactId>jgrapht-io</artifactId>
            <version>1.5.0</version>
        </dependency>

jgrapht绘制有向图示例：

import java.io.Writer;
import java.io.StringWriter;

import org.jgrapht.*;
import org.jgrapht.graph.*;
import org.jgrapht.nio.*;
import org.jgrapht.nio.dot.*;

/**
 * 测试代码
 */
public class Application {

    public static void main(String[] args) {
        // 初始化有向图
        Graph<String, DefaultEdge> directedGraph =
            new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);

        // 构建有向图
        directedGraph.addVertex("中国");
        directedGraph.addEdge("中国", "北京");
        directedGraph.addEdge("中国", "深圳");

        renderDirectedGraph(directedGraph);
    }

    // 绘制doT图
    private void renderDirectedGraph(Graph<String, DefaultEdge> directedGraph) {
        DOTExporter<String, DefaultEdge> exporter = new DOTExporter<>(v -> {
            // 移除特殊字符
            return v.replaceAll("[^a-zA-Z0-9]", "_");
        });

        // 为节点添加标签
        exporter.setVertexAttributeProvider((v) -> {
            Map<String, Attribute> map = new LinkedHashMap<>();
            map.put("label", DefaultAttribute.createAttribute(v.toString()));
            return map;
        });

        Writer writer = new StringWriter();
        exporter.exportGraph(directedGraph, writer);
        
        // 输出doT图
        System.out.println(writer.toString());
    }
}