Unit III - Graphs
Applications of Graph:
• Transportation Systems: Google Maps employs graphs to map roads, where
intersections are vertices and roads are edges. It calculates shortest paths for
efficient navigation.
• Social Networks: Platforms like Facebook model users as vertices and
friendships as edges, using graph theory for friend suggestions.
• World Wide Web: Web pages are vertices, and links between them are
directed edges, inspiring Google's Page Ranking Algorithm.
• Resource Allocation and Deadlock Prevention: Operating systems use
resource allocation graphs to prevent deadlocks by detecting cycles.
• Mapping Systems and GPS Navigation: Graphs help in locating places and
optimizing routes in mapping systems and GPS navigation.
• Graph Algorithms and Measures: Graphs are analyzed for structural
properties and measurable quantities, including dynamic properties in
networks.
What is a Graph?
A graph is an ordered pair G = (V, E) comprising a set V of vertices or
nodes and a collection of pairs of vertices from V, known as edges of a
graph. For example, for the graph below.
V = { 1, 2, 3, 4, 5, 6 }
E = { (1, 4), (1, 6), (2, 6), (4, 5), (5, 6) }
Types of graph
• Undirected • Directed
Weighted Graph
• A graph is a weighted graph if a number (weight) is assigned to each edge. Such
weights might represent, for example, costs, lengths or capacities, etc. depending
on the problem at hand.
Weighted graph
Directed Acyclic Graph (DAG)
• A Directed Acyclic Graph (DAG) is a directed graph that
contains no cycles.
Multi graph vs Simple graph
• A multigraph is an undirected graph in which multiple
edges (and sometimes loops) are allowed. Multiple edges
are two or more edges that connect the same two
vertices.
• A simple graph is an undirected graph in which both
multiple edges and loops are disallowed as opposed to a
multigraph.
Complete graph
• A complete graph is one in which every two vertices are
adjacent: all edges that could exist are present.
Connected graph
• A Connected graph has a path between every pair of
vertices. In other words, there are no unreachable
vertices. A disconnected graph is a graph that is not
connected.
Terminologies:
1. End vertices
2. Adjacent vertices
3. Outgoing edges
4. Incoming edges
5. Degree of a vertex, v, denoted deg(v) is the number of incident edges
6. Out-degree
7. In-degree
Degree of Node
Representations of Graph
• Here are the two most common ways to represent a
graph :
1. Adjacency Matrix
2. Adjacency List
What is Adjacency Matrix?
• Adjacency Matrix is a square matrix used to represent a
finite graph by storing the relationships between the
nodes in their respective cells. For a graph
with V vertices, the adjacency matrix A is an V X
V matrix or 2D array.
• If there is an edge from vertex i to j, mark adjMat[i][j]
as 1.
• If there is no edge from vertex i to j, mark adjMat[i][j]
as 0.
Adjacency List Representation
• An array of Lists is used to store edges between two vertices. The
size of array is equal to the number of vertices (i.e, n). Each index
in this array represents a specific vertex in the graph. The entry at
the index i of the array contains a linked list containing the vertices
that are adjacent to vertex i.
• Let’s assume there are n vertices in the graph So, create an array of
list of size n as adjList[n].
• adjList[0] will have all the nodes which are connected
(neighbour) to vertex 0.
• adjList[1] will have all the nodes which are connected
(neighbour) to vertex 1 and so on.
Graph representation using
adjacency List
Graph Traversal
• BFS (Breadth First Search)
The algorithm efficiently visits and marks all the key nodes in a graph in an
accurate breadthwise fashion. This algorithm selects a single node (initial or
source point) in a graph and then visits all the nodes adjacent to the selected
node. Remember, BFS accesses these nodes one by one.
• DFS (Depth First Search)
In Depth First Search (or DFS) for a graph, we traverse all adjacent
vertices one by one. When we traverse an adjacent vertex, we
completely finish the traversal of all vertices reachable through
that adjacent vertex.
steps to implement BFS
traversal...
Step 1 - Define a Queue of size total number of vertices in the
graph.
Step 2 - Select any vertex as starting point for traversal. Visit
that vertex and insert it into the Queue.
Step 3 - Visit all the non-visited adjacent vertices of the vertex
which is at front of the Queue and insert them into
the Queue.
Step 4 - When there is no new vertex to be visited from the
vertex which is at front of the Queue then delete that
vertex.
Step 5 - Repeat steps 3 and 4 until queue becomes empty.
Step 6 - When queue becomes empty, then produce final
spanning tree by removing unused edges from the graph
BFS Traversal using adjacency matrix
#define MAX 100 // Maximum number of vertices
while (![Link]()) {
int node = [Link]();
// Function to perform BFS on a graph represented [Link]();
by an adjacency matrix cout << node << " ";
void BFS(int graph[MAX][MAX], int vertices, int start)
{ // Traverse all adjacent vertices
bool visited[MAX] = {false}; // Array to keep track for (int i = 0; i < vertices; i++) {
if (graph[node][i] == 1 && !visited[i]) {
of visited nodes
visited[i] = true;
queue<int> q; // Queue for BFS traversal
[Link](i);
}
visited[start] = true; }
[Link](start); }
cout << "BFS Traversal: "; cout << endl;
}
Complexity Analysis of BFS
• Time Complexity: O(V + E), BFS explores all the
vertices and edges in the graph.
• In the worst case, it visits every vertex and edge once.
Therefore, the time complexity of BFS is O(V + E),
where V and E are the number of vertices and edges in
the given graph.
Steps to perform DSF
A standard DFS implementation puts each vertex of the graph into one of two
categories:
[Link]
[Link] Visited
The purpose of the algorithm is to mark each vertex as visited while avoiding
cycles.
The DFS algorithm works as follows:
[Link] by putting any one of the graph's vertices on top of a stack.
[Link] the top item of the stack and add it to the visited list.
[Link] a list of that vertex's adjacent nodes. Add the ones which aren't in the
visited list to the top of the stack.
[Link] repeating steps 2 and 3 until the stack is empty.
Pseudo Code DFS
// function to perform DFS on the graph
void dfs(int start, vector<bool> & visited)
{
// Print the current node
cout << start << " ";
// Set current node as visited
visited[start] = true;
// For every node of the graph
for (int i = 0; i < adj[start].size(); i++) {
// If some node is adjacent to the current node and it has not already been visited
if (adj[start][i] == 1 && (!visited[i])) {
dfs(i, visited);
}
}
}
Time complexity of DFS
• Time complexity: O(V + E), where V is the number of
vertices and E is the number of edges in the graph.
Spanning Tree of Graph
• A spanning tree is a subset of Graph G, which has all the vertices covered with
minimum possible number of edges. Hence, a spanning tree does not have cycles
and it cannot be disconnected.
• Properties of spanning tree
1. Spanning tree has n-1 edges, where n is the number of nodes (vertices).
2. A connected graph G can have more than one spanning tree.
3. All possible spanning trees of graph G, have the same number of edges
and vertices.
4. The spanning tree does not have any cycle (loops).
5. Removing one edge from the spanning tree will make the graph
disconnected, i.e. the spanning tree is minimally connected.
6. Adding one edge to the spanning tree will create a circuit or loop, i.e. the
spanning tree is maximally acyclic.
Applications of Spanning Tree
of Graph
1. Building Telecommunication Network.
2. Used in many path finding algorithms
3. Computer Network Routing Protocol
Minimum Spanning Tree of
Graph (MST)
• A minimum spanning tree (MST) is defined as a
spanning tree that has the minimum weight among all
the possible spanning trees.
• Algorithm to find MST
1. Prim’s algorithm
2. Kruskal’s Algorithm
Kruskal’s Algorithm to find MST
Kruskal’s Algorithm
Kruskal(Graph):
Initialize MST as an empty set
Sort all edges in the graph by their weight (in non-decreasing order)
Create a disjoint-set for all vertices
for each edge (u, v) in the sorted edge list:
if find(u) != find(v): // Check if u and v belong to different sets
Add edge (u, v) to MST
Union the sets of u and v
return MST
Kruskal’s Algorithm for MST