У меня проблемы с моей DFS.Итак, я считаю, что мой фактический поиск в глубину работает, но мой родительский узел (pi), расстояние (d) и финиш (f) возвращают некоторые странные числа.
IЯ очень внимательно следил за псевдокодом, поместив переменные точно так, как они есть в примере DFS в книге.
Моя стратегия состоит в том, чтобы передатьв 4 ArrayLists: вершина (текущая вершина), pi (родитель), d (расстояние), f (финиш) размера количества полных вершин в функции DFS и добавление значений по мере их появления в рекурсии.
DFS
enum VertexState {
White, Gray, Black}
// The function to do DFS traversal. It uses recursive DFSVisit()
//passes in 4 array lists (vertex, pi, d, f) that keep track of current vertex, parent node, distance, and finish times respectively
public void DFS(List<Integer> vertex, List<Integer> pi, List<Integer> d, List<Integer> f)
{
VertexState state[] = new VertexState[numberOfVertices()];
// Mark all the vertices as white (not visited)
for (int i = 0; i < numberOfVertices(); i++) {
state[i] = VertexState.White;
}
int time = 0; //initialize time
// Call the recursive helper function to print DFS traversal
// starting from all vertices one by one
for (int i = 0; i < numberOfVertices(); i++) {
if( state[i]== VertexState.White)
DFSVisit(i, state, vertex, pi, d, f, time);
}
}
// A function used by DFS
//passes in u (current node) and it's state (color)
//passes in 4 array lists (vertex, pi, d, f) that keep track of current vertex, parent node, distance, and finish times respectively
public void DFSVisit(int u, VertexState[] state, List<Integer> vertex, List<Integer>pi, List<Integer>d, List<Integer>f, int time)
{
time=time+1; //increment time (white vertex u has been discovered)
d.add(time); //add current time int to distance array list
// Mark the current node as gray (visited)
state[u] = VertexState.Gray;
vertex.add(u); //add current node to vertex array list
// Recur for all the vertices adjacent to this vertex
Iterator<Integer> i = adjacencies[u].listIterator();
while (i.hasNext())
{
int n = i.next();
if (state[n]==VertexState.White)
{
pi.add(n); //add current node to parent array list
DFSVisit(n, state, vertex, pi, d, f, time);
}
}
state[u] = VertexState.Black; //mark current node as black (it is finished)
time=time+1; //increment time
f.add(time); //add current time int to f (finished) array list
}
}
Драйвер
package com.company;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args)
{
//GENERATED GRAPHS
Graph g = new Graph(10, 0.3);
System.out.println("The graph is");
System.out.println( g.toString());
System.out.println("It had " + g.numberOfVertices() + " vertices and " + g.numberOfEdges() + " edges.");
//initialize array lists to print
List<Integer> vertex = new ArrayList<Integer>(g.numberOfVertices());
List<Integer> pi = new ArrayList<Integer>(g.numberOfVertices());
List<Integer> d = new ArrayList<Integer>(g.numberOfVertices());
List<Integer> f = new ArrayList<Integer>(g.numberOfVertices());
//depth first search
g.DFS(vertex,pi,d,f);
//print array lists
System.out.println("Vertex: "+vertex);
System.out.println("Parent: "+pi);
System.out.println("Distance: "+d);
System.out.println("Finish: "+f);
}
}
Вывод выглядит так:
График
0:[1, 5, 7]
1: [2, 6, 8, 9]
2: [1, 3, 4]
3: [0,1, 2, 8]
4: [1, 4]
5: [0, 4, 6]
6: [2, 6, 8]
7: [0, 8]
8: [5]
9: [3, 8]
У него было 10 вершин и 27 ребер.
Вершина: [0, 1, 2, 3, 8, 5, 4, 6, 9,7]
Родитель: [1, 2, 3, 8, 5, 4, 6, 9, 7]
Расстояние: [1, 2, 3, 4, 5, 6,7, 7, 3, 2]
Отделка: [8, 8, 7, 6, 5, 4, 4, 3, 3, 2]