COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 13-3 : Graphs
Giulia Alberini, Fall 2020 Slides adapted from Michael Langer’s
WHAT ARE WE GOING TO DO IN THIS VIDEO?
Graphs
Definitions
EXAMPLE
a
cf
eg
d
b
h
SAME EXAMPLE – DIFFERENT NOTATION
a
cf
d
eg
b
h
WEIGHTED GRAPH
a 7c
d
9 5
eg
4
h
12
f
11 7
2
5 4
b
DEFINITION
A directed graph is a set of vertices 𝑉={𝑣𝑖 ∶ 𝑖∈ {1,…,𝑛}}
and set of ordered pairs of these vertices called edges. 𝐸={𝑣,𝑣 ∶𝑖,𝑗∈{1,…,𝑛}}
In an undirected graph, the edges are unordered pairs.
𝐸= 𝑣,𝑣 ∶𝑖,𝑗∈{1,…,𝑛} 𝑖𝑗
𝑖𝑗
EXAMPLES
Vertices Edges
airports web pages Java objects
EXAMPLES
Vertices Edges
airports flights web pages
Java objects
EXAMPLES
Vertices
airports web pages Java objects
Edges
flights
links (URLs)
EXAMPLES
Vertices
airports web pages Java objects
Edges
flights
links (URLs) references
linked lists
trees
graphs
TERMINOLOGY: “IN DEGREE”
e cf
a
v in degree
a1 b2 c2 d0 e1 f3 g0 h1
d
g
b h
TERMINOLOGY: “OUT DEGREE”
e
a
cf
v out degree
a1 b1 c1 d2 e2 f2 g1 h0
d
g
b h
EXAMPLE: WEBPAGES
e cf
In degree: How many web pages link to some web page (e.g. f ) ?
Out degree: How many web pages does some web page (e.g. f ) link to ?
a
d
g
h
b
TERMINOLOGY: PATH
e cf
A path is a sequence of edges such that the end vertex of one edge is the start vertex of the next edge and no vertex is repeated except maybe first and last.
a
d
g
b h
TERMINOLOGY: PATH
e cf
A path is a sequence of edges such that the end vertex of one edge is the start vertex of the next edge and no vertex is repeated except maybe first and last.
Examples • acfeb
a
d
g
b
h
TERMINOLOGY: PATH
e cf
A path is a sequence of edges such that the end vertex of one edge is the start vertex of the next edge and no vertex is repeated except maybe first and last.
Examples • acfeb • dac
a
d
g
b
h
TERMINOLOGY: PATH
e cf
A path is a sequence of edges such that the end vertex of one edge is the start vertex of the next edge and no vertex is repeated except maybe first and last.
Examples • acfeb • dac
• febf
• …..
a
d
g
b
h
GRAPH ALGORITHMS IN COMP 251 (DIJKSTRA’S ALGORITHM)
Given a graph, what is the shortest (weighted) path between two vertices?
TERMINOLOGY: CYCLE
a
d
g
e
A cycle is a path such that the last vertex is the same as the first vertex.
c
f
b h
TERMINOLOGY: CYCLE
a
d
g
e
A cycle is a path such that the last vertex is the same as the first vertex.
c
f
b
Examples • febf
h
TERMINOLOGY: CYCLE
a
d
g
e
A cycle is a path such that the last vertex is the same as the first vertex.
c
f
b
Examples • febf
• efe
h
TERMINOLOGY: CYCLE
a
d
g
e
A cycle is a path such that the last vertex is the same as the first vertex.
c
f
b
Examples • febf
• efe
• fbf •…
h
“TRAVELLINGSALESMAN” COMP360 -(HAMILTONIANCIRCUIT)
a 11 c 12
Find the shortest cycle that visits all vertices once.
How many potential cycles are there in a graph of n vertices ?
7 7
2
d4g
DIRECTED ACYCLIC GRAPH no cycles
b a
c
Used to capture dependencies.
d
There are three paths from a to d.
DIRECTED ACYCLIC GRAPH no cycles
b a
c
Used to capture dependencies.
d
There are three paths from a to d.
DIRECTED ACYCLIC GRAPH no cycles
b a
c
Used to capture dependencies.
d
There are three paths from a to d.
DIRECTED ACYCLIC GRAPH no cycles
b a
c
Used to capture dependencies.
d
There are three paths from a to d.
MATH
(prereqs for many upper level COMP courses)
240 Disc. Str. 1
222 Cal III
323 Prob.
SYSTEMS (compilers, networks,
distributedsys, concurrency, web,..)
APPLICATIONS (graphics, vision, bioinf,games, machine learning..)
THEORY
(crypto, optimization, game theory, logic, correctness,computability..)
202 Intro Program
206 Software Sys
250 Intro CompSci
223 Linear Alg.
273 Comp. Sys.
303 Software Design
302 Program Lang
251 Data Str & Alg
350 Num. Meth
310 Oper. Sys.
421 Data- bases
424 Artif. Intel.
360 Alg. Design
330 Theory Comp.
GRAPH ADT
addVertex( ), addEdge( ) containsVertex( ), containsEdge( ) getVertex( ), getEdge( ) removeVertex( ), removeEdge( ) numVertices( ), numEdges( )
…
How to implement a Graph class?
A graph is a generalization of a tree, so …
RECALL: HOWTOIMPLEMENTAROOTEDTREEINJAVA?
// alternatively….
class Tree
TreeNode
:
class TreeNode
T element;
ArrayList
TreeNode
} }
class Tree
TreeNode
:
class TreeNode
T element;
TreeNode
TreeNode
}
ADJACENCY LIST
(GENERALIZATION OF CHILDREN FOR GRAPHS)
a
cf
e
v v.adjList
ac bf cf
d a, c
e b, f
f b, e
gh
h
Here each adjacency list is sorted, but that is not always possible (or necessary).
d
g
b
h
HOW TO IMPLEMENT A GRAPH CLASS IN JAVA?
A very basic Graph class:
class Graph
class Vertex
ArrayList
T element; }
}
HOW TO IMPLEMENT A GRAPH CLASS IN JAVA?
class Graph
ArrayList
T element;
boolean visited;
}
class Edge {
Vertex endVertex;
double weight;
: }
}
Note that, unlike a rooted tree, there is no notion of a root vertex in a graph.
HOW TO REFERENCE VERTICES?
class Graph
ArrayList< Vertex
:
class Vertex
}
HOW MANY OBJECTS ?
e f
b
HOW MANY OBJECTS ?
Graph
ArrayList
e f
b
Vertex
Vertex
Vertex
Edge
Edge
Edge
Edge
Edge
ArrayList
ArrayList
ArrayList
ADJACENCY MATRIX
a d
e cf
001000 000001 000001 101000 010001 010010
abcdef
a b c d e f
boolean[][] adjMatrix = new boolean[6][6]
b
Assume we have a mapping from vertex names to 0, 1, …. , n-1.
ADJACENCY MATRIX
loop
a d
abcdef
a b c d e f
boolean[][] adjMatrix = new Boolean[6][6]
e cf
101000 000001 000001 101000 010011 010010
b
Assume we have a mapping from vertex names to 0, 1, …. , n-1.
“DEFINITIONS”
Consider a graph with 𝑛 vertices.
We say that the graph is dense if the number of edges is close to 𝑛2. We say that the graph is sparse if the number of edges is close to 𝑛.
(These are not formal definitions.)
EXERCISE
Would you use an adjacency list or adjacency matrix for each of the following? The graph is sparse e.g. 10,000 vertices and 20,000 edges and we want to use
as little space as possible.
The graph has 10,000 vertices and 20,000,000 edges, and it is important to use as little space as possible.
You need to answer the query areAdjacent() as quickly as possible, no matter how much space you use.
You need to perform operation insertVertex.
You need to perform operation removeVertex.
EXERCISE
Would you use an adjacency list or adjacency matrix for each of the following? The graph is sparse e.g. 10,000 vertices and 20,000 edges and we want to use
as little space as possible.
The graph is dense e.g. 10,000 vertices and 20,000,000 edges, and we want to use as little space as possible.
You need to answer the query areAdjacent() as quickly as possible, no matter how much space you use.
You need to perform operation insertVertex.
You need to perform operation removeVertex.
EXERCISE
Would you use an adjacency list or adjacency matrix for each of the following? The graph is sparse e.g. 10,000 vertices and 20,000 edges and we want to use
as little space as possible.
The graph is dense e.g. 10,000 vertices and 20,000,000 edges, and we want to
use as little space as possible. .
Answer the query areAdjacent() as quickly as possible, no matter how much
space you use.
You need to perform operation insertVertex.
You need to perform operation removeVertex.
EXERCISE
Would you use an adjacency list or adjacency matrix for each of the following? The graph is sparse e.g. 10,000 vertices and 20,000 edges and we want to use
as little space as possible.
The graph is dense e.g. 10,000 vertices and 20,000,000 edges, and we want to
use as little space as possible. .
Answer the query areAdjacent() as quickly as possible, no matter how much
space you use.
Perform operation insertVertex( v ).
You need to perform operation removeVertex.
EXERCISE
Would you use an adjacency list or adjacency matrix for each of the following? The graph is sparse e.g. 10,000 vertices and 20,000 edges and we want to use
as little space as possible.
The graph is dense e.g. 10,000 vertices and 20,000,000 edges, and we want to
use as little space as possible. .
Answer the query areAdjacent() as quickly as possible, no matter how much
space you use.
Perform operation insertVertex( v ).
Perform operation removeVertex( v ).
COMING UP!
Recursive graph traversal depth first
Non-recursive graph traversal depth first
breadth first
In the next videos: More on graphs