Graphs

Revised by Tran Thanh Tung

1
Contents

 Definition
 Implementation
 Depth First Search
 Breadth First Search
 Topological sorting
 Dijkstra Algorithm
 Connectivity Problem

2
Graphs

 Graph is a data structure which represent relationships

between entities
 Vertices represent entities
 Edges represent some kind of relationship

3
Example

 The graph on the previous page could be used to model

San Jose freeway connections:

4
Adjacency

 Two vertices are adjacent to one another if they are

connected by a single edge

 For example:
 I and G are adjacent
 A and C are adjacent
 I and F are not adjacent

 Two adjacent nodes are

considered neighbors

5
Path

 A path is a sequence of edges

 Paths in this graph include:

 BAEJ, CAFG, HFEJDCAB, HIJDCBAFE, etc.

6
Connected Graphs

 A graph is connected if there is at least one path from

every vertex to every other vertex

7
Unconnected Graph

 An unconnected graph consists of several connected

components:

 Connected components of this graph are:

 AB, and CD
 We’ll be working with connected graphs
8
Directed Graphs

 A graph where edges have directions

 Usually designated by an arrow

9
Weighted Graphs

 A graph where edges have weights, which quantifies the

relationship
 For example, you may assign path distances between cities
 Or airline costs
 These graphs can be directed or undirected

10
Vertices: Java
Implementation
 We can represent a vertex as a Java class with:
 Character data
 A boolean data member to check if it has been visited

 Now we need to specify edges.

 But in a graph, we don’t know how many there will be!

 We can do this using either an adjacency matrix or an

adjacency list. We’ll look at both.

11
Adjacency Matrix

 An adjacency matrix for a graph with n nodes, is size n

xn
 Position (i, j) contains a 1 if there is an edge connecting
node i with node j
 Zero otherwise
 For example, here is a graph and its adjacency matrix:

12
Redundant?

 This may seem a bit redundant:

 Why store two pieces of information for the same edge?

 i.e., (A, B) and (B, A)
 Unfortunately, there’s no easy way around it
 Because edges have no direction
 No concept of ‘parents’ and ‘children’
13
Adjacency List

 An array of linked lists

 Index by vertex, and obtain a linked list of neighbors
 Here is the same graph, with its adjacency list:

14
Application: Searches

 A fundamental operation for a graph is:

 Starting from a particular vertex
 Find all other vertices which can be reached by following paths

 Example application
 How many towns in the VN can be reached by train from
Da Lat?

 Two approaches
 Depth first search (DFS)
 Breadth first search (BFS)
15
Depth First Search (DFS)
 Idea
 Pick a starting point
 Follow a path to unvisited
vertices, as long as you can
until you hit a dead end
 When you hit a dead end, go
back to a previous spot and hit
unvisited vertices
 Stop when every path is a dead
end

16
Depth First Search (DFS)

 Algorithm
 Pick a vertex (call it A) as your starting point
 Visit this vertex, and:
 Push it onto a stack of visited vertices
 Mark it as visited (so we don’t visit it again)
 Visit any neighbor of A that hasn’t yet been visited
 Repeat the process
 When there are no more unvisited neighbors
 Pop the vertex off the stack
 Finished when the stack is empty

 Note: We get as far away from the starting point until we

reach a dead end, then pop (can be applied to mazes)
17
18
Example

 Start from A, and execute depth first search on this

graph, showing the contents of the stack at each step
 Every step, we’ll either have a visit or pop

19
Depth First Search:
Complexity
 Let |V| be the number of vertices in a graph
 And let |E| be the number of edges

 In the worst case, we visit every vertex and every edge:

 O(|V| + |E|) time

 At first glance, this doesn’t look too bad

 But remember a graph can have lots of edges!
 Worst case, every vertex is connected to every other:
 (n-1) + (n-2) + … + 1 = O(n2)
 So it can be expensive if the graph has many edges

20
Breadth First Search (BFS)
 Same application as DFS; we
want to find all vertices which
we can get to from a starting
point, call it A
 However this time, instead of
going as far as possible until
we find a dead end, like DFS
 We visit all the closest
vertices first
 Then once all the closest
vertices are visited, branch
further out

21
Breadth First Search (BFS)

 We’re going to use a queue instead of a stack!

 Algorithm
 Start at a vertex, call it current
 If there is an unvisited neighbor, mark it, and insert it into
the queue
 If there is not:
 If the queue is empty, we are done, otherwise:
 Remove a vertex from the queue and set current to that
vertex, and repeat the process

22
Example

 Start from A, and execute breadth first search on this

graph, showing the contents of the queue at each step
 Every step, we’ll either have a visit or a removal

23
Breadth First Search:
Complexity
 Let |V| be the number of vertices in a graph
 And let |E| be the number of edges

 In the worst case, we visit every vertex and every edge:

 O(|V| + |E|) time
 Same as DFS

 Again, if the graph has lots of edges, you approach

quadratic run time which is the worst case

24
Minimum Spanning Trees (MSTs)
 On that note of large numbers of edges slowing down
our precious search algorithms:
 Let’s look at MSTs, which can help ameliorate this problem
 It would be nice to take a graph and reduce the number
of edges to the minimum number required to span all
vertices:

What’s the
number of
edges
now?

25
We’ve done it already…
 Actually, if you execute DFS you’ve already computed
the MST!

 Think about it: you follow a path for as long as you can,
then backtrack (visit every vertex at most once)
 You just have to save edges as you go

26
Directed Graphs

 A directed graph is a graph where the edges have

direction, signified by arrows:

 This will simplify the adjacency matrix a bit…

27
Adjacency Matrix

 The adjacency matrix for this graph does not contain

redundant entries
 Because now each edge has a source and a sink
 So entry (i, j) is only set to 1 if there is an edge going from
i to j
 0 otherwise

28
Topological Sort
 Only works with DAGs (Directed Acyclic Graphs)
 That is if the graph has a cycle, this will not work

 Idea: Sort all vertices such that if a vertex’s successor

always appears after it in a list (application: course
prerequisites) 29
30
Topological Sort
 Algorithm
 Find a vertex that has no successors
 Delete this vertex from the graph, and insert its label at the
beginning of a list
 Repeat until every vertex is gone

 Works because if a vertex has no successors, it must be the

last one (or tied for last) in the topological ordering
 As soon as it’s removed, at least one of the remaining vertices
must not have successors
 Because there are no cycles!

 Graph does NOT have to be fully connected for this to work!

31
Weighted Graphs

 Once again, a graph where edges have weights, which

quantifies the relationship
 These graphs can be directed or undirected

32
Weighted Graph: Adjacency
List
 The adjacency list for a weighted graph contains edge
weights
 Instead of 0 and 1

 If there is no edge connecting vertices i and j, a weight of

INFINITY is used (not 0!)
 Because ‘0’ can also be a weight
 Also most applications of weighted graphs are to find minimum
spanning trees or shortest path (we’ll look at this)

 Also remember if the graph is undirected, redundant

information should be stored

33
Weighted Graph: Adjacency List

A B C D E F
A INF INF INF INF 0.1 0.9
B 0.3 INF 0.3 0.4 INF INF
C INF INF INF 0.6 0.4 INF
D INF INF INF INF 1 INF
E 0.55 INF INF INF INF 0.45
F INF INF INF 1 INF 34
INF
Dijkstra’s Algorithm
 Given a weighted graph, find the shortest path (in terms
of edge weights) between two vertices in the graph
 Numerous applications
 Cheapest airline fare between departure and arrival cities
 Shortest driving distance in terms of mileage

35
Dijkstra’s Algorithm

 Suppose in the graph below, we wanted the shortest path

from B to F

 Idea: Maintain a table of the current shortest paths from B

to all other vertices (and the route it takes)
 When finished, the table will hold the shorest path from B to
all other vertices
36
Dijsktra’s Algorithm
1 Initialization:
2 N = {A}
3 for all nodes v
4 if v adjacent to A
5 then D(v) = c(A,v)
6 else D(v) = infty
7
8 Loop
9 find w not in N such that D(w) is a minimum
10 add w to N
11 update D(v) for all v adjacent to w and not in N:
12 D(v) = min( D(v), D(w) + c(w,v) )
13 /* new cost to v is either old cost to v or known
14 shortest path cost to w plus cost from w to v */
15 until all nodes in N
School of CSE – International University HCM City
Page 37
 Dijkstra’s algorithm example
Step start N D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A infinity infinity
1 AD 2,A 4,D 2,D infinity
2 ADE 2,A 3,E 4,E
3 ADEB 3,E 4,E
4 ADEBC 4,E
5 ADEBCF

B 3 C
2 5
A 2 F
1
3
1 2
D E
School of CSE – International University HCM City
1
Page 38
School of CSE – International University HCM City
Page 39
Dijkstra’s Algorithm

 Here is our initial graph:

 And here is our table:

A C D E F
INF INF INF INF INF

40
Step 1

 Take all edges leaving B,

and put their weights in
the table
Along with the source
vertex

 And here is our table:

A C D E F
0.3 (B) 0.3 (B) 0.4 (B) INF INF

41
Step 2

 Pick the edge with

the smallest weight
and mark it as the shortest
path from B
(How do we know that?)

 And here is our table:

A C D E F
0.3* (B) 0.3 (B) 0.4 (B) INF INF

42
Step 3

 Now choose one of the

edges with minimal weight
and repeat the process
(explore adj. vertices and
mark their total weight)

 And here is our table:

A C D E F
0.3* (B) 0.3 (B) 0.4 (B) INF INF

43
Step 4

 In this case, we’ll look at A

 Explore adjacent vertices
 Enter the total weight
from B to those vertices
 IF that weight is smaller than
 the current entry in the table
 Ignore the ones marked (*)

 So here is our table:

A C D E F
0.3* (B) 0.3 (B) 0.4 (B) 0.4 (A) 1.2 (A)

44
Step 5

 Now, A is marked and

 we’ve visited its neighbors
 So pick the lowest entry
in the table (in this case C)
and repeat the process

 So here is our table:

A C D E F
0.3* (B) 0.3* (B) 0.4 (B) 0.4 (A) 1.2 (A)

45
Step 6

 Visit C’s neighbors that

 are unmarked
 Insert their total weight
 into the table, IF it’s
 smaller than the current
 entry

 So in fact, nothing changes in the table:

A C D E F
0.3* (B) 0.3* (B) 0.4 (B) 0.4 (A) 1.2 (A)
46
Step 7

 Now we visit D
 Which only contains
 one edge to E

 0.4+1 = 1.4, which

 is larger than 0.4

 So again, nothing changes in the table:

A C D E F
0.3* (B) 0.3* (B) 0.4* (B) 0.4 (A) 1.2 (A)
47
Step 8

 Now we visit E
 Has two outgoing edges
 One to A (marked, ignore)
 One to F, which changes
 the table to
 0.4 + 0.45 = 0.85

 Which is smaller than the

 current entry, 1.2

 So the table changes, we found a shorter path to F:

A C D E F
0.3* (B) 0.3* (B) 0.4* (B) 0.4* (A) 0.85 (E)
48
Step 9

 Only one vertex left, so

 we’re actually finished
 Shortest path can be
 obtained by starting from
 the destination entry and
 working backwards
 F <- E <- A <- B

 Shortest path from B to F is: B -> A -> E -> F

 Total weight: 0.85
A C D E F 49

0.3* (B) 0.3* (B) 0.4* (B) 0.4* (A) 0.85* (E)
Example

 Let’s try this example with train costs:

50
Exercise

51