Prestige Institute of Engineering, Management &

Research, Indore

Department of Computer Science & Engineering

Subject: Data Structure [CS-303]

Lecture No.
:
Topic
: Graph Introduction

By: Dr. Aradhana Negi, Department of Computer Science & Engineering, PIEMR, Indore
Unit-II Syllabus
● Graphs: Introduction
● Classification of graph: Directed and Undirected graphs, etc
● Graph Representation
● Graph Traversal: Depth First Search (DFS), Breadth First Search
(BFS)
● Graph algorithm: Minimum Spanning Tree (MST)
● Kruskal’s Algorithm
● Prim’s Algorithm
● Dijkstra’s shortest path algorithm
● Comparison between different graph algorithms
● Application of graphs

By: Dr. Aradhana Negi, Department of Computer Science & Engineering, PIEMR, Indore
Pedagogy Used

Analogy-Based Learning
Socratic Method or Inquiry-Based Learning

By: Dr. Aradhana Negi, Department of Computer Science & Engineering, PIEMR, Indore
Graph

● Graph is a non-linear data structure which finds its application in various

engineering domains.
● It consists of vertices (nodes) and edges.
● A vertex, also called a node, is a point or an object in the Graph, and an edge
is used to connect two vertices with each other.
● It is non-linear because the data structure allows us to have different paths to
get from one vertex to another, unlike with linear data structures like Arrays or
Linked Lists.

By: Dr. Aradhana Negi, Department of Computer Science & Engineering, PIEMR, Indore
Graph Formal Definition

A graph is a collection of vertices (nodes) and edges (connections), where the

edges represent relationships between the vertices. Formally, a graph G is defined
as:

G=(V,E)

Where:
● V is the set of vertices (nodes).
● E is the set of edges, which are pairs of vertices representing the connections
between them.

By: Dr. Aradhana Negi, Department of Computer Science & Engineering, PIEMR, Indore
Where Graphs are used?

Graphs are used to represent and solve problems where the data consists
of objects and relationships between them, such as:
● Social Networks: Each person is a vertex, and relationships (like
friendships) are the edges. Algorithms can suggest potential friends.
● Maps and Navigation: Locations, like a town or bus stops, are stored
as vertices, and roads are stored as edges. Algorithms can find the
shortest route between two locations when stored as a Graph.
● Internet: Can be represented as a Graph, with web pages as vertices
and hyperlinks as edges.
● Biology: Graphs can model systems like neural networks or the spread
of diseases.

By: Dr. Aradhana Negi, Department of Computer Science & Engineering, PIEMR, Indore
Types of Graphs

1. Undirected Graph
2. Directed Graph
3. Weighted Graph
4. Unweighted Graph
5. Connected Graph
6. Complete Graph
7. Incomplete Graph

By: Dr. Aradhana Negi, Department of Computer Science & Engineering, PIEMR, Indore
Directed and Undirected Graph

Directed Graph: A graph where the connections between

nodes have a specific direction, like one-way streets.

Undirected Graph: A graph where the connections between

nodes can be traveled in both directions.

By: Dr. Aradhana Negi, Department of Computer Science & Engineering, PIEMR, Indore
Weighted and Unweighted Graph

Weighted Graph: A graph where connections between

nodes have a value, such as the distance or time required to
travel.
Unweighted Graph: A graph where connections between
nodes are either present or absent, without any associated
value.

By: Dr. Aradhana Negi, Department of Computer Science & Engineering, PIEMR, Indore
Complete and Incomplete Graph

Complete Graph: A graph in which each vertex is connected

to every other vertex.

Incomplete Graph: A graph in which each vertex is not

connected to every other vertex.

By: Dr. Aradhana Negi, Department of Computer Science & Engineering, PIEMR, Indore
Bipartite Graphs

A graph in which the vertices can be divided into two

disjoint sets such that every edge connects a vertex in one
set to a vertex in the other set. Example: A job applicant
graph where the vertices can be divided into job applicants
and job openings.

By: Dr. Aradhana Negi, Department of Computer Science & Engineering, PIEMR, Indore
Terminology of Graph

1. Trees: A connected graph with no cycles. Example: A family tree where each person is
connected to their parents.
2. Cycles: A graph with at least one cycle. Example: A bike-sharing graph where the cycles
represent the routes that the bikes take.

By: Dr. Aradhana Negi, Department of Computer Science & Engineering, PIEMR, Indore
Graph Algorithm

Graph algorithms are methods used to manipulate and analyze

graphs, solving various range of problems like finding the shortest
path, cycles detection.
1. Kruskal’s Algorithm
2. Prim’s Algorithm
3. Dijkstra’s Algorithm

By: Dr. Aradhana Negi, Department of Computer Science & Engineering, PIEMR, Indore
Reference
Text Books (T)
1. AM Tanenbaum, Y Langsam& MJ Augustein, “Data structure using C and C++”, Prentice Hall India.
2. Robert Kruse, Bruse Leung, “Data structures & Program Design in C”, Pearson Education.
Reference Books (R)
3. Aho, Hopcroft, Ullman, “Data Structures and Algorithms”, Pearson Education.
4. N. Wirth, “Algorithms + Data Structure = Programs”, Prentice Hall.
5. Jean – Paul Trembly , Paul Sorenson, “An Introduction to Structure with application”, TMH.
6. Richard, GilbergBehrouz, Forouzan ,“Data structure – A Pseudocode Approach with C”, Thomson
press.

By: Dr. Aradhana Negi, Department of Computer Science & Engineering, PIEMR, Indore