How to print these letters out in depth first search format How do I make the output return the result: [a, c, e, b, d, g, f, h, j] instead of [a, j, e, h, f, b, g, d, c]? I think there is something wrong with my depthFirstTransversal method but I don’t know where. My goal is to ultimately accept the input: a c e j e b f h b d g and get the result: [a, c, e, b, d, g, f, h, j]
@Yunnosch I did my best, let me know what you think: depthFirstTraversal takes the input graph and root and places it into a set
declares a LinkedHashSet Visited and a stack called stack
pushes the root “a” onto the stack while the stack isn’t empty: String vertex = stack.pop() =“a” If (visited doesn’t contain vertex) Add vertex “a” to visited. For(the vertex v: getAdjVertices(vertex) “a”. which takes a label as the input and returns a new vertex and arraylist Stack.push(v.label)
I think my code returns a depth first search but I want it to return the results from first input to last, not last input to first. So if c e and j depend on a, I want it to return a c e j, not a j e c
import java.util.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
public class Graph {
public static class GraphTraversal {
static Set<String> depthFirstTraversal(Graph graph, String root) {
Set<String> visited = new LinkedHashSet<String>();
Stack<String> stack = new Stack<String>();
stack.push(root);
while (!stack.isEmpty()) {
String vertex = stack.pop();
if (!visited.contains(vertex)) {
visited.add(vertex);
for (Vertex v : graph.getAdjVertices(vertex)) {
stack.push(v.label);
}
}
}
return visited;
}
static Set<String> breadthFirstTraversal(Graph graph, String root) {
Set<String> visited = new LinkedHashSet<String>();
Queue<String> queue = new LinkedList<String>();
queue.add(root);
visited.add(root);
while (!queue.isEmpty()) {
String vertex = queue.poll();
for (Vertex v : graph.getAdjVertices(vertex)) {
if (!visited.contains(v.label)) {
visited.add(v.label);
queue.add(v.label);
}
}
}
return visited;
}
}
private Map<Vertex, List<Vertex>> adjVertices;
Graph() {
this.adjVertices = new HashMap<Vertex, List<Vertex>>();
}
void addVertex(String label) {
adjVertices.putIfAbsent(new Vertex(label), new ArrayList<>());
}
void removeVertex(String label) {
Vertex v = new Vertex(label);
adjVertices.values().stream().forEach(e -> e.remove(v));
adjVertices.remove(new Vertex(label));
}
void addEdge(String label1, String label2) {
Vertex v1 = new Vertex(label1);
Vertex v2 = new Vertex(label2);
adjVertices.get(v1).add(v2);
adjVertices.get(v2).add(v1);
}
void removeEdge(String label1, String label2) {
Vertex v1 = new Vertex(label1);
Vertex v2 = new Vertex(label2);
List<Vertex> eV1 = adjVertices.get(v1);
List<Vertex> eV2 = adjVertices.get(v2);
if (eV1 != null)
eV1.remove(v2);
if (eV2 != null)
eV2.remove(v1);
}
List<Vertex> getAdjVertices(String label) {
return adjVertices.get(new Vertex(label));
}
String printGraph() {
StringBuffer sb = new StringBuffer();
for(Vertex v : adjVertices.keySet()) {
sb.append(v);
sb.append(adjVertices.get(v));
}
return sb.toString();
}
class Vertex {
String label;
Vertex(String label) {
this.label = label;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + getOuterType().hashCode();
result = prime * result + ((label == null) ? 0 : label.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Vertex other = (Vertex) obj;
if (!getOuterType().equals(other.getOuterType()))
return false;
if (label == null) {
if (other.label != null)
return false;
} else if (!label.equals(other.label))
return false;
return true;
}
@Override
public String toString() {
return label;
}
private Graph getOuterType() {
return Graph.this;
}
}
static Graph createGraph() {
Graph graph = new Graph();
graph.addVertex("a");
graph.addVertex("c");
graph.addVertex("e");
graph.addVertex("j");
graph.addVertex("b");
graph.addVertex("f");
graph.addVertex("h");
graph.addVertex("d");
graph.addVertex("g");
graph.addEdge("a", "c");
graph.addEdge("a", "e");
graph.addEdge("a", "j");
graph.addEdge("e", "b");
graph.addEdge("e", "f");
graph.addEdge("e", "h");
graph.addEdge("b", "d");
graph.addEdge("b", "g");
return graph;
}
public static void main(String[] args) {
Graph graph = createGraph();
System.out.println(GraphTraversal.depthFirstTraversal(graph, "a"));
}
}
The neighbors are added to the stack in your creation order and you want the graph to be traversed in that order, the ArrayList you create upholds that order but stack is LIFO which means that for an arbitrary node if a neighbor is added to the stack first, it is popped and processed last (for example if c as a neighbor of a is added to the stack first it is popped last, and j is visited first) so you have to add it last (in the reverse order) for it to be traversed first.
if (!visited.contains(vertex)) {
visited.add(vertex);
List<Vertex> neighbors = graph.getAdjVertices(vertex);
for (int i = neighbors.size()-1; i >= 0; --i) {
Vertex v = neighbors.get(i);
stack.push(v.label);
}
}