java - 如何递归获取图形中可以包含循环的所有连接节点？

Question

我尝试实现加权图。快完成了，但我面临一个问题，我无法正确收集图形的所有连接节点。例如我有以下图表:

  1  2  3  4  5  6
1 0  1  1  0  0  0
2 1  0  1  1  0  0
3 1  1  0  1  0  0
4 0  1  1  0  0  0
5 0  0  0  0  0  1
6 0  0  0  0  1  0

我想获得集合[[1,2,3,4],[5,6]]的结果集，如果没有循环，我的代码可以很好地工作，但如果有循环，我的代码就会进入无限循环。

节点类:

    public class Node<T> {

    private T content;

    private Set<Node<T>> neighbors;

    private boolean marked;

    public Node(T content) {
        super();
        Validate.notNull(content, "Value of vertex can't be null!");
        this.content = content;
        this.neighbors = new HashSet<Node<T>>();
    }

    public T getContent() {
        return content;
    }

    public void setContent(T content) {
        this.content = content;
    }

    public boolean hasNeighbors() {
        return !neighbors.isEmpty();
    }

    public void addNeighbor(Node<T> neighbor) {
        this.neighbors.add(neighbor);
    }

    public Set<Node<T>> getNeighbors() {
        return neighbors;
    }

    public void setNeighbors(Set<Node<T>> neighbors) {
        this.neighbors = neighbors;
    }

    public boolean isMarked() {
        return marked;
    }

    public void setMarked(boolean marked) {
        this.marked = marked;
    }

    public Set<Node<T>> getAllRelatedNeighbors() {
        Set<Node<T>> result = new HashSet<Node<T>>();
        result.add(this);

        if (neighbors.isEmpty()) {
            return result;
        }

        for (Node<T> neighbor : neighbors) {
            result.add(neighbor);
            for(Node<T> nestedNeighbor: neighbor.getNeighbors()){
                if(!nestedNeighbor.equals(this) ){
                    result.addAll(neighbor.getAllRelatedNeighbors());
                }
            }
        }
        return result;
    }

    @Override
    public String toString() {
        return "Vertex [content=" + content + ", marked=" + marked + "]";
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((content == null) ? 0 : content.hashCode());
        result = prime * result + (marked ? 1231 : 1237);
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Node other = (Node) obj;
        if (content == null) {
            if (other.content != null)
                return false;
        } else if (!content.equals(other.content))
            return false;
        if (marked != other.marked)
            return false;
        return true;
    }
}

public class Edge<T> {

    private Node<T> first;

    private Node<T> second;

    private int weight;

    public Edge(Node<T> first, Node<T> second, int weight) {
        this(first, second);
        this.weight = weight;
    }

    public Edge(Node<T> first, Node<T> second) {
        super();
        this.first = first;
        this.second = second;
        this.first.addNeighbor(second);
        this.second.addNeighbor(first);
    }

    public Node<T> getFirst() {
        return first;
    }

    public void setFirst(Node<T> first) {
        this.first = first;
    }

    public Node<T> getSecond() {
        return second;
    }

    public void setSecond(Node<T> second) {
        this.second = second;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Edge [first=" + first + ", second=" + second + ", weight="
                + weight + "]";
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((first == null) ? 0 : first.hashCode());
        result = prime * result + ((second == null) ? 0 : second.hashCode());
        result = prime * result + weight;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Edge other = (Edge) obj;
        if (first == null) {
            if (other.first != null)
                return false;
        } else if (!first.equals(other.first))
            return false;
        if (second == null) {
            if (other.second != null)
                return false;
        } else if (!second.equals(other.second))
            return false;
        if (weight != other.weight)
            return false;
        return true;
    }               
}

public class WeightedGraph<T> {

    private Set<Node<T>> nodes;

    private Set<Edge<T>> edges;

    public WeightedGraph(Collection<T> elements) {
        this();
        addNodes(convertCollectionOfElementsToNodes(elements));
    }

    public WeightedGraph(Set<Node<T>> nodes, Set<Edge<T>> edges) {
        super();
        validateParameters(nodes, edges);
        this.nodes = nodes;
        this.edges = edges;
    }

    public WeightedGraph() {
        super();
        this.nodes = new HashSet<Node<T>>();
        this.edges = new HashSet<Edge<T>>();
    }

    public void addNode(Node<T> node) {
        this.nodes.add(node);
    }

    public void addNodes(Set<Node<T>> nodes) {
        this.nodes.addAll(nodes);
    }

    public void addEdge(Edge<T> edge) {
        this.edges.add(edge);
    }

    public void addEdges(Set<Edge<T>> edges) {
        this.edges.addAll(edges);
    }

    public Set<Node<T>> getNodes() {
        return nodes;
    }

    public Set<Edge<T>> getEdges() {
        return edges;
    }

    public void connectNodesBidirectional(Node<T> first, Node<T> second) {
        connectNodesBidirectional(first, second, 0);
    }

    public void connectNodesBidirectional(Node<T> first, Node<T> second,
            int weight) {
        validateNode(first);
        validateNode(second);
        edges.add(new Edge<T>(first, second, weight));      
        edges.add(new Edge<T>(second, first, weight));
    }

    public void connectNodes(Node<T> first, Node<T> second) {
        connectNodes(first, second, 0);
    }

    public void connectNodes(Node<T> first, Node<T> second, int weight) {
        validateNode(first);
        validateNode(second);
        edges.add(new Edge<T>(first, second, weight));
    }

    private Set<Node<T>> convertCollectionOfElementsToNodes(Collection<T> elements){
        Set<Node<T>> nodes = new HashSet<Node<T>>();
        for(T element : elements) {
            nodes.add(new Node<T>(element));
        }
        return nodes;
    }

    private void validateParameters(Set<Node<T>> nodes, Set<Edge<T>> edges) {
        Validate.notNull(nodes, "Collection of nodes can't be null.");
        Validate.notNull(edges, "Collection of nodes can't be null.");
        for (Edge<T> edge : edges) {
            Validate.isTrue(
                    nodes.contains(edge.getFirst())
                            && nodes.contains(edge.getSecond()),
                    "Should be passed properly configured collection, each node of each edge should exist in node collection.");
        }
    }

    private void validateNode(Node<T> node) {
        Validate.notNull(node, "Node can't be null.");
        Validate.isTrue(nodes.contains(node),
                "Graph should contains specified node: " + node + ".");
    }
}

测试类代码

    WeightedGraph<Integer> graph = new WeightedGraph<Integer>();

    Node<Integer> first = new Node<Integer>(1);
    Node<Integer> second = new Node<Integer>(2);
    Node<Integer> third = new Node<Integer>(3);
    Node<Integer> fourth = new Node<Integer>(4);

    graph.addNode(first);
    graph.addNode(second);
    graph.addNode(third);
    graph.addNode(fourth);

    graph.connectNodesBidirectional(first, second);
    graph.connectNodesBidirectional(second, third);
    graph.connectNodesBidirectional(first, third);
    graph.connectNodesBidirectional(third, fourth);
    graph.connectNodesBidirectional(fourth, second);

    Set<Node<Integer>> nodes = graph.getNodes();
    Set<Set<Node<Integer>>> result = new HashSet<Set<Node<Integer>>>();
    for (Node<Integer> node : nodes) {
        result.add(node.getAllRelatedNeighbors());
    }

我希望你能帮我解决递归函数。感谢您抽出时间。

Answer 1

[从评论复制]在跟踪节点时，您需要跟踪您已经看到的节点，例如将您关注的所有节点放入一个集合中。每当您考虑一个新节点时，您都​​会检查您之前是否一直在关注此节点，如果是，则忽略它。