GRAPHS

1
 Definition
● A graph, G=(V, E), consists of two sets:
⚪a finite set of vertices(V), and
⚪a finite, possibly empty set of edges(E)
⚪V(G) and E(G) represent the sets of vertices and
edges of G, respectively
● Undirected graph
⚪The pairs of vertices representing any edges is
unordered
⚪e.g., (v0, v1) and (v1, v0) represent the same edge
● Directed graph (v0, v1) = (v1,v0)
⚪Each edge as a directed pair of vertices
⚪e.g. <v0, v1> represents an edge, v0 is the tail and v1 is
the head <v0, v1> != <v1,v0>
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>}
complete undirected graph: n(n-1)/2 edges
complete directed graph: n(n-1) edges
3
 Complete Graph
● A complete graph is a graph that has the
maximum number of edges
⚪for undirected graph with n vertices, the
maximum number of edges is n(n-1)/2
⚪for directed graph with n vertices, the maximum
number of edges is n(n-1)
⚪example: G1 is a complete graph

4
 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

5
Example of a graph with feedback loops and a
multigraph
0

0 2 1 3

1 2
self edge multigraph:
(a) (b) multiple occurrences
of the same edge

6
 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

7
 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
8

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 9
 connected

0 0

1 2 1 2
3
3 4 5 6
G1
G2
tree (acyclic graph)

10
 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.

11
A graph with two connected components
connected component (maximal connected subgraph)

H H 4
0
1 2

2 1 5

3 6

12
Strongly connected components of G3
strongly connected component
not strongly connected (maximal strongly connected subgraph)

0
0 2

1
2
G3

13
 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

14
 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
G3 15
 0

1 2

● Adjacency matrices G1

● Adjacency lists
● Adjacency multilists
0

1
0 4

2
2 1 5 6
G3
3 7
16
G4
 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

17
 Examples for Adjacency Matrix
0 0 4
0
2 1 5
1 2
3 6
3 1
7
2

G2
G1

symmetric

18

G4
 Merits of Adjacency Matrix

● From the adjacency matrix, to determine

the connection of vertices is easy
● The degree of a vertex is
● For a digraph, the row sum is the
out_degree, while the column sum is the
in_degree

19
 Adjacency lists
0
1
● n linked list
1
#define MAX_VERTICES 50 2 0
typedef struct node *node_ptr;
typedef struct node { 2

int vertex; G3
node_ptr link;
} node;
3 1 2
node_ptr graph[MAX_VERTICES]; 0
int n = 0; /* number of nodes */ 2 3 0
1 2
1 3 0
3
0 1 2
G1 20
 Interesting 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

21
 0

1 2
Adjacency multilists 3

G1
m vertex1 vertex2 list1 list2 N0 0 1 N1 N3

N1 0 2 N2 N3
typedef struct edge *edge_ptr;
Typedef struct edge {
int marked; N2 0 3 NIL N4
int vertex1;
int vertex2;
edge_ptr path1; N3 1 2 N4 N5
edge_ptr path2;
} edge; N4 1 3 NIL N5
edge_ptr graph[MAX_VERTICES];

N5 2 3 NIL NIL
22
 Some Graph Operations
● Traversal
Given G=(V,E) and vertex v, find all w∈V,
such that w connects v.
⚪Depth First Search (DFS)
preorder tree traversal
⚪Breadth First Search (BFS)
level order tree traversal
● Connected Components
● Spanning Trees
23
 Elementary graph operations
Graph G and its adjacency lists
depth first search: v0, v1, v3, v7, v4, v5, v2, v6

breadth first search: v0, v1, v2, v3, v4, v5, v6, v7
24
 Depth First Search
DFS-A(G,s)
for all v in V[G]
visited[v] := false
S := EmptyStack
Push(S,s)
while not Empty(S) {
u := Pop(S)
if not visited[u] {
visted[u] := true
for all w in Adj[u]
if not visited[w]
Push(S,w)
}
}
Adjacency list: O(e)
25
Adjacency matrix: O(n2)
Breadth-First Search
BFS-A(G,s)
for all v in V[G]
visited[v] := false
Q := EmptyQueue
Enqueue(Q,s)
while not Empty(Q) {
u := Dequeue(Q)
if not visited[u]
visted[u] := true
for all w in Adj[u] adjacency list: O(e)
if not visited[w] adjacency matrix:
Enqueue(Q,w)
O(n2)
26