Scribd
Upload
24 views

Module 2 - Graph

The document defines key concepts related to graphs including: - A graph consists of vertices connected by edges and can be directed or undirected. - Key graph terms include adjacent nodes, paths, degrees of vertices, and graph size. - Graphs can be represented using adjacency matrices or adjacency lists. - Common graph traversal algorithms are breadth-first search (BFS) and depth-first search (DFS). - Minimum spanning tree and shortest path algorithms like Prim's, Kruskal's and Dijkstra's are used to find minimum cost trees and paths in graphs.

Uploaded by

lejmcguzansveuykbu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
24 views

Module 2 - Graph

The document defines key concepts related to graphs including: - A graph consists of vertices connected by edges and can be directed or undirected. - Key graph terms include adjacent nodes, paths, degrees of vertices, and graph size. - Graphs can be represented using adjacency matrices or adjacency lists. - Common graph traversal algorithms are breadth-first search (BFS) and depth-first search (DFS). - Minimum spanning tree and shortest path algorithms like Prim's, Kruskal's and Dijkstra's are used to find minimum cost trees and paths in graphs.

Uploaded by

lejmcguzansveuykbu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 35

GRAPH

DR. AMRITA SARKAR


Graph
In this graph,
V(G)= {a, b, c, d, e}
E(G)= { (a,b), (a,c), (b,d), (c,d), (d,e)}

• A graph is a pictorial representation of a set of objects where some pairs of objects are
connected by links. The interconnected objects are represented by points termed as vertices, and
the links that connect the vertices are called edges.

• Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges,
connecting the pairs of vertices.
Directed vs. Undirected graphs
• When the edges in a graph have no direction, the graph is called undirected.

• When the edges in a graph have a direction, the graph is called directed (or digraph)
Graph Terminologies
• Adjacent nodes or neighbours: two nodes are adjacent if they are
connected by an edge

• Path: a sequence of vertices that connect two nodes in a graph

• Complete graph: a graph in which every vertex is directly connected to


every other vertex

• Degree of a vertex or node: The degree of a vertex in a graph is the


number of edges that touch it.

• Size of a Graph: The size of a graph is the number of vertices that it


has.
Adjacency Matrix
Adjacency Matrix (Sequential
Representation)
Adjacency Matrix
Power of Adjacency Matrix
Path Matrix or Reachability Matrix
Adjacency List
Preparation
Graph Traversal Algorithm
Breadth First Search (BFS)
Breadth
First Search
(BFS)
Write DFS &
BFS of
following
Graph
Procedure BFS (Vertex V)
Procedure BFS (Vertex V)
Depth First
Search
(DFS)
Depth First
Search
(DFS)
Procedure DFS (Vertex V)
Procedure DFS (Vertex V)
Spanning Tree
Construct
Spanning
Tree
Construct
Spanning
Tree
Minimum Cost Spanning Tree
Prim’s
Algorithm
Kruskal’s
Algorithm
Construct
Minimum
Spanning
Tree
Shortest Path Algorithm
Dijkstra’s
Algorithm-
Shortest
Path
Dijkstra’s
Algorithm-
Shortest
Path
Dijkstra’s
Algorithm-
Shortest
Path
Dijkstra’s
Algorithm
- Shortest
Path
Dijkstra’s
Algorithm
- Shortest
Path
Shortest
Path
THANK YOU

You might also like