title: How can I recursively get all connected nodes of graph, which can contain cycles?
body: <p>I try to implement weighted graph. Almost done, but I faced with one problem, I can't properly collect all connected nodes of graph. For example I have following graph:</p>
  
  <pre><code>  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
  </code></pre>
  
  <p>I want to get as result set of sets [[1,2,3,4],[5,6]], my code works good if no cycles but with cycles my code goes to infinite loop.</p>
  
  <p>Node class:</p>
  
  <pre><code>    public class Node&lt;T&gt; {
  
      private T content;
  
      private Set&lt;Node&lt;T&gt;&gt; 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&lt;Node&lt;T&gt;&gt;();
      }
  
      public T getContent() {
          return content;
      }
  
      public void setContent(T content) {
          this.content = content;
      }
  
      public boolean hasNeighbors() {
          return !neighbors.isEmpty();
      }
  
      public void addNeighbor(Node&lt;T&gt; neighbor) {
          this.neighbors.add(neighbor);
      }
  
      public Set&lt;Node&lt;T&gt;&gt; getNeighbors() {
          return neighbors;
      }
  
      public void setNeighbors(Set&lt;Node&lt;T&gt;&gt; neighbors) {
          this.neighbors = neighbors;
      }
  
      public boolean isMarked() {
          return marked;
      }
  
      public void setMarked(boolean marked) {
          this.marked = marked;
      }
  
      public Set&lt;Node&lt;T&gt;&gt; getAllRelatedNeighbors() {
          Set&lt;Node&lt;T&gt;&gt; result = new HashSet&lt;Node&lt;T&gt;&gt;();
          result.add(this);
  
          if (neighbors.isEmpty()) {
              return result;
          }
  
          for (Node&lt;T&gt; neighbor : neighbors) {
              result.add(neighbor);
              for(Node&lt;T&gt; 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&lt;T&gt; {
  
      private Node&lt;T&gt; first;
  
      private Node&lt;T&gt; second;
  
      private int weight;
  
      public Edge(Node&lt;T&gt; first, Node&lt;T&gt; second, int weight) {
          this(first, second);
          this.weight = weight;
      }
  
      public Edge(Node&lt;T&gt; first, Node&lt;T&gt; second) {
          super();
          this.first = first;
          this.second = second;
          this.first.addNeighbor(second);
          this.second.addNeighbor(first);
      }
  
      public Node&lt;T&gt; getFirst() {
          return first;
      }
  
      public void setFirst(Node&lt;T&gt; first) {
          this.first = first;
      }
  
      public Node&lt;T&gt; getSecond() {
          return second;
      }
  
      public void setSecond(Node&lt;T&gt; 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&lt;T&gt; {
  
      private Set&lt;Node&lt;T&gt;&gt; nodes;
  
      private Set&lt;Edge&lt;T&gt;&gt; edges;
  
      public WeightedGraph(Collection&lt;T&gt; elements) {
          this();
          addNodes(convertCollectionOfElementsToNodes(elements));
      }
  
      public WeightedGraph(Set&lt;Node&lt;T&gt;&gt; nodes, Set&lt;Edge&lt;T&gt;&gt; edges) {
          super();
          validateParameters(nodes, edges);
          this.nodes = nodes;
          this.edges = edges;
      }
  
      public WeightedGraph() {
          super();
          this.nodes = new HashSet&lt;Node&lt;T&gt;&gt;();
          this.edges = new HashSet&lt;Edge&lt;T&gt;&gt;();
      }
  
      public void addNode(Node&lt;T&gt; node) {
          this.nodes.add(node);
      }
  
      public void addNodes(Set&lt;Node&lt;T&gt;&gt; nodes) {
          this.nodes.addAll(nodes);
      }
  
      public void addEdge(Edge&lt;T&gt; edge) {
          this.edges.add(edge);
      }
  
      public void addEdges(Set&lt;Edge&lt;T&gt;&gt; edges) {
          this.edges.addAll(edges);
      }
  
      public Set&lt;Node&lt;T&gt;&gt; getNodes() {
          return nodes;
      }
  
      public Set&lt;Edge&lt;T&gt;&gt; getEdges() {
          return edges;
      }
  
      public void connectNodesBidirectional(Node&lt;T&gt; first, Node&lt;T&gt; second) {
          connectNodesBidirectional(first, second, 0);
      }
  
      public void connectNodesBidirectional(Node&lt;T&gt; first, Node&lt;T&gt; second,
              int weight) {
          validateNode(first);
          validateNode(second);
          edges.add(new Edge&lt;T&gt;(first, second, weight));      
          edges.add(new Edge&lt;T&gt;(second, first, weight));
      }
  
      public void connectNodes(Node&lt;T&gt; first, Node&lt;T&gt; second) {
          connectNodes(first, second, 0);
      }
  
      public void connectNodes(Node&lt;T&gt; first, Node&lt;T&gt; second, int weight) {
          validateNode(first);
          validateNode(second);
          edges.add(new Edge&lt;T&gt;(first, second, weight));
      }
  
      private Set&lt;Node&lt;T&gt;&gt; convertCollectionOfElementsToNodes(Collection&lt;T&gt; elements){
          Set&lt;Node&lt;T&gt;&gt; nodes = new HashSet&lt;Node&lt;T&gt;&gt;();
          for(T element : elements) {
              nodes.add(new Node&lt;T&gt;(element));
          }
          return nodes;
      }
  
      private void validateParameters(Set&lt;Node&lt;T&gt;&gt; nodes, Set&lt;Edge&lt;T&gt;&gt; edges) {
          Validate.notNull(nodes, "Collection of nodes can't be null.");
          Validate.notNull(edges, "Collection of nodes can't be null.");
          for (Edge&lt;T&gt; edge : edges) {
              Validate.isTrue(
                      nodes.contains(edge.getFirst())
                              &amp;&amp; nodes.contains(edge.getSecond()),
                      "Should be passed properly configured collection, each node of each edge should exist in node collection.");
          }
      }
  
      private void validateNode(Node&lt;T&gt; node) {
          Validate.notNull(node, "Node can't be null.");
          Validate.isTrue(nodes.contains(node),
                  "Graph should contains specified node: " + node + ".");
      }
  }
  </code></pre>
  
  <p>Code of test class </p>
  
  <pre><code>    WeightedGraph&lt;Integer&gt; graph = new WeightedGraph&lt;Integer&gt;();
  
      Node&lt;Integer&gt; first = new Node&lt;Integer&gt;(1);
      Node&lt;Integer&gt; second = new Node&lt;Integer&gt;(2);
      Node&lt;Integer&gt; third = new Node&lt;Integer&gt;(3);
      Node&lt;Integer&gt; fourth = new Node&lt;Integer&gt;(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&lt;Node&lt;Integer&gt;&gt; nodes = graph.getNodes();
      Set&lt;Set&lt;Node&lt;Integer&gt;&gt;&gt; result = new HashSet&lt;Set&lt;Node&lt;Integer&gt;&gt;&gt;();
      for (Node&lt;Integer&gt; node : nodes) {
          result.add(node.getAllRelatedNeighbors());
      }
  </code></pre>
  
  <p>I hope you help me with recursive function. Thank you for your time.</p>