.png)
Graph data structures - Searching
Previously we looked at an introduction to graph data structures and designed a very basic Graph implementation. I also mentioned that the main things we would likely want to do with a graph is search/explore the graph.There are two primary tools that we will use to explore graphs - these are basic computer science concepts, and should be familiar to everyone who has studied computer science at uni and faced graphs before.
Depth First Search (DFS)
The concept behinds DFS is that given a starting point or root node, we will search as deep as we can one route before backtracking (e.g. select a neighbour to the root node, visit that neighbour, then select a neighbour from that node and visit - continue this until we reach a node that we cannot follow any more edges from, and then backtrack up the graph considering alternate neighbours at each step)
Below is a simple Java implementation of DFS using recursion to handle the backtracking.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public boolean depthFirstSearchRecurse( Graph g, String v, String target, List<String> visited ){ | |
| //Add current node to visited list | |
| visited.add(v); | |
| if (v.equals(target)) return true; | |
| // look at all neighbours for current node | |
| for ( String neighbour : g.getNeighbours(v) ){ | |
| if ( !visited.contains(neighbour) ) { | |
| //Recurse as deep as possible through graph | |
| boolean found = depthFirstSearchRecurse( g, neighbour, target, visited ); | |
| if (found) return true; | |
| } | |
| } | |
| return false; | |
| } |
Breadth First Search (BFS)
This search takes the different approach of looking as wide as possible before moving down a level. For example, we will visit all the immediate neighbours of the root, then select one of the immediate neighbours and visit their immediate neighbours - then backtrack up to visit other neighbours at this level.(image also from wikipedia)
BFS is also fairly simple, and pretty close to DFS but it uses a Queue (FIFO) structure rather than a stack to visit nodes from the root down first. Below is example code of BFS implemented in Java.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public boolean breadthFirstSearch(Graph g, String v, String target){ | |
| //Create a Queue structure and a list to keep track of nodes we have already visited | |
| Deque<String> q = new ArrayDeque<String>(); | |
| List<String> visited = new ArrayList<String>(); | |
| //Mark the root node as visited and add it to the Queue | |
| visited.add(v); | |
| q.add(v); | |
| //While the Queue is not empty keep inspecting neighbours | |
| while ( q.iterator().hasNext() ){ | |
| //Pop first element off Queue | |
| String vertex = q.removeFirst(); | |
| if (vertex.equals(target)) return true; | |
| //get at all neighbours of node being looked at and add them to the Queue | |
| for (String neighbour : g.getNeighbours(vertex)){ | |
| if ( !visited.contains(neighbour) ) { | |
| visited.add(neighbour); | |
| q.add(neighbour); | |
| } | |
| } | |
| } | |
| return false; | |
| } |
0 comments: