0% found this document useful (0 votes)

33 views66 pages

Week 10 (Graphs and Trees)

The document outlines a course on Graphs and Trees, covering fundamental concepts such as graph definitions, types (directed, undirected, acyclic), and representations (adjacency matrix and list). It also discusses graph searching techniques like Depth First Search (DFS) and Breadth First Search (BFS), along with their applications in various fields including AI and telecommunications. Additionally, it provides examples and illustrations to clarify the concepts presented.

Uploaded by

ahasanhabibhira.aiub

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PPTX, PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

33 views66 pages

Week 10 (Graphs and Trees)

Uploaded by

ahasanhabibhira.aiub

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PPTX, PDF, TXT or read online on Scribd

You are on page 1/ 66

Graphs and Trees

Course Code: CSC 2211 Course Title: Algorithms

Dept. of Computer Science

Faculty of Science and Technology

Lecturer No: Week No: 10 Semester: Spring 2019-2020

Lecturer: Md. Mustak Un Nobi, ( [email protected] )
Lecture Outline

• Graph Basics
• Graph Searching
• Depth First Search
• Breadth First Search
• Topological Sort
Graphs
 Graph – mathematical object consisting of a set of:
 V = nodes (vertices, points).
 E = edges (links, arcs) between pairs of nodes.
 Denoted by G = (V, E).
 Captures pair wise relationship between objects.
 Graph size parameters: n = |V|, m = |E|.

V = { 1, 2, 3, 4, 5, 6, 7, 8 }
E = { {1,2}, {1,3}, {2,3}, {2,4}, {2,5}, {3,5}, {3,7}, {3,8},
{4,5}, {5,6} }
n=8
m = 11
Graphs
Undirected Graph: A graph whose edges are unordered pairs of vertices. That is,
each edge connects two vertices where edge (u, v) = edge (v, u).

Directed Graph: A graph whose edges are ordered pairs of vertices. That is, each
edge can be followed from one vertex to another vertex where edge (u, v) goes
from vertex u to vertex v.

Acyclic Graph: A graph with no path that starts and ends at the same vertex.

1 2 1 2 1 2

3 4 3 4 3 4

Directed Undirected Acyclic

graph graph graph
Graph Example

A directed graph G= (V, E), where

V = {1, 2, 3, 4, 5, 6} and
E={ (1,2), (2,2), (2,4), (2,5), (4,1), (4,5), (5,4), (6,3) }.
The edge (2,2) is self loop.
Vertex 5 has in-degree 2 and out-degree 1.
Vertex 4 is adjacent to vertex 5; {1, 5} is adjacent to 4;
3 is not adjacent to any other vertex except 6.
Graph Example
An undirected graph G = (V, E), where
V = {1, 2, 3, 4, 5, 6} and
E = { {1,2}, {1,5}, {2,5}, {3,6}}.
The vertex 4 is isolated.
Vertex 1, 2, 5 has degree 2; vertex 3, 6 has degree 1; vertex 4 has degree 0.
Vertex 3 is adjacent to vertex 6 and vice versa; {1, 5} is adjacent to 2; 4 is not
adjacent to any other vertex.
Graph Introduction
Complete graph: When every vertex is strictly connected to each other. (The number of
edges in the graph is maximum).
Degree of a vertex v: The degree of vertex v in a graph G, written d (v ), is the number of
edges incident to v, except that each loop at v counts twice (in-degree and out-degree for
directed graphs)

A B

F C

E D d(A)=3, d(B)=3,d(C)=2

Complete Graph d(D)=3, d(E)=3,d(F)=2

Graph Introduction
Dense graph: When the number of edges in the graph is close to
maximum. (adjacency matrix is used to store info for this)

Sparse graph: When number of edges in the graph is very few.

(adjacency list is used to store info for this)
Graph Introduction

Weighted graph: associates weights with either the edges or the vertices

DAG: Directed acyclic graphs

Connected: if every vertex of a graph can reach every other vertex, i.e., every
pair of vertices is connected by a path

Strongly connected: every 2 vertices are reachable from each other (in a
digraph)

Connected Component: equivalence classes of vertices under “is reachable

from” relation. Simply put, it is a subgraph in which any two vertices
are connected to each other by paths, and which is connected to no
additional vertices in the supergraph.
Forests, DAG, Components

Weighted Graph
Graph Applications

 State-space search in Artificial Intelligence

 Geographical information systems, electronic street directory
 Logistics and supply chain management
 Telecommunications network design
 Many more industry applications
 The graphic representation of world wide web (www)
 Resource allocation graph for processes that are active in the
system.
 The graphic representation of a map
 Scene graphs: The contents of a visual scene are also managed
by using graph data structure.
Applications—Communication Network

2
3
8
1 10

4
5
9
11

6
7

Vertex = city, edge = communication link.

Applications—Driving Distance/Time Map

2
4 3
8 8
1 6 10
2 4 5
4 4 3
5
9
11
5 6

6 7
7

Vertex = city, edge weight = driving distance/time.

Applications—Street Map

2
3
8
1 10

4
5
9
11

6
7

Some streets are one way.

Graph Representation

Adjacency matrix: represents a graph as n x n matrix A (here, n is

the number of nodes/ vertices):
A[i, j] = 1 if edge (i, j)  E (or weight of edge)
= 0 if edge (i, j)  E

Storage requirements: O(n2)

Using adjacency matrix is more efficient to represent dense
graphs
 Especially if store just one bit/edge
 Undirected graph: only need half of matrix
Graph Representation

(a) (b)

a. An undirected graph G having five vertices and six edges.

b. The adjacency-matrix representation of G.
Graph Representation

(a) (b)

a. A directed graph G having five vertices and eight edges.

b. The adjacency-matrix representation of G.
Graph Representation

(a) (b)

a. A directed weighted graph G having five vertices and six edges.

b. The adjacency-matrix representation of G.
Graph Representation

Adjacency list: list of adjacent vertices. For each vertex v  V,

store a list of vertices adjacent to v
Storage requirements: O(n+e)
Using adjacency list is more efficient to represent sparse graphs

(a) (b)
a. A directed graph G having five vertices and six edges.
b. The adjacency-list representation of G.
Graph Representation

(a) (b)

a. An undirected graph G having five vertices and six edges.

b. The adjacency-list representation of G.
Graph Representation

(a) (b)

a. A directed weighted graph G having six vertices and seven edges.

b. The adjacency-list representation of G.
Graph Searching
 Given: a graph G = (V, E), directed or undirected
 Goal: methodically explore every vertex and edge
 Ultimately: build a tree on the graph
 Pick a vertex as the root
 Choose certain edges to produce a tree
 Note: might also build a forest if graph is not connected

 Breadth-first search
 Depth-first search
 Other variants: best-first, iterated deepening search, etc.
Depth-First Search (DFS)
 Explore “deeper” in the graph whenever possible
 Edges are explored out of the most recently discovered vertex v that still has
unexplored edges (LIFO)
 When all of v’s edges have been explored, backtrack to the vertex from which
v was discovered
 computes 2 timestamps: d[ ] (discovered) and f[ ] (finished)
 builds one or more depth-first tree(s) (depth-first forest)

 Algorithm colors each vertex

 WHITE: undiscovered
 GRAY: discovered, in process
 BLACK: finished, all adjacent vertices have been discovered
Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{
{ color[u] = GREY; 
for each vertex uV time = time+1;
color[u] = WHITE; d[u] = time; // compute d[]
time = 0; for each v adjacent to u
for each vertex uV if (color[v] == WHITE)
if (color[u] == WHITE) p[v]= u // build tree
DFS_Visit(u); DFS_Visit(v);
color[u] = BLACK;
} time = time+1;
f[u] = time; // compute f[]
}
DFS Classification of Edges

 DFS can be used to classify edges of G:

1. Tree edges: edges in the depth-first forest.
2. Back edges: edges (u, v) connecting a vertex u to
an ancestor v in a depth-first tree.
3. Forward edges: non-tree edges (u, v) connecting
a vertex u to a descendant v in a depth-first tree.
4. Cross edges: all other edges.

 DFS yields valuable information about the

structure of a graph.
Operations of DFS
u v w
Undiscovered

Discovered,
On Process

Finished, all
adjacent vertices x y z
have been
discovered

Discover time/ Finish time

Operations of DFS
u v w
Undiscovered 1/

Discovered,
On Process

Finished, all
adjacent vertices x y z
have been
discovered