Нерекурсивная DFS в Java с итераторами

Question

Я хочу, чтобы DFS-график (нерекурсивный) с использованием ArrayList и списка смежности. У меня есть следующий список смежности

2 3 4 
1 3 4 
1 2 4 
1 2 3 

Так узел 1 -> 2,3,4 узел 2 -> 1,3,4 ... я уже список смежности реализован в массивах, как это: (L являются линиями, а л элементы на линии)

ArrayList<List<Integer>>L=new ArrayList<List<Integer>>(); 
    ArrayList<Integer>l=new ArrayList<Integer>(); 

Я написал на бумаге следующий алгоритм, чтобы напечатать DFS графа с использованием 2 Стеки. Первым узлом может быть любой узел.

//all viz[i] = 0; 
stack.push(root); 
while (!stack.isEmpty()) 
    { 
     node = stack.pop(); 
     print node; 
     viz[node]=1; 
     for (each node.childnodes) 
       { 
       if(viz[i]==0) {stack.push(childnode)} 
       } 
    } 

Я не понимаю, как реализовать Итераторы, чтобы я мог использовать аррайалистов с моим алгоритмом. Я очень благодарен за любую помощь!

Answer 1

Вам не нужно явно использовать итераторы здесь - достаточно «foreach» разнообразия цикла for.

Сделайте Stack<Integer>, чтобы сохранить индекс текущего узла. Ваш for цикл будет выглядеть следующим образом:

Integer node = stack.pop(); 
// L.get(node) returns List<Integer>, letting you iterate 
// over your adjacency list using "foreach" loop: 
for (Integer child : L.get(node)) { 
    if(!viz[child]) { 
     stack.push(child); 
    } 
} 

Обратите внимание, что, так как ваш «посетили» массив содержит только 1 с и 0 с, вы должны использовать boolean вместо int для его элементов.