Is this a proper implementation of a Graph for DFS, BFS

Question

I'm learning about search algorithms BFS and DFS. I plan to implement both but before I do that, I need to implement my graph structure. Here's my idea:

A graph of connecting cities: Each city is represented by a Node. Our graph will simply be an ArrayList of Nodes added as they're created, and each Node will have a list of it's neighbors, and a parent which will let us know where we came from (for path retrieval). I haven't coded anything up yet, I wanted to get some feedback on my ideas before spending the time writing up something that won't work. Here's some pseudocode-ish, code. One potential problem I can see is how we're going to deal with Nodes that we can get to from multiple places (multiple parents). If anyone has any suggestions on dealing with that, feel free to share.

 public class Node{
     String name;
     Node parent;
     ArrayList<Node> neighbors; 

    public addNeighbor(Node n);
    public setParent(Node n);
    public getNeighbors()
    ...
 }

 public static void main(String[] args){
     ArrayList<Node> graph = new ArrayList<Node>(); 
     //build node
     Node node = new Node(String name);

     //add neighbors
     node.addNeighbor(neighbor1);
     node.addNeighbor(neighbor2);

     //set parent
     node.setParent(parent1);

     //add to graph
     graph.add(node);

     path = dfs(graph, startNode, goalNode);
     System.out.print(path);
 }

Edit: I know I could look online and find implementations of this pretty easily, but I'd prefer to come up with my own solutions.

Alejandro Goñi Alejandro Goñi · Accepted Answer · 2016-02-24T22:36:57

Your implementation look good. It's the classic implentation of a graph structure (a node with a list of neighbors). Some points:

You can use backtracking to deal with multiples paths that reach the same node. If the dfs method have a recursive implementation, you need to avoid the recursive call if the Node has already a parent. But if the new path is better that the old one, then you discard the old parent, and set the new one.
Your implementation is a directional graph. In other words, you can build a graph that has a path from A to B, but has no path from B to A. I don't know if this is ok for you.
I recommend you encapsulate the building of the graph inside a wrapper, that build both paths automatically, whith a unique call to a method. That way, always you build bidirectional paths.
You can use a Set to store the neighbors. That way, there is no duplicates. Of course, you need to implements the "equals" method in the Node class.

Is this a proper implementation of a Graph for DFS, BFS

1 Answers