Lecture 6: GRAPHS
1
Definition
A graph G consists of two sets
– a finite, nonempty set of vertices V(G)
– a finite, possible empty set of edges E(G)
– G(V,E) represents a 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
2
Examples for Graph
0 0 0
1 2 1 2
1
3
3 4 5 6
G1 2
G2
complete graph incomplete graph G3
V(G1)={0,1,2,3} E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}
V(G2)={0,1,2,3,4,5,6} E(G2)={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)}
V(G3)={0,1,2} E(G3)={<0,1>,<1,0>,<1,2>}
A complete graph is a graph that has the max number of edges
complete undirected graph: n(n-1)/2 edges 3
complete directed graph: n(n-1) edges
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
4
A graph with feedback loops and a multi-graph
0 2 1 3
1 2
self edge multigraph:
(a) (b) multiple occurrences
of the same edge
Figure 6.3
5
Subgraph and Path
A subgraph of G is a graph G’ such that V(G’)
is a subset of V(G) and E(G’) is a subset of E(G)
A path from vertex vp to vertex vq in a graph G,
is a sequence of vertices, vp, vi1, vi2, ..., vin, vq,
such that (vp, vi1), (vi1, vi2), ..., (vin, vq) are edges
in an undirected graph
The length of a path is the number of edges on
it
6
Figure 6.4: subgraphs of G1 and G3 (p.261)
0 0 0 1 2 0
1 2 1 2 3 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
(i) (ii) (iii) (iv)
2 (b) Some of the subgraph of G3
7
G3
Simple Path and Style
A simple path is a path in which all vertices,
except possibly the first and the last, are distinct
A cycle is a simple path in which the first and
the last vertices are the same
In an undirected graph G, two vertices, v0 and v1,
are connected if there is a path in G from v0 to v1
An undirected graph is connected if, for every
pair of distinct vertices vi, vj, there is a path
from vi to vj
8
tree (acyclic graph)
connected
0 0
1 2 1 2
3
3 4 5 6
G1
G2
9
Connected Component
A connected component of an undirected graph
is a maximal connected subgraph.
A tree is a graph that is connected and acyclic.
A directed graph is strongly connected if there
is a directed path from vi to vj and also
from vj to vi.
A strongly connected component is a maximal
subgraph that is strongly connected.
10
Degree
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 n
vertices and e edges, the number of edges is
n 1
e( d )/ 2
0
i
11
undirected graph
degree
3 0
0 2
1 2
3 1 2 3 3 3
3 4 5 6
3
G13 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
12
G3
ADT for Graph
structure Graph is
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 adjacent to v
13
Graph Representations
Adjacency Matrix
Adjacency Lists
14
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
15
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
16
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 is
adj _ mat[i][ j]
j 0
For a digraph, 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
17
Data Structures for Adjacency Lists
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 */
18
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 19
An undirected graph with n vertices and e edges ==> n head nodes and 2e list nodes
Graph Operations
Traversal
Given G=(V,E) and vertex v, find all wV,
such that w connects v.
– Depth First Search (DFS)
– Breadth First Search (BFS)
Connected Components
Spanning Trees
20
*Figure 6.19:Graph G and its adjacency lists (p.274)
depth first search: v0, v1, v3, v7, v4, v5, v2, v6
breadth first search: v0, v1, v2, v3, v4, v5, v6, v7
21
Depth First Search
The purpose of the algorithm is to mark each
vertex as visited while avoiding cycles.
The DFS algorithm works as follows:
Step 1: Define a Stack of size total number of vertices in
the graph.
Step 2: Select any vertex as starting point for traversal.
Visit that vertex and push it on to the Stack.
Step 3: Visit any one of the adjacent vertex of the vertex
which is at top of the stack which is not visited and push it
on to the stack.
22
Depth First Search
Step 4: Repeat step 3 until there are no new vertex to be
visit from the vertex on top of the stack.
Step 5: When there is no new vertex to be visit then use
back tracking and pop one vertex from the stack.
Step 6: Repeat steps 3, 4 and 5 until stack becomes Empty.
Step 7: When stack becomes Empty, then produce final
spanning tree by removing unused edges from the graph
23
Depth First Search
#define FALSE 0
#define TRUE 1
short int visited[MAX_VERTICES];
void dfs(int v)
{
node_pointer w;
visited[v]= TRUE;
printf(“%5d”, v);
for (w=graph[v]; w; w=w->link)
if (!visited[w->vertex])
dfs(w->vertex); Data structure
} adjacency list: O(e)
adjacency matrix: O(n 2)
24
Breadth First Search
We use the following steps to implement BFS traversal...
Step 1: Define a Queue of size total number of vertices in the graph.
Step 2: Select any vertex as starting point for traversal. Visit that
vertex and insert it into the Queue.
Step 3: Visit all the adjacent vertices of the vertex which is at front of
the Queue which is not visited and insert them into the Queue.
Step 4: When there is no new vertex to be visit from the vertex at fron
of the Queue then delete that vertex from the Queue.
Step 5: Repeat step 3 and 4 until queue becomes empty.
Step 6: When queue becomes Empty, then produce final spanning tre
by removing unused edges from the graph
25
Breadth First Search
typedef struct queue *queue_pointer;
typedef struct queue {
int vertex;
queue_pointer link;
};
void addq(queue_pointer *,
queue_pointer *, int);
int deleteq(queue_pointer *);
26
Breadth First Search (Continued)
void bfs(int v)
{
node_pointer w;
queue_pointer front, rear;
front = rear = NULL;
adjacency list: O(e)
printf(“%5d”, v); adjacency matrix: O(n2)
visited[v] = TRUE;
addq(&front, &rear, v);
27
while (front) {
v= deleteq(&front);
for (w=graph[v]; w; w=w->link)
if (!visited[w->vertex]) {
printf(“%5d”, w->vertex);
addq(&front, &rear, w->vertex);
visited[w->vertex] = TRUE;
}
}
}
28
Spanning Trees
When graph G is connected, a depth first or
breadth first search starting at any vertex will
visit all vertices in G
A spanning tree is any tree that consists solely
of edges in G and that includes all the vertices
E(G): T (tree edges) + N (nontree edges)
where T: set of edges used during search
N: set of remaining edges
29
Examples of Spanning Tree
0 0 0 0
1 2 1 2 1 2 1 2
3 3 3 3
G1 Possible spanning trees
30
Spanning Trees
Either dfs or bfs can be used to create a
spanning tree
– When dfs is used, the resulting spanning tree is
known as a depth first spanning tree
– When bfs is used, the resulting spanning tree is
known as a breadth first spanning tree
While adding a nontree edge into any spanning
tree, this will create a cycle
31
DFS VS BFS Spanning Tree
0 0 0
1 2 1 2 1 2
3 4 5 6 3 4 5 6 3 4 5 6
7 7 nontree edge 7
cycle
DFS Spanning BFS Spanning
32
Minimum Spanning Trees
Edges are weighted: find minimum cost
spanning tree
Applications
– Find cheapest way to wire your house
– Find minimum cost to send a message on the
Internet
33
Two Algorithms
Prim: (build tree incrementally)
– Pick lower cost edge connected to known (incomplete)
spanning tree that does not create a cycle and expand to
include it in the tree
Kruskal: (build forest that will finish as a tree)
– Pick lowest cost edge not yet in a tree that does not
create a cycle. Then expand the set of included edges to
include it. (It will be somewhere in the forest.)
34
Prim’s algorithm
1
Starting from empty T, 10
choose a vertex at random 5
and initialize 1
V = {1), E’ ={} 3
8
2 3 4
1 1 6
4
2
6 5
35
Prim’s algorithm
1
Choose the vertex u not in V 10
such that edge weight from u 5
to a vertex in V is minimal 1
(greedy!)
8 3
V={1,3} E’= {(1,3) } 2 3 4
1 1 6
4
2
6 5
36
Prim’s algorithm
Repeat until all vertices have been
1
chosen
10 5
Choose the vertex u not in V such 1
that edge weight from v to a vertex
in V is minimal (greedy!)
8 3
V= {1,3,4} E’= {(1,3),(3,4)} 2 3 4
V={1,3,4,5} E’={(1,3),(3,4),(4,5)}
1 1 6
….
V={1,3,4,5,2,6} 4
E’={(1,3),(3,4),(4,5),(5,2),(2,6)} 2
6 5
37
Prim’s algorithm
Repeat until all vertices have been
1
chosen
10 5
V={1,3,4,5,2,6} 1
E’={(1,3),(3,4),(4,5),(5,2),(2,6)}
8 3
2 3 4
Final Cost: 1 + 3 + 4 + 1 + 1 = 10
1 1 6
4
2
6 5
38
Prim’s Algorithm
Implementation
Assume adjacency list representation
Initialize connection cost of each node to “inf” and “unmark” them
Choose one node, say v and set cost[v] = 0 and prev[v] =0
While they are unmarked nodes
Select the unmarked node u with minimum cost; mark it
For each unmarked node w adjacent to u
if cost(u,w) < cost(w) then cost(w) := cost (u,w)
prev[w] = u
39
Kruskal’s Algorithm
Select edges in order of increasing cost
Accept an edge to expand tree or forest only
if it does not cause a cycle
Implementation using adjacency list,
priority queues and disjoint sets
40
Kruskal’s Algorithm
Initialize a forest of trees, each tree being a single node
Build a priority queue of edges with priority being lowest cost
Repeat until |V| -1 edges have been accepted {
Deletemin edge from priority queue
If it forms a cycle then discard it
else accept the edge – It will join 2 existing trees yielding a larger tree
and reducing the forest by one tree
}
The accepted edges form the minimum spanning tree
41
Detecting Cycles
If the edge to be added (u,v) is such that
vertices u and v belong to the same tree,
then by adding (u,v) you would form a
cycle
– Therefore to check, Find(u) and Find(v). If they
are the same discard (u,v)
– If they are different Union(Find(u),Find(v))
42
Example
1
10 5
1
1
8 3
2 3 4
1 1 6
4
2
6 5
43
Initialization
1
Initially, Forest of 6 trees
F=
{{1},{2},{3},{4},{5},{6}}
2 3 4
Edges in a heap (not shown)
6 5
44
Step 1
1
Select edge with lowest cost
(2,5)
Find(2) = 2, Find (5) = 5
Union(2,5)
2 3 4
F= {{1},{2,5},{3},{4},{6}}
1 edge accepted 1
6 5
45
Step 2
1
Select edge with lowest cost
(2,6)
Find(2) = 2, Find (6) = 6
Union(2,6)
2 3 4
F= {{1},{2,5,6},{3},{4}}
2 edges accepted 1
1
6 5
46
Step 3
1
Select edge with lowest cost
(1,3)
1
Find(1) = 1, Find (3) = 3
Union(1,3)
2 3 4
F= {{1,3},{2,5,6},{4}}
3 edges accepted 1
1
6 5
47
Step 4
1
Select edge with lowest cost
(5,6)
1
Find(5) = 2, Find (6) = 2
Do nothing
2 3 4
F= {{1,3},{2,5,6},{4}}
3 edges accepted 1
1
6 5
48
Step 5
1
Select edge with lowest cost
(3,4)
1
Find(3) = 1, Find (4) = 4
Union(1,4) 3
2 3 4
F= {{1,3,4},{2,5,6}}
4 edges accepted 1
1
6 5
49
Step 6
Select edge with lowest cost 1
(4,5)
Find(4) = 1, Find (5) = 2
1
Union(1,2)
3
F= {{1,3,4,2,5,6}} 2 3 4
5 edges accepted : end
1
Total cost = 10 4
1
Although there is a unique
spanning tree in this
example, this is not generally 6 5
the case
50
Kruskal’s Algorithm Analysis
Initialize forest O(n)
Initialize heap O(m), m = |E|
Loop performed m times
– In the loop one DeleteMin O(log m)
– Two Find, each O(log n)
– One Union (at most) O(1)
So worst case O(m log m) = O(m log n)
51
Time Complexity Summary
Recall that m = |E| = O(V2) = O(n2 )
Prim’s runs in O((n+m) log n)
Kruskal runs in O(m log m) = O(m log n)
In practice, Kruskal has a tendency to run
faster since graphs might not be dense and
not all edges need to be looked at in the
Deletemin operations
52
