带权的有向图G的邻接表

### 带权有向图 G 的邻接表表示法

带权有向图可以通过邻接表来高效地表示。对于每一个顶点，仅需记录其指向的其他顶点及其对应的权重即可。这种方式节省空间，在稀疏图中尤为明显。

#### 数据结构设计

为了实现这一点，通常会为每个节点维护一个链表，其中包含了该节点所指的所有其它节点的信息。具体来说：

- 使用数组 `vertices` 来保存所有的顶点对象；
- 每个顶点对象内部含有一个列表 `edges` ，用于存储由当前顶点出发到达的目标顶点以及相应的边权重；

class Vertex {
    String label; // 节点标签
    List<Edge> edges = new ArrayList<>(); // 边集
    
    public Vertex(String label){
        this.label = label;
    }
}

class Edge {
    int weight; // 边的权重
    Vertex targetVertex; // 目标顶点
    
    public Edge(Vertex v, int w){
        this.targetVertex = v;
        this.weight = w;
    }
}

上述代码片段展示了如何定义顶点和边的数据结构[^1]。

#### 创建并操作图形实例

下面是一个简单的例子，说明怎样构建这样的图表，并添加一些基本的操作函数，比如增加一条新的加权路径。

public class DirectedWeightedGraph {

    private final Map<String, Vertex> vertices;

    public DirectedWeightedGraph() {
        vertices = new HashMap<>();
    }

    /**
     * 添加新顶点到图中
     */
    public void addVertex(String vertexLabel) {
        if (!vertices.containsKey(vertexLabel)) {
            vertices.put(vertexLabel, new Vertex(vertexLabel));
        } else {
            System.out.println("Vertex " + vertexLabel + " already exists.");
        }
    }

    /**
     * 向两个已存在的顶点之间加入一条有权重的方向性边
     */
    public void addEdge(String fromLabel, String toLabel, int weight) {
        var startVertex = vertices.get(fromLabel);
        var endVertex = vertices.get(toLabel);

        if (startVertex != null && endVertex != null) {
            startVertex.edges.add(new Edge(endVertex, weight));
        } else {
            throw new IllegalArgumentException("One or both of the specified vertices do not exist");
        }
    }

    @Override
    public String toString(){
        StringBuilder sb=new StringBuilder();
        for(var entry : vertices.entrySet()){
            sb.append(entry.getKey()).append(": ");
            for(Edge e:entry.getValue().edges){
                sb.append(e.targetVertex.label).append("(").append(e.weight).append("), ");
            }
            sb.setLength(sb.length()-2); // Remove last ", "
            sb.append("\n");
        }
        return sb.toString();
    }
}

这段代码实现了带有方向性和权重特性的图模型，允许动态增删节点与连接关系。