Graphs

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),
c (a,d),
(b,e),(c,d),(c,e),
(d,e)}
d e
Applications
CS16
electronic circuits

networks (roads, flights,

communications)

JFK

LAX STL
HNL
DFW
FTL
Terminology:
Adjacent and Incident
If (v0, v1) is an edge in an undirected
graph,
v0 and v1 are adjacent
The edge (v0, v1) is incident on vertices v0
and v1
If <v0, v1> is an edge in a directed
graph
v0 is adjacent to v1, and v1 is adjacent from
v0
The edge <v0, v1> is incident on v0 and v1
Terminology:
Degree of a Vertex
The degree of a vertex is the number of
edges incident to that vertex
For directed graph,
the in-degree of a vertex v is the number of
edges
that have v as the head
the out-degree of a vertex v is the number of
edges
that have v as the tail
if di is the degree of a vertex i in a graph G
with nn vertices
1 and e edges, the number of
Why? Since adjacent vertices each
edges
e (  0
is
i
d )/ 2 count the adjoining edge, it will be
counted twice
Examples
0
3 2
0 1 2
3 3
3 1 2 3 3 4 5 6
3G1 1 1 G2 1 1
3
0 in:1, out: 1
directed graph
in-degree
out-degree 1 in: 1, out: 2

2 in: 1, out: 0
G3
Terminology:
Path
path: sequence of
3 2
vertices v1,v2,. . .vk
such that
consecutive vertices 3
vi and vi+1 are
adjacent. 3 3

a b a b

c c

d e d e
abedc bedc
7
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
a b

acda
c

d e
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.
Subgraphs Examples
0
0 0 1 2 0
1 2
1 2 3 1 2
3
G1 (i) (ii) (iii) 3(iv)
(a) Some of the subgraph of G1
0
0 0 0 0

1 1 1 1

2 2 2
(i) (ii) (iii) (iv)
(b) Some of the subgraph of G3
G3
More…

tree - connected graph without cycles

forest - collection of trees

tree

tree

forest

tree

tree
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

n 
5
m (5 
More Connectivity

n = #vertices
n 5
m = #edges m 4
For a tree m = n - 1
If m < n - 1, G is
not connected

n 5
m 3
Oriented (Directed) Graph
A graph where edges are directed
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
ADT for Graph
objects: a nonempty set of vertices and a set of undirected edges,
where each
edge is a pair of vertices
functions: for all graph  Graph, v, v1 and v2  Vertices
Graph Create()::=return an empty graph
Graph InsertVertex(graph, v)::= return a graph with v inserted. v
has no
incident edge.
Graph InsertEdge(graph, v1,v2)::= return a graph with new edge
between v1 and v2
Graph DeleteVertex(graph, v)::= return a graph in which v and
all edges
incident to it are removed
Graph DeleteEdge(graph, v1, v2)::=return a graph in which the
edge (v1, v2)
is removed
Boolean IsEmpty(graph)::= if (graph==empty graph) return
TRUE
else return FALSE
List Adjacent(graph,v)::= return a list of all vertices that are
Graph Representations

Adjacency Matrix
Adjacency Lists
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 gra
is symmetric; the adjacency matrix for a
digraph
Examples for Adjacency Matrix
0 0 4
0
2 1 5
1 2
3 6
3 1
0 1 1 1  0 1 0
1 0 1 1    7
  1 0 1 
2 0 1 1 0 0 0 0 0
1 1 0 1  0 0 0 1
   0 0 1 0 0 0 0
1 1 1 0
1 0 0 1 0 0 0 0
G2
G1  
0 1 1 0 0 0 0 0
0 0 0 0 0 1 0 0
 
0 0 0 0 1 0 1 0
symmetric 0 0 0 0 0 1 0 1
 
undirected: n2/2  0 0 0 0 0 0 1 0
directed: n2
G4
Merits of Adjacency Matrix

From the adjacency matrix, to determine

the connection of vertices is easy
n 1

The degree of a vertex isadj _ mat[i][ j ]

j 0
For a digraph (= directed graph), the row
sum is the out_degree, while the column
sum is the in_degree
n 1 n 1
ind (vi )  A[ j , i ] outd (vi )  A[i , j ]
j 0 j 0
Adjacency Lists (data
structures)
Each row in adjacency matrix is represented as an adjacency list.

#define MAX_VERTICES 50
typedef struct node *node_pointer;
typedef struct node {
int vertex;
struct node *link;
};
node_pointer graph[MAX_VERTICES];
int n=0; /* vertices currently in use */
0 0 4
2 1 5
1 2 3 6
3 7
0 1 2 3 0 1 2
1 0 2 3 1 0 3
2 0 1 3 2 0 3
3 0 1 2 3 1 2
G1 0 4 5
5 4 6
0 1 6 5 7
1 0 2 1
7 6
2
G3 G4
2
An undirected graph with n vertices and e edges ==> n head nodes and 2e list nodes
Some Operations
degree of a vertex in an undirected graph
–# of nodes in adjacency list
# of edges in a graph
–determined in O(n+e)
out-degree of a vertex in a directed graph
–# of nodes in its adjacency list
in-degree of a vertex in a directed graph
–traverse the whole data structure
Graph Traversal
Problem: Search for a certain node or
traverse all nodes in the graph
Depth First Search
Once a possible path is found, continue the
search until the end of the path
Breadth First Search
Start several paths at a time, and advance
in each one step at a time
Depth-First Search
A B C D

E F G H

I J K L

M N O P
Exploring a Labyrinth
Without Getting Lost
A depth-first search (DFS) in an undirected graph G
is like wandering in a labyrinth with a string and a can
of red paint without getting lost.
We start at vertex s, tying the end of our string to the
point and painting s “visited”. Next we label s as our
current vertex called u.
Now we travel along an arbitrary edge (u, v).
If edge (u, v) leads us to an already visited vertex v we
return to u.
If vertex v is unvisited, we unroll our string and move to
v, paint v “visited”, set v as our current vertex, and
repeat the previous steps.
Depth-First Search

Algorithm DFS(v); Input: A vertex v in a graph

Output: A labeling of the edges as “discovery” edges and
“backedges”
for each edge e incident on v do
if edge e is unexplored then let w be the other
endpoint of e
if vertex w is unexplored then label e as a discovery
edge
recursively call DFS(w)
else label e as a backedge
Breadth-First Search

Like DFS, a Breadth-First Search (BFS) traverses a connected

component of a graph, and in doing so defines a spanning tree
with several useful properties.
The starting vertex s has level 0, and, as in DFS, defines that
point as an “anchor.”
In the first round, the string is unrolled the length of one
edge, and all of the edges that are only one edge away from
the anchor are visited.
These edges are placed into level 1
In the second round, all the new edges that can be reached by
unrolling the string 2 edges are visited and placed in level 2.
This continues until every vertex has been assigned a level.
The label of any vertex v corresponds to the length of the
shortest path from s to v.

28
BFS - A Graphical
Representation
0 0 1

A B C D A B C D

a) E F G H E F G H b)

I J K L I J K L

M N O P M N O P
0 1 2
0 1 2 3
A B C D B C D
A
c) d)
E F G H E F G H

I J K L
I J K L

M N O P
M N O P
29
More BFS

0 1 2 3 0 1 2 3

A B C D A B C D

E F G H E F G H

4 4
I J K L I J K L

M N O P M N O P 5
BFS Pseudo-Code

Algorithm BFS(s): Input: A vertex s in a graph

Output: A labeling of the edges as “discovery” edges and “cross
edges”
initialize container L0 to contain vertex s
i0
while Li is not empty do
create container Li+1 to initially be empty
for each vertex v in Li do
if edge e incident on v do
let w be the other endpoint of e
if vertex w is unexplored then
label e as a discovery edge
insert w into Li+1
else label e as a cross edge
ii+1
31
Applications: Finding a Path

Find path from source vertex s to

destination vertex d
Use graph search starting at s and
terminating as soon as we reach d
Need to remember edges traversed
Use depth – first search ?
Use breath – first search?
DFS vs. BFS

F B A start
DFS Process E

G D C
destination

C DFS on C D Call DFS on D

B DFS on B B B Return to call on B
A DFS on A A A A

G Call DFS on G found destination - done!

D Path is implicitly stored in DFS recursion
B Path is: A, B, D, G
A
DFS vs. BFS

F B A start
E
BFS Process
G D C
destination

rear front rear front rear front rear front

A B D C D
Initial call to BFS on A Dequeue A Dequeue B Dequeue C
Add A to queue Add B Add C, D Nothing to add
rear front

G found destination - done!

Dequeue D Path must be stored separately
Add G