Graphs
Based on slides by David Kauchak
COSC 336 1
Graphs
What is a graph?
A
B
F
G
D
E
C
COSC 336
2
Graphs
A graph is a set of vertices V and a set of edges (u,v) E where u,v V
A
B
F
G
D
E
C
COSC 336
3
Graphs
How do graphs differ? What are graph characteristics we might care about?
A
B
F
G
D
E
C
COSC 336
4
Different types of graphs
Undirected – edges do not have a direction
A
B
F
G
D
E
C
COSC 336
5
Different types of graphs
Directed – edges do have a direction
A
B
F
G
D
E
C
COSC 336
6
Different types of graphs
Weighted – edges have an associated weight
A 8
B
2
C
7
D1
F 7
E
20 2
COSC 336
7
G
Different types of graphs
Weighted – edges have an associated weight
A 8
B
2
C
7
D1
F 7
E
20 2
COSC 336
8
G
Terminology
Path – A path is a list of vertices p1,p2,…pk where there exists an edge (pi,pi+1) E
A
B
F
D
E
CG
COSC 336 9
Terminology
Path – A path is a list of vertices p1,p2,…pk where there exists an edge (pi,pi+1) E
{A, B, D, E, F}
B
A
D
F E
CG
COSC 336 10
Terminology
Path – A path is a list of vertices p1,p2,…pk where there exists an edge (pi,pi+1) E
{C, D}
B
A
D
F E
CG
COSC 336 11
Terminology
Path – A path is a list of vertices p1,p2,…pk where there exists an edge (pi,pi+1) E
A simple path contains no repeated vertices (often this is implied)
F
D
E
CG
COSC 336 12
A
B
Terminology
Cycle – A subset of the edges that form a path such that the first and last node are the same
A
B
F
D
E
CG
COSC 336 13
Terminology
Cycle – A subset of the edges that form a path such that the first and last node are the same
{A, B, D} B
A
D
CG
COSC 336 14
F
E
Terminology
Cycle – A subset of the edges that form a path such that the first and last node are the same
A
not a cycle
B
F
D
E
CG
COSC 336 15
Terminology
Cycle – A subset of the edges that form a path such that the first and last node are the same
A
B
F
D
E
CG
COSC 336 16
Terminology
Cycle – A subset of the edges that form a path such that the first and last node are the same
A
not a cycle
B
F
D
E
CG
COSC 336 17
Terminology
Cycle – A path p1,p2,…pk where p1 = pk
cycle
A
B
F
D
E
CG
COSC 336 18
Terminology
Connected – every pair of vertices is connected by a path
connected
B
A
F
D
E
CG
COSC 336 19
Terminology
Connected – every pair of vertices is connected by a path
connected
B
A
F
D
E
CG
COSC 336 20
Terminology
Connected (undirected graphs) – every pair of vertices is connected by a path
not connected
B
A
F
D
E
CG
COSC 336 21
Terminology
Strongly connected (directed graphs) – Every two vertices are reachable by a path
not strongly connected
B
A
F
D
E
CG
COSC 336 22
Terminology
Strongly connected (directed graphs) – Every two vertices are reachable by a path
not strongly connected
B
A
D
F E
G 23
COSC 336
Terminology
Strongly connected (directed graphs) – Every two vertices are reachable by a path
strongly connected
B
A
D
F E
G 24
COSC 336
Different types of graphs
What is a tree (in our terminology)?
F
B
A
D
C
H E
G
COSC 336
25
Different types of graphs
Tree – connected, undirected graph without any cycles
F
B
A
D
C
H E
G
COSC 336
26
Different types of graphs
Tree – connected, undirected graph without any cycles
F
C
B
A
D
H E
G
need to specify root
COSC 336
27
Different types of graphs
Tree – connected, undirected graph without any cycles
F
A
B
H E
G
D
C
COSC 336
28
Different types of graphs
DAG – directed, acyclic graph
F
B
A
D
C
H E
G
COSC 336
29
Different types of graphs
Complete graph – an edge exists between every node
B
A
F
D
C
COSC 336
30
Different types of graphs
Bipartite graph – a graph where every vertex can be partitioned into two sets X and Y such that all edges connect a vertex u X and a vertex v Y
A B C
D
E
F G
COSC 336
31
When do we see graphs in real life problems?
• Transportation networks (flights, roads, etc.) • Communication networks
• Web
• Social networks
• Circuit design
• Bayesian networks
COSC 336 32
Standard notation for graphs
• Agraphisgivenbytwosets:thesetVofnodes(orvertices)andthesetEofedges. • Notation: G = (V,E)
• Notation for the number of nodes: |V| or n
• Notation for the number of edges: |V| or m
COSC 336 33
Node degree
In an undirected graph:
For a node v, deg(v) = no. of v’s neighbors
∑ ∈ deg 𝑣 = 2 𝐸
(because in the sum we count each edge twice) In a directed graph:
in-deg(v) = no of edges incoming in v out-deg(v) = no of edges outgoing from v
∑ ∈ in-deg(v) = ∑ ∈ out-deg(v) = |E|
COSC 336 34
Representing graphs
Adjacency list – Each vertex u V contains an adjacency list of the set of vertices v such that there exists an edge (u,v) E
A
A: B D B: A D
C: D
D: A B C E
D35
B
D
E C
COSC 3
36
E:
Representing graphs
Adjacency list – Each vertex u V contains an adjacency list of the set of vertices v such that there exists an edge (u,v) E
A
A: B B:
C: D
D: A B
COSC 3 D 36
B
D
E C
36
E:
Representing graphs
Adjacency matrix – A |V|x|V| matrix A such that:
1 if(i,j)E
otherwise
A
B
D
C
aij 0 E
ABCDE
A01010 B10010 C00010 D11101 E00010
COSC 336
37
Representing graphs
Adjacency matrix – A |V|x|V| matrix A such that:
A
B
D
C
aij 0 E
ABCDE
A01010 B10010 C00010 D11101 E00010
1 if(i,j)E
otherwise
COSC 336
38
Representing graphs
Adjacency matrix – A |V|x|V| matrix A such that:
A
B
D
C
aij 0 E
ABCDE
A01010 B10010 C00010 D11101 E00010
1 if(i,j)E
otherwise
COSC 336
39
Representing graphs
Adjacency matrix – A |V|x|V| matrix A such that:
A
B
D
C
aij 0 E
ABCDE
A01010 B10010 C00010 D11101 E00010
1 if(i,j)E
otherwise
COSC 336
40
Representing graphs
Adjacency matrix – A |V|x|V| matrix A such that:
1 if(i,j)E aij 0 otherwise
A
B
D
Is it always symmetric?
ABCDE A01010
B10010 C00010 D11101 E00010
E C
COSC 336
41
Representing graphs
Adjacency matrix – A |V|x|V| matrix A such that:
A
B
D
C
aij 0 E
ABCDE
A01000 B00000 C00010 D11000 E00010
1 if(i,j)E
otherwise
COSC 336
42
Adjacency list vs. adjacency matrix
Adjacency list
Sparse graphs (e.g. web) Space efficient
Must traverse the adjacency list to discover is an edge exists
Adjacency matrix
Dense graphs
Constant time lookup to discover if an edge exists
Simple to implement
For non-weighted graphs, only requires boolean matrix
Can we get the best of both worlds?
COSC 336 43
Sparse adjacency matrix
Rather than using an adjacency list, use an adjacency hashtable
A
B
D
C
E
A: hashtable [B,D]
B: hashtable [A,D]
C: hashtable [D]
D: hashtable [A,B,C,E]
hashtable [D] 44
COSC 3
36
E:
Sparse adjacency matrix
Constant time lookup
Space efficient
Not good for dense graphs, why?
A
B
D
C
E
A: hashtable [B,D]
B: hashtable [A,D]
C: hashtable [D]
D: hashtable [A,B,C,E]
hashtable [D] 45
COSC 3
36
E:
Weighted graphs
Adjacency list
• store the weight as an additional field in the list
A:
B:8
D:3
8 B
A
3
13 2
D 10
E
C
COSC 336 46
Weighted graphs
Adjacency matrix
aij weight if(i,j)E
8 B
A
3
otherwise
ABCDE A∞8∞3∞
B8∞∞2∞ C ∞ ∞ 010 ∞ D 3 2 10 ∞ 13 E∞∞ ∞13∞
13 2
D 10
E
C
COSC 336
47
Graph algorithms which we’ll cover
• Topological sorting of a DAG
• Graph traversal (BFS, DFS)
• Shortest path from a to b • unweighted
• weighted positive weights • negative/positive weights
• Minimum spanning trees • Flows in networks
COSC 336 48
Topological Sort
Givenagraph,G = (V, E),outputallthe vertices in V such that no vertex is output before any other vertex with an edge to it.
call taxi
pack bags
reserve flight
check in airport
taxi to airport
take flight
locate gate
COSC 336
49
Topological Sort
call pack taxi to reserve check in
locate take gate flight
taxi bags airport flight
airport
COSC 336
50
Topo-Sort Take One
Label each vertex’s in-degree (# of inbound edges) While there are vertices remaining
Pick a vertex with in-degree of zero and output it Reduce the in-degree of all vertices adjacent to it Remove it from the list of vertices
runtime: O(|V|2)
COSC 336 51
Topo-Sort Take Two
Label each vertex’s in-degree
Initialize a queue to contain all in-degree zero vertices
While there are vertices remaining in the queue
Remove a vertex v with in-degree of zero and output it Reduce the in-degree of all vertices adjacent to v
Put any of these with new in-degree zero on the queue
runtime: O(|V| + |E|)
Can we use a stack instead of a queue ?
COSC 336 52
Topo-Sort
• Topo-Sort takes linear time: O(|V|+|E|)
COSC 336 53
Recall: Tree Traversals
a
bcd fg
e hij
kl
abfgkcdhilje
COSC 336 54
Depth-First Search
• Pre/Post/In – order traversals are examples of depth-first search
• Nodes are visited deeply on the left-most branches before any nodes are visited on the right-most branches
• Visitingtherightbranchesdeeplybeforetheleftwouldstillbe depth-first! Crucial idea is “go deep first!”
• In DFS the nodes “being worked on” are kept on a stack
COSC 336 55
DFS(not quite right)
void DFS(Node startNode) { Stack s = new Stack;
s.push(startNode);
while (!s.empty()) { x = s.pop();
/* process x */
for y in x.children() do
s.push(y); }
COSC 336 56
DFS on Trees
a
a
b
f
g
bcd fg
e hij
k
kl
COSC 336 57
DFS on Graphs
a
a
b
f
g
bcd fg
e hij
a
Problem with cycles: may run into an infinite loop
kl
COSC 336 58
DFS- for connected graphs
Running time:
O(|V| + |E|)
Key observation: each node enters the stack at most its indegree times
59
for v in Nodes do v.visited = false;
DFS(startNode);
void DFS(Node v) { Stack s = new Stack; s.push(v);
while (!s.empty()) {
x = s.pop();
if (!x.visited) {
x.visited = true;
process( x ) }
for y in x.children() do
if (!y.visited) s.push(y);
}
COSC 336
DFS- for general graphs
for v in V do
v.visited = false;
for v in V do
if (!v.visited) DFS(v);
COSC 336
60
Running time:
Breadth-First Search
• Traversing tree level by level from top to bottom
(alphabetic order)
a
bcd fg
e hij
kl
COSC 336
61
Breadth-First Search
BFS characteristics
• Nodes being worked on maintained in a FIFO Queue, not a stack
• Iterative style procedures often easier to design than recursive procedures
COSC 336 62
Breadth-First Search- for connected graphs
for v in Nodes do v.visited = false;
DFS(startNode);
void DFS(Node v) { Stack s = new Stack; s.push(v);
while (!s.empty()) {
x = s.pop(); if (!x.visited)
x.visited = true; process (x)
for y in x.children() do if (!y.visited) s.push(y);
}
for v in Nodes do v.visited = false;
BFS(startNode);
void BFS(Node v) { Queue s = new Queue; s.enqueue(startNode); while (!s.empty()) {
x = s.dequeue(); if (!x.visited)
x.visited = true; process (x)
for y in x.children() do
if (!y.visited) s.enqueue(y); }
COSC 336 63
QUEUE
a
bcde cdefg defg efghij fghij ghij hijk ijk
jkl
kl
l
a
bcd fg
e hij
kl
COSC 336
64
Graph Traversals
DFS and BFS
• Either can be used to determine connectivity: • Is there a path between two given vertices?
• Is the graph (weakly) connected?
• Important difference: Breadth-first search always finds a shortest path from the start vertex to any other (for unweighted graphs)
• Depth first search may not!
COSC 336 65
Breadth First Search (BFS) on Trees
COSC 336 66
Tree BFS
A BDE
CFG
Q:
COSC 336
67
Tree BFS
A BDE
CFG
Q:A
COSC 336
68
Tree BFS
A
BDE CFG
Q:
COSC 336
69
Tree BFS
A
BDE CFG
Q: B, D, E
COSC 336
70
Tree BFS
A
BDE CFG
Q: D, E
COSC 336
71
Tree BFS
A
BDE CFG
Q: D, E, C, F
COSC 336
72
Tree BFS
A BDE
CFG
Q: E, C, F
COSC 336
73
Tree BFS
Q: E, C, F
A BDE
CFG
Frontier: the set of vertices that have been visited so far
COSC 336 74
Tree BFS
A BDE
CFG
COSC 336
75
Tree BFS
A BDE
CFG
COSC 336
76
Tree BFS
A BDE
CFG
COSC 336
77
Tree BFS
A BDE
CFG
COSC 336
78
Tree BFS
What order does the algorithm traverse the nodes?
BFS traversal visits the nodes in increasing distance from the root
COSC 336 79
Tree BFS
Does it visit all of the nodes?
COSC 336 80
Running time of Tree BFS
Adjacency list
• How many times does it visit each vertex? • How many times is each edge traversed? • O(|V|+|E|)
Adjacency matrix
• For each vertex visited, how much work is done? • O(|V|2)
COSC 336 81