Graph Processing Algorithms
Data Structures and Abstractions
Graph Processing Algorithms
Lecture 33
* of 16
Depth First Search
Depth first search (DFS) answers the question “is vertex A connected to vertex B?”
Using an adjacency matrix, DFS takes O(V2).
Using an adjacency list, DFS takes O(V+E).
DFS of a graph is usually done recursively.
Textbook has code with explanations.
* of 16
Depth First Search Algorithm
DFS (fromVertex, toVertex)
boolean found = false
IF fromVertex <> toVertex // what if == ?
IF the fromVertex has not already been visited
Mark it as visited
FOR each vertex in its adjacency list AND while not found
found = DFS(adjacentVertex, toVertex)
ENDFOR
ENDIF
ELSE
found = true
ENDIF
return found // function wise
END DFS
* of 16
Examples
* of 16
Other Examples
Make sure you can do, by hand, a depth first search of a graph. The Graph program can be used to check your answers.
* of 16
Application to Maze Solving
Consider a maze.
This can be modelled as a graph.
DFS can now be used to find the route from start to finish.
* of 16
Breadth First Search
Breadth First Search (BFS) finds the closest solution to your current position in the graph.
For example, in all game playing you want the fastest route to a game win.
In a tree it is equivalent to searching layer by layer. Go through the animation of the breadth first search in the tree lecture notes first.
* of 16
Breadth First Search (fromVertex, toVertex)
boolean found = false
IF (fromVertex <> toVertex)
Put fromVertex on a queue
Mark fromVertex as visited
WHILE the queue is not empty AND not found
Remove qVertex from the queue
FOR each aVertex in the adjacency list of qVertex AND not found
IF aVertex has not been visited
IF aVertex <> toVertex
Add aVertex to the queue
Mark aVertex as visited
ELSE
found = true
ENDIF
ENDIF
ENDFOR
ENDWHILE
ELSE
found = true
ENDIF
return found
END BFS
* of 16
Breadth First Search Examples
* of 16
Other Examples
Make sure you can do, by hand, a breadth first search of a graph. Use the graphs program to check your answers.
* of 16
Shortest Path Problems
Shortest path problems apply to weighted graphs only.
There are three sub-problems:
Find the shortest path from vertex X to vertex W.
Find the shortest path between every pair of vertices.
Find the shortest path from a particular vertex to all other vertices.
The latter of these forms a Shortest Path Tree (SPT).
Every vertex has a different SPT.
* of 16
SPT Algorithms
There are many SPT algorithms.
Some are faster than others and some are easier to code (never the same algorithm of course!)
Research continues in the area because of the huge importance of network traffic routing, and other similar problems.
We will look at only one as it is easy to understand and good enough to be useful.
It has complexity of O(V), which is very good for a graph theory algorithm.
* of 16
Dijkstra’s SPT Algorithm
DijkstraSPT
Put the starting vertex into the tree
FOR V-1 times
Add the vertex that is adjacent to the SPT and which has the
shortest total path from the starting vertex
ENDFOR
End DijkstraSPT
0
From Vertex 0
1
4
0
1
2
3
4
5
6
7
2
3
6
7
5
END
0
1
2
3
4
5
6
7
87
91
138
60
125
172
70
102
144
205
* of 16
Dijkstra’s SPT Algorithm
DijkstraSPT
Put the starting vertex into the tree
FOR V-1 times
Add the vertex that is adjacent to the SPT and which has the
shortest total path from the starting vertex
ENDFOR
End DijkstraSPT
4
From Vertex 4
3
7
0
1
2
3
4
5
6
7
2
5
0
6
1
END
Note that this tree is different from the previous one.
0
1
2
3
4
5
6
7
87
91
138
60
125
172
70
102
144
205
* of 16
Shortest Path Between Two Vertices
This can be done using Dijkstra’s SPT algorithm, but stopping when the target vertex is reached.
ShortestPath
Put the starting vertex into the tree
WHILE we have added less than V-1 vertices AND
target not found
Add the vertex that is adjacent to the SPT and
which has the shortest total path from the
starting vertex
IF this is the target vertex
found = true
ENDIF
ENDWHILE
Return found
END Shortest Path
* of 16
Other Examples
Make sure you can draw, by hand, an SPT of a graph from any starting vertex. Use the Graph program to check your answers.
* of 16
Readings
Textbook Chapter on Graphs.
Reference book, Introduction to Algorithms. Part on Graph Algorithms contains a number of chapters on graph algorithms. Please read for further study. The lecture notes and textbook is sufficient for this unit.