Description
Objectives
-
What is a Graph?
-
Depth First Search
-
Breadth First Search
-
Exercise
-
-
Challenge 1 (Silver Badge)
-
-
-
Challenge 2 (Gold Badge)
-
In real world, many problems are represented in terms of objects and connections between them. For example, in an airline route map, we might be interested in questions like: “What’s the fastest way to go from Denver to San Francisco” or “What is the cheapest way to go from Denver to San Francisco” To answer these questions we need information about connections between objects. Graphs are data structures used for solving these kinds of problems.
Graph: A graph is a pair (V, E), where V is a set of nodes, called vertices and E is a collection of pairs of vertices, called edges.
Directed Edge
-
Ordered pair of vertices (u, v)
-
First vertex u is the origin
-
Second vertex v is the destination
-
Example: one way road traffic
1
Recitation 9,
Graph Algorithms
Undirected Edge:
-
Unordered pair of vertices (u, v)
-
Example: Railway lines
Applications of Graphs
-
Representing relationships between components in electronic circuits.
-
Transportation networks: Highway network, Flight network
-
Computer networks: Local area network, Internet web
Graph Representation
As in other Abstract Data types, to manipulate graphs we need to represent them in some useful form. Basically, there are two ways of doing this:
-
Adjacency Matrix
-
Adjacency Lists
Graph Traversals
To solve problems on graphs, we need a mechanism for traversing the graphs. Graph traversal algorithms are also called a graph search algorithms. Like tree traversal algorithms (Inorder, Preorder, Postorder traversals), graph search algorithms can be thought of as starting at some source vertex in a graph, and ‘search’ the graph by going through the edges and making the vertices. Now, we will discuss two such algorithms for traversing the graphs.
-
Depth First Search (DFS)
-
Breadth First Search (BFS)
Depth First Search (DFS)
The strategy followed by depth-first search is, as its name implies, to search “deeper” in the graph whenever possible.
2
Recitation 9,
Graph Algorithms
The DFS algorithm is a recursive algorithm that uses the idea of backtracking. The idea is to travel as deep as possible from neighbour to neighbour before backtracking. What determines how deep is possible is that you must follow edges, and you don’t visit any vertex twice. To do this properly we need to keep track of which vertices have already been visited, plus how we got to where we currently are, so that we can backtrack.
Here, the word backtrack means that when you are moving forward and there are no more nodes along the current path, you move backwards on the same path to find nodes to traverse.
All the nodes on the current path are visited, after which the next path will be selected. We would be using the Adjacency lists to get the neighbours of any vertex.
Here’s a pseudocode of this recursive approach:
DFS(G, u)
u.visited = true
for each v ∈ G.Adj[u]
if v.visited == false
DFS(G,v)
init() {
for each u ∈ G
u.visited = false
for each u ∈ G
If u.visited==false
DFS(G, u)
}
Make sure that the nodes that are visited are marked. This will prevent you from visiting the same node more than once. If you do not mark the nodes that are visited and you visit the same node more than once, you may end up in an infinite loop.
This recursive behaviour (which uses a system stack) can be simulated by an iterative algorithm explicitly using a stack. So, DFS uses a stack to push nodes we mean to visit onto that.
We gave a pseudocode for DFS traversal using recursion and we will be giving a visualization of DFS traversal using stacks to help you understand better. The following will give you the basic idea of Stack implementation.
3
Recitation 9,
Graph Algorithms
