Basic Java: получить список подключенных узлов

Question

поэтому у меня есть список основных узлов, например узлов AB C.

каждый компонент может увидеть, что он прикреплен к, например:

a-> б

b-> с

c-> а

Я хочу так, что я могу получить список всех узлов в графе. Тем не менее, я столкнулся с проблемой, поскольку моя текущая система не может определить, достиг ли она уже достигнутой цели. EG в приведенном выше примере будет идти a-> b-> c-> a-> b и т. Д. Как я могу обнаружить это или как решить эту проблему.

Мой текущий "решение" getList() в Node классе:

ArrayList<Node> tempList = new ArrayList<Node>(); 

    tempList.add(this); 

    for(int i = 0 ; i < nodesAttachedTo.size();i++){ 
     tempList.addAll(nodesAttachedTo.get(i).getList()); 
    } 

    return tempList; 

Answer 1

Вы можете использовать HashSet. Он не позволит добавить один элемент дважды.

Вот пример кода, который сначала создает граф, похожий на ваш пример, затем начинается в какой-то момент на графике и проходит через него.

import java.util.HashSet; 

public class Node 
{ 
    private HashSet<Node> nextNodes = new HashSet<Node>(); 

    public Node() 
    { 
    } 

    public void addNextNode(Node node) 
    { 
     nextNodes.add(node); 
    } 

    public static void main(String[] args) 
    { 
     // this builds the graph of connected nodes 
     Node a = new Node(); 
     Node b = new Node(); 
     Node c = new Node(); 

     a.addNextNode(b); 
     b.addNextNode(c); 
     c.addNextNode(a); 

     //this is the set that will lsit all nodes: 
     HashSet<Node> allNodes = new HashSet<Node>(); 

     // this goes through the graph 
     a.listAllNodes(allNodes); 

     System.out.println(allNodes); 
    } 

    private void listAllNodes (HashSet<Node> listOfNodes) 
    { 
     // try to put all next nodes of the node into the list: 
     for(Node n : nextNodes) 
     { 
      if (listOfNodes.add(n))   // the set returns true if it did in fact add it. 
       n.listAllNodes(listOfNodes); // recursion 
     } 

    } 
} 

Это переход от одного узла ко всем узлам, которые этот узел знает. (скажем, что очень быстро три раза) Пока он не зашел в тупик (= узел, который он уже посетил)

Я решил использовать HashSet в самом узле, чтобы хранить все узлы, которые он знает. Это также может быть ArrayList или что-то еще. Но, поскольку я не думаю, что должно быть соединение дважды, HashSet, кажется, хороший выбор и в этой ситуации.

Answer 2

Я не знаком с вашими нотами, но вы можете использовать два указателя для решения своей проблемы. Начните с двух указателей, указывающих на один и тот же узел. Увеличивайте один указатель до тех пор, пока он не вернется к началу. Ниже приведен псевдокод.

ArrayList<Node> tempList = new ArrayList<Node>(); 
Node head = nodesAttachedTo.get(0); //get the head of the list 
tempList.add(head); 
Node runner = head; 
runner = runner.next; 
while (!runner.equals(head)) { 
    tempList.add(runner); 
    runner = runner.next; 
} 

Answer 3

Возможно, что hashmap - путь сюда. Он позволяет использовать постоянный доступ времени (требуется некоторые накладные расходы, но я предполагаю, что вы хотите, чтобы решение хорошо масштабировалось) к любому элементу на карте.

HashMap<String, String> specificSolution = new HashMap<String, String>(); 
specificSolution.put("a", "b"); 
specificSolution.put("b", "c"); 
specificSolution.put("c", "a"); 
// To get all nodes in the graph 
Set<String> nodes = specificSolution.keySet(); 

я реализовал с Последовательностью здесь, потому что вы не обеспечиваете определение узла класс в вашем вопросе, но он может быть легко выгружен.

Существует множество различных способов представления графика, и каждый из них имеет свои собственные ограничения/преимущества. Может быть, другой может быть более уместным, но нам нужна дополнительная информация о проблеме.