Java数据结构之加权无向图的设计实现

前言

在计算机科学中，图（Graph）作为一种基本数据结构，被广泛应用于各种领域，如网络流、图像处理、计算机视觉等。本文将介绍加权无向图（Weighted Undirected Graph）的设计实现，涉及图的存储、添加边、获取特定节点的相邻节点、计算最短路径等。

设计实现

存储结构

加权无向图可以用一个邻接表数组存储，其中每个邻接表包含该节点相连的边和权值。每个节点的信息可以用一个 Map 存储，其中键为节点名称，值为相应节点的邻接表。

public class WeightedUndirectedGraph {
    private final Map<String, List<Edge>> graph = new HashMap<>();

    // add undirected edge to the graph
    public void addEdge(String node1, String node2, int weight) {
        addDirectedEdge(node1, node2, weight);
        addDirectedEdge(node2, node1, weight);
    }

    // add directed edge to the graph
    private void addDirectedEdge(String startNode, String endNode, int weight) {
        List<Edge> edges = graph.get(startNode);
        if (edges == null) {
            edges = new ArrayList<>();
            graph.put(startNode, edges);
        }
        edges.add(new Edge(startNode, endNode, weight));
    }
}

class Edge {
    String startNode;
    String endNode;
    int weight;

    Edge(String startNode, String endNode, int weight) {
        this.startNode = startNode;
        this.endNode = endNode;
        this.weight = weight;
    }
}

获取特定节点的相邻节点

通过节点名称从图中获取该节点的相邻节点，只需要在 Map 中查找相应的邻接表即可。

List<String> getNeighbors(String node) {
    List<Edge> edges = graph.get(node);
    if (edges == null) {
        return Collections.emptyList();
    }
    List<String> neighbors = new ArrayList<>();
    for (Edge edge : edges) {
        neighbors.add(edge.endNode);
    }
    return Collections.unmodifiableList(neighbors);
}

计算最短路径

实现最短路径算法，可以使用 Dijkstra 算法或 Bellman-Ford 算法。下面给出使用 Dijkstra 算法计算最短路径的代码示例。

Map<String, Integer> calculateShortestPath(String startNode) {
    Map<String, Integer> distances = new HashMap<>();
    for (String node : graph.keySet()) {
        distances.put(node, Integer.MAX_VALUE);
    }
    distances.put(startNode, 0);

    PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(n -> n.distance));
    queue.offer(new Node(startNode, 0));

    Set<String> visited = new HashSet<>();

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        if (visited.contains(node.name)) {
            continue;
        }
        visited.add(node.name);
        List<Edge> edges = graph.get(node.name);
        if (edges == null) {
            continue;
        }
        for (Edge edge : edges) {
            if (visited.contains(edge.endNode)) {
                continue;
            }
            int distance = distances.get(node.name) + edge.weight;
            if (distance < distances.get(edge.endNode)) {
                distances.put(edge.endNode, distance);
                queue.offer(new Node(edge.endNode, distance));
            }
        }
    }
    return Collections.unmodifiableMap(distances);
}

class Node {
    String name;
    int distance;

    Node(String name, int distance) {
        this.name = name;
        this.distance = distance;
    }
}

示例说明

添加边

使用 addEdge() 方法添加边，如下所示：

WeightedUndirectedGraph graph = new WeightedUndirectedGraph();
graph.addEdge("A", "B", 4);
graph.addEdge("A", "C", 2);
graph.addEdge("B", "C", 1);
graph.addEdge("B", "D", 5);
graph.addEdge("C", "D", 8);

计算最短路径

使用 calculateShortestPath() 方法计算两个节点之间的最短路径，例如从节点 "A" 到节点 "D" 的最短路径：

Map<String, Integer> shortestPath = graph.calculateShortestPath("A");
Integer distance = shortestPath.get("D"); // distance == 6

总结

本文介绍了加权无向图的设计实现，包括存储结构、获取相邻节点、计算最短路径等操作，并给出了相关代码实现。通过本文的学习，读者能够深入理解加权无向图的实现原理，为后续的算法实现奠定基础。