如何将有向图转为无向图？修改addEdge方法实现双向邻接

要把你的图改成无向图，只需要修改Node类里的addEdge方法，在添加目标节点到当前节点邻接表的同时，把当前节点也加入目标节点的邻接表就行。

基础修改版本 #

直接修改addEdge方法，添加双向关联：

public void addEdge(Node node) {
    edge.add(node);
    // 把当前节点加入目标节点的邻接表，实现双向边
    node.edge.add(this);
}

不过这里有个小问题：如果重复调用n1.addEdge(n2)，会导致两边的邻接表都重复添加节点。如果需要避免重复，可以加个存在性检查：

带去重的优化版本 #

public void addEdge(Node node) {
    // 检查当前节点的邻接表是否已有目标节点，没有才添加
    if (!edge.contains(node)) {
        edge.add(node);
        // 同样检查目标节点的邻接表是否已有当前节点，避免重复添加
        if (!node.edge.contains(this)) {
            node.edge.add(this);
        }
    }
}

完整修改后的代码 #

public class Main {

    public static void main(String[] args) {

        Graph g = new Graph();
        Node n1 = new Node("A");
        Node n2 = new Node("B");
        Node n3 = new Node("C");
        Node n4 = new Node("D");
        n1.addEdge(n2);
        n2.addEdge(n3);
        n3.addEdge(n4);
        n4.addEdge(n1);

    }
}

class Node{
    String node;
    boolean isVisited;
    LinkedList<Node> edge;

    Node(String node){
        this.node = node;
        edge = new LinkedList<>();
    }

    public void addEdge(Node node){
        // 带去重的双向边添加逻辑
        if (!edge.contains(node)) {
            edge.add(node);
            if (!node.edge.contains(this)) {
                node.edge.add(this);
            }
        }
    }

    public LinkedList<Node> getEdge(){
        return edge;
    }
}

class Graph {
    // 可根据需求补充节点管理、图遍历等逻辑
}

这样修改后，每次调用addEdge都会同时在两个节点的邻接表里互相添加，实现无向图的特性。

内容的提问来源于stack exchange，提问作者mo_beezy