Graphs
Graphs
Dr Timothy Kimber
February 2018
Introduction
Introduction
Graphs are fundamental to much of computer science
We have already seen how trees are used as data structures
All sorts of problems can be modelled using graphs
Networks, images, programs, anything involving related objects
Algorithms (580) Graphs February 2018 2 / 24
Terminology
Graph Terminology
Definition
A graph G is a pair (V ,E ) where V is a finite set (of objects) and E is a
binary relation on V . Elements of V are called vertices and elements of E
are called edges.
E is a set of pairs of vertices: {u, v} such that there is an edge
between u and v
Vertices u and v are adjacent if there is an edge {u, v}
Algorithms (580) Graphs February 2018 3 / 24
Terminology
Graph Terminology
A path from v1 to vn, written v1 vn, is a sequence 〈v1, v2, . . . , vn〉
such that there is an edge {vi , vi+1} for all i , 1 ≤ i < n
A cycle exists if there is a path from v to v , containing at least 4
vertices, for some vertex v
Vertex v is reachable from vertex u if u = v , or if there is a path u v
A connected component (also just called a component) is a set of
vertices all reachable from each other
Algorithms (580) Graphs February 2018 4 / 24
Representing Graphs
Graph Representation
Question
How should a graph be represented as a data structure?
A graph vertex is connected to 0-to-many other vertices
Going to assume that |V | is fixed
Algorithms (580) Graphs February 2018 5 / 24
Representing Graphs
Graph Representation
Two common ways:
Adjacency List(s): adj [u] contains v if there is an edge {u, v}
Adjacency Matrix: adjuv = 1 if there is an edge {u, v}, else 0
Adjacency lists good for sparse graphs
Algorithms (580) Graphs February 2018 6 / 24
Graph Search
Graph Search
Question
Why search a graph?
Searching a graph is like iterating through an ordered structure
Want to use data in the graph for some computation
Algorithms (580) Graphs February 2018 7 / 24
Graph Search
Graph Search Actions
Searching a graph has two actions:
Find adjacent vertices
Visit vertices not found before
Visiting means using the vertex: includes finding further vertices
Vertices are visited in the order they are first found
Vertices are coloured when they are first found/visited
Algorithms (580) Graphs February 2018 8 / 24
Breadth-First Search Design
Breadth-First Search
Question
What is a breadth-first search of a graph?
Algorithms (580) Graphs February 2018 9 / 24
Breadth-First Search Design
Breadth-First Search
In breadth-first search
Visit a vertex v (starting with source vertex s)
Find all vertices adjacent to v before visiting another
Result: search proceeds gradually down every path at the same rate
Algorithms (580) Graphs February 2018 10 / 24
Breadth-First Search Design
BFS Procedure
Question
How would you implement BFS?
Inputs are graph g and vertex s
g .adj [u] returns list of vertices
g .vertices is number of vertices
Objective: find all reachable vertices (will add actions later)
Algorithms (580) Graphs February 2018 11 / 24
Breadth-First Search Algorithm
Breadth-First Search
BFS (Input: graph g , vertex s)
found = new boolean[g.vertices]
q = new Queue(s) // FIFO queue
while q is not empty
u = q.remove()
for v in g.adj[u]
if not found[v] // avoid loops
found[v] = true
q.add(v)
The use of a (FIFO) queue is characteristic of BFS
By convention only search from given s
Algorithms (580) Graphs February 2018 12 / 24
Breadth-First Search Shortest Paths
Shortest Paths
BFS searches all paths at the same rate, so ...
Question
How would you modify the BFS procedure to find the length (number of
edges) of the shortest path from s to every other vertex?
BFS (Input: graph g , vertex s)
found = new boolean[g.vertices]
q = new Queue(s) // FIFO queue
while q is not empty
u = q.remove()
for v in g.adj[u]
if not found[v] // avoid loops
found[v] = true
q.add(v)
Algorithms (580) Graphs February 2018 13 / 24
Breadth-First Search Shortest Paths
Shortest Paths
BFS (Input: graph g , vertex s)
q = new Queue(s)
dist = new int[g.vertices]
dist.fill(-1)
dist[s] = 0
while q is not empty
u = q.remove()
for v in g.adj[u]
if dist[v] == -1 // not found
dist[v] = dist[u] + 1
q.add(v)
The distance is recorded when a vertex is (first) found
Arrays of size |V | like dist are also common in graph search
Unreachable vertices have dist[v] = -1
Algorithms (580) Graphs February 2018 14 / 24
Breadth-First Search Performance
Time
Question
For a connected graph with V vertices and E edges, how long does BFS
take?
BFS (Input: graph g , vertex s)
found = new boolean[g.vertices]
q = new Queue(s)
while q is not empty
u = q.remove()
for v in g.adj[u]
if not found[v]
found[v] = true
q.add(v)
Algorithms (580) Graphs February 2018 15 / 24
Breadth-First Search Performance
BFS Time Complexity
Each vertex is added and removed from the queue exactly once
Each adjacency list is used exactly once
Each edge contributes exactly two vertices to the adjacency lists
Time depends on both variables: O(V + E )
BFS (Input: graph g , vertex s)
found = new boolean[g.vertices]
q = new Queue(s)
while q is not empty
u = q.remove() runs once per vertex
for v in g.adj[u]
if not found[v] runs twice per edge
found[v] = true
q.add(v)
Algorithms (580) Graphs February 2018 16 / 24
Depth-First Search Design
Depth-First Search
Question
What is a depth-first search of a graph?
Algorithms (580) Graphs February 2018 17 / 24
Depth-First Search Design
Depth-First Search
In depth-first search
Visit every vertex as soon as it is found
i.e. start the next visit before completing current visit
Result: search follows a single path as far as possible and then
backtracks to the last alternative path
Algorithms (580) Graphs February 2018 18 / 24
Depth-First Search Design
DFS Procedure
Question
How would you implement DFS?
Input is graph g
Assume g .adj [u] returns list of vertices
Objective: find all vertices
Algorithms (580) Graphs February 2018 19 / 24
Depth-First Search Algorithm
Depth-First Search
DepthFirstSearch (Input: graph g)
found = new boolean[g.vertices]
for v in g
if not found[v]
DFS(g, v, found)
DFS (Input: graph g , vertex s, array found)
found[s] = true
for v in g.adj[s]
if not found[v]
DFS(g, v, found)
DFS can use call stack instead of explicit queue
Restart until whole graph searched (or not)
Algorithms (580) Graphs February 2018 20 / 24
Depth-First Search Example Application
An Application
Program checks if (whole) graph is acyclic
Returns true or false
DepthFirstAcyclic (Input: graph g)
parent = new int[g.vertices]
parent.fill(-1) // nothing found
for v in g
if parent[v] == -1 // not found
parent[v] = -2 // found, no parent
if not DFSAcyclic(g, v, parent)
return false
return true
Algorithms (580) Graphs February 2018 21 / 24
Depth-First Search Example Application
Depth-First Search
DFSAcyclic (Input: graph g , vertex u, array parent)
for v in g.adj[u]
if parent[v] == -1 // not found
parent[v] = u
if not DFSAcyclic(g, v, parent)
return false
else if parent[u] != v // cycle detected
return false
return true
A cycle exists if v was already found, unless it is u’s parent
Since u was just found, and not from v, the edge {u,v} completes an
alternative path to u from the source
Algorithms (580) Graphs February 2018 22 / 24
Depth-First Search Performance
Time
Question
For a connected graph with V vertices and E edges, how long does DFS
take?
DFS (Input: graph g , vertex s, array found)
found[s] = true
for v in g.adj[s]
if not found[v]
DFS(g, v, found)
Algorithms (580) Graphs February 2018 23 / 24
Depth-First Search Performance
DFS Time Complexity
DFS is called exactly once per vertex
Each adjacency list is used exactly once
Each edge contributes exactly two vertices to the adjacency lists
Time depends on both variables: O(V + E )
DFS (Input: graph g , vertex s, array found)
found[s] = true runs V times
for v in g.adj[s]
if not found[v] runs 2E times
DFS(g, v, found)
Algorithms (580) Graphs February 2018 24 / 24
Introduction
Terminology
Representing Graphs
Graph Search
Breadth-First Search
Design
Algorithm
Shortest Paths
Performance
Depth-First Search
Design
Algorithm
Example Application
Performance