Lecture 11.2

Graph
Course Code: CSC 2106 Course Title: Data Structure (Theory)
Dept. of Computer Science

Faculty of Science and Technology
Lecture No: 11.2 Week No: 11 Semester: Fall 2020-2021

Lecturer: MAHFUJUR RAHMAN, mahfuj@aiub.edu
Lecture Outline
1. Graphs
2. Graph Introduction
3. Graph Applications
4. Graph Representation
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
(a) (b)
a. An undirected graph G having five vertices and six edges.

b. The adjacency-matrix representation of G.
(a) (b)
a. A directed graph G having five vertices and eight edges.

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

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.
(a) (b)
a. An undirected graph G having five vertices and six edges.

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

Books
 “Schaum's Outline of Data Structures with C++”. By John R. Hubbard (Can be

found in university Library)
 “Data Structures and Program Design”, Robert L. Kruse, 3rd Edition, 1996.
 “Data structures, algorithms and performance”, D. Wood, Addison-Wesley, 1993
 “Advanced Data Structures”, Peter Brass, Cambridge University Press, 2008
 “Data Structures and Algorithm Analysis”, Edition 3.2 (C++ Version), Clifford A.
Shaffer, Virginia Tech, Blacksburg, VA 24061 January 2, 2012
 “C++ Data Structures”, Nell Dale and David Teague, Jones and Bartlett Publishers,
2001.
 “Data Structures and Algorithms with Object-Oriented Design Patterns in C++”,
Bruno R. Preiss,
References
1. https://en.wikipedia.org/wiki/Data_structure

Lecture 11.2

Uploaded by

Copyright:

Available Formats

Lecture 11.2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture 11.2

Uploaded by

Copyright:

Available Formats

Graph

Course Code: CSC 2106 Course Title: Data Structure (Theory)

Dept. of Computer Science

Lecture No: 11.2 Week No: 11 Semester: Fall 2020-2021

Directed Undirected Acyclic

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

An undirected graph G = (V, E), where

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

Dense graph: When the number of edges in the graph is close to

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

DAG: Directed acyclic graphs

Connected Component: equivalence classes of vertices under “is reachable

 State-space search in Artificial Intelligence

Vertex = city, edge = communication link.

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

Some streets are one way.

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

Storage requirements: O(n2)

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

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

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

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

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

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

 “Schaum's Outline of Data Structures with C++”. By John R. Hubbard (Can be

You might also like