What is a Graph?
A graph G = (V,E) is composed of:
V: set of vertices
E: set of edges connecting the vertices in V
An edge e = (u,v) is a pair of vertices
Example:
a b V= {a,b,c,d,e}
E= {(a,b),(a,c),(a,d),
c (b,e),(c,d),(c,e),
(d,e)}
d e
1
Applications
electronic circuits CS16
networks (roads, flights, communications)
JFK
LAX STL
HNL
DFW
FTL 2
Examples
0
3 2
0 1 2
3 3
3 1 2 3 3 4 5 6
3G13 1 1 G2 1 1
0 in:1, out: 1
directed graph
in-degree
out-degree 1 in: 1, out: 2
2 in: 1, out: 0
G3
3
Terminology:
Path
path: sequence of vertices v1,v2,. . .vk
3 2
such that consecutive vertices vi and
vi+1 are adjacent.
3
3 3
a b a b
c c
d e d e
abedc bedc
4
More Terminology
simple path: no repeated vertices
a b
bec
c
d e
cycle: simple path, except that the last vertex is the same as the first vertex
5
Even More Terminology
• connected graph: any two vertices are connected by some path
connected not connected
subgraph: subset of vertices and edges forming a graph
connected component: maximal connected subgraph. E.g., the graph below has 3 connected
components.
6
Subgraphs Examples
0 0 1 2 0
0
1 2 3 1 2
1 2
3 3
G1 (i) (ii) (iii) (iv)
(a) Some of the subgraph of G1
0
0 0 0 0
1 1 1 1
2 2 2
(i) (ii) (iii) (iv)
G3 (b) Some of the subgraph of G3
7
More…
tree - connected graph without cycles
forest - collection of trees
8
Connectivity
Let n = #vertices, and m = #edges
A complete graph: one in which all pairs of vertices are adjacent
How many total edges in a complete graph?
● Each of the n vertices is incident to n-1 edges, however, we would have
counted each edge twice! Therefore, intuitively, m = n(n -1)/2.
Therefore, if a graph is not complete, m < n(n -1)/2
9
More Connectivity
n = #vertices
m = #edges
For a tree m = n - 1
If m < n - 1, G is
not connected
10
Directed vs. Undirected Graph
An undirected graph is one in which the pair of vertices in a edge is
unordered, (v0, v1) = (v1,v0)
A directed graph is one in which each edge is a directed pair of
vertices, <v0, v1> != <v1,v0>
tail head
11
Graph Representations
Adjacency Matrix
Adjacency Lists
12
Adjacency Matrix
Let G=(V,E) be a graph with n vertices.
The adjacency matrix of G is a two-dimensional
n by n array, say adj_mat
If the edge (vi, vj) is in E(G), adj_mat[i][j]=1
If there is no such edge in E(G), adj_mat[i][j]=0
The adjacency matrix for an undirected graph is symmetric; the adjacency
matrix for a digraph need not be symmetric
13
Examples for Adjacency Matrix
0 0 4
0
2 1 5
1 2
3 6
3 1
7
2
G2
G1
symmetric
undirected: n2/2
directed: n2
G4 14
Graphs: Adjacency List
● Adjacency list: for each vertex v ∈ V, store a list of vertices
adjacent to v
● Example:
● Adj[1] = {2,3} 1
● Adj[2] = {3}
● Adj[3] = {}
● Adj[4] = {3} 2 4
3
GRAPH ------- DEPTH FIRST TRAVERSAL
16
GRAPH ------- DEPTH FIRST TRAVERSAL
Algorithm
Algorithm DFS(G, u){
[Link] = true
for each v ∈ [Link][u]{
if [Link] == false
DFS(G,v)
}
}
17
GRAPH ------- BREADTH FIRST TRAVERSAL
18
GRAPH ------- BREADTH FIRST TRAVERSAL
Algorithm
Algorithm BFS(G){
create a queue Q
mark v as visited and put v into Q
while Q is non-empty {
remove the head u of Q
mark and enqueue all (unvisited) neighbours of u
}
}
19