Я реализовал алгоритм на Java. Я кодировал две версии:
- тот, где я инициализировал структуры данных в конструкторе,
и
- тот, где я проанализировал текстовый файл и инициализировал структуру данных из ввода
Странно то, что я получил различное поведение от двух версий и с трудом могу понять, как.
Почему у меня другое поведение?
Алгоритм является первой частью поиска в глубину. Набор узлов следует посетить и распечатать только один раз . В моей версии, где я читаю из текстового файла, первый узел печатается дважды. Программа использует рекурсию.
Вот вывод, код ниже. В первых четырех строках печатаются структуры данных, затем распечатывается каждая информация о первом посещении узла и счетчик. Счетчик должен идти только к 2 , а не 3.
Вывод при чтении из текстового файла:
>java GraphStart ex1.txt
Node 1
Node 2
Edge: Node 1 -- Node 2
Edge: Node 2 -- Node 1
Start on Node 1
Node 1 Counter: 1
Node 2 Counter: 2
Node 1 Counter: 3
Выходные данные при инициализации в конструкторе:
Node 1
Node 2
Edge: Node 1 -- Node 2
Edge: Node 2 -- Node 1
Start on Node 1
Node 1 Counter: 1
Node 2 Counter: 2
Поиск в глубину - инициализирован в конструкторе:
public class DepthFirstSearch {
private final static LinkedList<Node> nodes = new LinkedList<Node>();
private static LinkedList[] edges = new LinkedList[0];
public DepthFirstSearch() {
Node node1 = new Node(1);
Node node2 = new Node(2);
nodes.add(node1);
nodes.add(node2);
edges = Arrays.copyOf(edges, 1);
edges[0] = new LinkedList<Edge>();
edges[0].add(new Edge(node1, node2));
edges = Arrays.copyOf(edges, 2);
edges[1] = new LinkedList<Edge>();
edges[1].add(new Edge(node2, node1));
DFS.startDFS(nodes, edges);
}
public static void main(String[] args) {
new DepthFirstSearch();
}
}
Поиск в глубину - инициализируется из текстового файла:
public class GraphStart {
private final static LinkedList<Node> nodes = new LinkedList<Node>();
private static LinkedList[] edges = new LinkedList[0];
public GraphStart(String fileName) {
scanFile(fileName);
DFS.startDFS(nodes, edges);
}
// Parse a textfile with even number of integers
// Add the nodes and edges to the datastructures
private static void scanFile(String filename) {
try {
Scanner sc = new Scanner(new File(filename));
while(sc.hasNextInt()){
Node startNode = new Node(sc.nextInt());
if(sc.hasNextInt()) {
Node endNode = new Node(sc.nextInt());
if(!nodes.contains(startNode)){
nodes.add(startNode);
//EDIT
System.out.println("Added " + startNode);
// Grow the Edge-array and initialize the content
if(edges.length < startNode.getNr())
edges = Arrays.copyOf(edges, startNode.getNr());
edges[startNode.getNr()-1] = new LinkedList<Edge>();
}
if(!nodes.contains(endNode)){
nodes.add(endNode);
//EDIT
System.out.println("Added " + endNode);
// Grow the Edge-array and initialize the content
if(edges.length < endNode.getNr())
edges = Arrays.copyOf(edges, endNode.getNr());
edges[endNode.getNr()-1] = new LinkedList<Edge>();
}
// Add the Edge
edges[startNode.getNr()-1].add(new Edge(startNode, endNode));
}
}
} catch (FileNotFoundException e) {
System.out.println("Can not find the file:" + filename);
System.exit(0);
}
}
public static void main(String[] args) {
if(args.length==1) {
new GraphStart(args[0]);
} else {
System.out.println("Wrong argument. <filename>");
}
}
}
Текстовый файл для ввода:
1 2
2 1
Он представляет край от узла 1 до узла 2 и край от узла 2 до узла 1.
Алгоритм реализован в статическом файле, используемом обеими версиями.
DFS - алгоритм:
public class DFS {
private static int counter = 0;
private static LinkedList<Node> nodes;
private static LinkedList[] edges;
public static void startDFS(LinkedList<Node> ns, LinkedList[] es) {
nodes = ns;
edges = es;
/* Print the data structures */
printList(nodes);
printEdges(edges);
for(Node n : nodes) {
if(!n.isVisited()) {
System.out.println("\nStart on "+n);
dfs(n);
}
}
}
private static void dfs(Node n) {
counter++;
n.visit();
System.out.println(n + " Counter: " + counter);
for(Object o : edges[n.getNr()-1]) {
if(!((Edge)o).getEnd().isVisited()) {
dfs(((Edge)o).getEnd());
}
}
private static void printList(LinkedList<?> list) {
for(Object obj : list)
System.out.println(obj);
}
private static void printEdges(LinkedList[] edges) {
for(LinkedList list : edges) {
System.out.print("Edge: ");
for(Object o : list) {
System.out.print(o);
}
System.out.println("");
}
}
}
РЕДАКТИРОВАТЬ: Добавлены списки кодов Node и Edge.
Node:
public class Node {
private final int nr;
private boolean visited = false;
public Node(int nr) {
this.nr = nr;
}
public int getNr() { return nr; }
public boolean isVisited() { return visited; }
public void visit() { visited = true; }
@Override
public boolean equals(Object obj) {
if(obj instanceof Node)
return ((Node)obj).getNr() == nr;
else
return false;
}
@Override
public String toString() {
return "Node " + nr;
}
}
Край:
public class Edge {
private final Node startNode;
private final Node endNode;
public Edge(Node start, Node end) {
this.startNode = start;
this.endNode = end;
}
public Node getStart() { return startNode; }
public Node getEnd() { return endNode; }
public String toString() {
return startNode + " " +
"--" + " " +
endNode;
}
}
Извините за очень длинные списки кодов. Я попытался изолировать свою проблему, а также показать работающую программу.