GRAPH IN DATA STRUCTURE
A graph in
computer science is a collection of nodes (vertices) and edges connecting pairs
of nodes. Graphs are used to model relationships and connections between
various entities.
They find
applications in a wide range of fields, including computer science, social
network analysis, transportation systems, and more.
Figure
from the web resource
Basic Terminology
of Graphs:
1. Vertex (Node):
- A fundamental unit of a graph representing
a point or entity. Denoted by \(V\) or \(N\).
2. Edge:
- A connection between two vertices,
representing a relationship. Denoted by \(E\).
3. Directed Graph
(Digraph):
- A graph in which edges have a direction,
pointing from one vertex to another.
4. Undirected
Graph:
- A graph in which edges have no direction,
representing symmetric relationships.
5. Weighted Graph:
- A graph in which edges have weights or
costs assigned to represent the cost of traversing the edge.
6. Degree of a
Vertex:
- The number of edges incident to a vertex.
In directed graphs, there are in-degrees and out-degrees.
7. Path:
- A sequence of vertices where each adjacent
pair is connected by an edge.
8. Cycle:
- A path that starts and ends at the same
vertex, forming a closed loop.
9. Connected
Graph:
- A graph in which there is a path between
every pair of vertices.
10. Disconnected
Graph:
- A graph in which there are at least two
vertices without a path between them.
Features of Graphs:
1. Versatility:
- Graphs can model a wide range of
relationships and structures, making them a versatile data structure.
2. Representation
Flexibility:
- Graphs can be represented using various
data structures, including adjacency matrix, adjacency list, and others.
3. Dynamic
Structure:
- Graphs can be easily modified by adding or
removing vertices and edges.
4. Graph
Algorithms:
- Many algorithms are designed to operate on
graphs, such as Dijkstra's algorithm for shortest paths and depth-first search
for traversal.
5. Applications:
- Graphs find applications in various
fields, including social networks, transportation networks, computer networks,
and recommendation systems.
Structure of a Graph:
1. Adjacency
Matrix:
- A 2D matrix where each cell (i, j)
represents whether there is an edge between vertex i and vertex j. For weighted
graphs, the cell may contain the weight of the edge.
2. Adjacency List:
- A collection of lists or arrays, where
each list represents the vertices adjacent to a particular vertex. Suitable for
sparse graphs.
3. Edge List:
- A list of edges, where each edge is
represented as a pair (u, v), indicating an edge between vertex u and vertex v.
Example of a Graph:
Consider an
undirected graph:
A
/ \
B - C
This graph has
three vertices {A, B, C} and three edges {(A, B), (A, C), (B, C)}.
In an adjacency
list representation:
A: [B, C]
B: [A, C]
C: [A, B]
In an adjacency
matrix representation:
A
B C
A [0, 1, 1]
B [1, 0, 1]
C [1, 1, 0]
Graph algorithms
operate on graphs to solve various problems, including finding paths,
connectivity, and spanning trees.
Mainly two
fundamental graph algorithms are :
Depth-First Search
(DFS) and
Breadth-First
Search (BFS).
Depth-First Search (DFS):
DFS explores as
far as possible along each branch before backtracking. It's commonly used for
tasks like finding connected components, topological sorting, and solving
mazes.
# Example in C++: cpp
#include
<iostream>
#include
<vector>
#include
<stack>
#include
<unordered_set>
using namespace
std;
class Graph {
public:
int vertices;
vector<vector<int>>
adjacencyList;
Graph(int v) : vertices(v),
adjacencyList(v) {}
void addEdge(int u, int v) {
adjacencyList[u].push_back(v);
adjacencyList[v].push_back(u);
}
void DFS(int start) {
vector<bool> visited(vertices,
false);
stack<int> s;
s.push(start);
while (!s.empty()) {
int vertex = s.top();
s.pop();
if (!visited[vertex]) {
cout << vertex <<
" ";
visited[vertex] = true;
for (int neighbor :
adjacencyList[vertex]) {
if (!visited[neighbor]) {
s.push(neighbor);
}
}
}
}
}
};
int main() {
Graph graph(6);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
cout << "DFS starting from
vertex 0: ";
graph.DFS(0);
return 0;
}
-----------------------------------------
# Example in
Python: python
from collections
import defaultdict
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adjacency_list = defaultdict(list)
def add_edge(self, u, v):
self.adjacency_list[u].append(v)
self.adjacency_list[v].append(u)
def DFS(self, start):
visited = [False] * self.vertices
stack = [start]
while stack:
vertex = stack.pop()
if not visited[vertex]:
print(vertex, end="
")
visited[vertex] = True
for neighbor in
self.adjacency_list[vertex]:
if not visited[neighbor]:
stack.append(neighbor)
if __name__ ==
"__main__":
graph = Graph(6)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 5)
print("DFS starting from vertex
0:", end=" ")
graph.DFS(0)
--------------------------------------------------------
Breadth-First Search (BFS):
BFS explores all
the vertices at the current depth before moving on to vertices at the next
depth level. It's often used for finding the shortest path in unweighted graphs
and network broadcasting.
# Example in C++: cpp
#include
<iostream>
#include
<vector>
#include
<queue>
#include
<unordered_set>
using namespace
std;
class Graph {
public:
int vertices;
vector<vector<int>>
adjacencyList;
Graph(int v) : vertices(v),
adjacencyList(v) {}
void addEdge(int u, int v) {
adjacencyList[u].push_back(v);
adjacencyList[v].push_back(u);
}
void BFS(int start) {
vector<bool> visited(vertices,
false);
queue<int> q;
q.push(start);
while (!q.empty()) {
int vertex = q.front();
q.pop();
if (!visited[vertex]) {
cout << vertex <<
" ";
visited[vertex] = true;
for (int neighbor :
adjacencyList[vertex]) {
if (!visited[neighbor]) {
q.push(neighbor);
}
}
}
}
}
};
int main() {
Graph graph(6);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
cout << "BFS starting from
vertex 0: ";
graph.BFS(0);
return 0;
}
------------------------------------------------------
# Example in
Python: python
from collections
import defaultdict, deque
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adjacency_list = defaultdict(list)
def add_edge(self, u, v):
self.adjacency_list[u].append(v)
self.adjacency_list[v].append(u)
def BFS(self, start):
visited = [False] * self.vertices
queue = deque([start])
while queue
:
vertex = queue.popleft()
if not visited[vertex]:
print(vertex, end="
")
visited[vertex] = True
for neighbor in
self.adjacency_list[vertex]:
if not visited[neighbor]:
queue.append(neighbor)
if __name__ ==
"__main__":
graph = Graph(6)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 5)
print("BFS starting from vertex
0:", end=" ")
graph.BFS(0)
These examples
demonstrate the implementation of DFS and BFS algorithms in both C++ and Python
on a simple graph. These algorithms are fundamental for graph traversal and
exploration.
-------------------------------------------------------
Graph Types:
1. Directed Graph
(Digraph):
- Edges have a direction, indicating a
one-way relationship between vertices.
2. Undirected
Graph:
- Edges have no direction, representing
symmetric relationships between vertices.
3. Weighted Graph:
- Edges have weights or costs assigned to
represent the cost of traversing the edge.
4. Unweighted
Graph:
- Edges have no weights; all edges are
considered to have the same weight.
5. Cyclic Graph:
- Contains at least one cycle, a closed path
where a sequence of edges returns to the starting vertex.
6. Acyclic Graph:
- Does not contain any cycles.
7. Connected
Graph:
- There is a path between every pair of
vertices.
8. Disconnected
Graph:
- There are at least two vertices without a
path between them.
----------------------------------------------------------------
Advantages of Graphs:
1. Modeling
Relationships:
- Graphs are excellent for modeling
relationships between entities in various domains, such as social networks,
transportation systems, and computer networks.
2. Versatility:
- Graphs can represent a wide range of
structures and relationships, making them versatile for different applications.
3. Graph
Algorithms:
- Many efficient algorithms have been
developed for graph-related problems, including shortest path algorithms,
minimum spanning tree algorithms, and more.
4. Data
Representation:
- Graphs can be used to represent data
structures like trees, linked structures, and more.
-------------------------------------------------
Disadvantages of Graphs:
1. Complexity:
- Graph algorithms can be complex and
resource-intensive, especially for large graphs.
2. Storage
Overhead:
- Depending on the representation, graphs
may have higher storage overhead compared to simpler data structures.
---------------------------------------------
Applications of Graphs:
1. Social
Networks:
- Representing friendships, connections, and
interactions between individuals.
2. Transportation
Networks:
- Modelling roads, flight paths, and other
transportation systems.
3. Computer
Networks:
- Representing communication and
connectivity between devices.
4. Recommendation
Systems:
- Analysing user preferences and
recommending items based on relationships.
5. Databases:
- Indexing and querying relational
databases.
6. Routing
Algorithms:
- Finding the shortest path between two
locations in maps or networks.
7. Circuit Design:
- Representing components and connections in
electronic circuits.
8. Molecular
Biology:
- Representing interactions in biological
systems.
9. Game
Development:
- Representing relationships between game
entities and characters.
10. Knowledge
Representation:
- Modelling relationships between concepts
in knowledge graphs.
Graphs are a
fundamental data structure with broad applicability. They provide a powerful
way to model and analyze complex relationships and structures in diverse
fields.
============================================
Directed Graph
Figure
from the web resource
A Directed Graph
(DiGraph) is a type of graph in which edges have a direction, indicating a
one-way relationship between vertices. Each edge in a directed graph is
represented as an ordered pair \((u, v)\), where \(u\) is the starting vertex,
and \(v\) is the ending vertex.
Directed graphs
are widely used to model various scenarios where relationships have a clear
directionality.
Basic Terminology of Directed Graphs:
1. Vertex (Node):
- A fundamental unit of a directed graph
representing a point or entity. Denoted by \(V\) or \(N\).
2. Edge:
- A connection between two vertices with a
direction, represented as an ordered pair \((u, v)\) indicating a directed edge
from \(u\) to \(v\).
3. In-Degree:
- The number of incoming edges to a vertex.
4. Out-Degree:
- The number of outgoing edges from a
vertex.
5. Adjacent
Vertices:
- Two vertices are adjacent if there is an
edge from the first vertex to the second.
6. Path:
- A sequence of vertices where each adjacent
pair is connected by a directed edge.
7. Cycle:
- A path that starts and ends at the same
vertex, forming a closed loop.
Features of
Directed Graphs:
1. Directionality:
- Edges in directed graphs have a clear
direction, indicating a one-way relationship between vertices.
2. In-Degree and
Out-Degree:
- Directed graphs have in-degrees and
out-degrees associated with each vertex, providing information about incoming
and outgoing edges.
3. Cyclic and
Acyclic:
- Directed graphs can be cyclic, containing
at least one cycle, or acyclic, with no cycles.
4. Connectivity:
- Directed graphs can be strongly connected,
meaning there is a directed path between every pair of vertices, or weakly
connected, where ignoring edge directions results in a connected undirected
graph.
----------------------------------------
Structure of
Directed Graphs:
1. Adjacency
Matrix:
- A 2D matrix where each cell (i, j)
represents whether there is a directed edge from vertex i to vertex j. For
weighted graphs, the cell may contain the weight of the directed edge.
2. Adjacency List:
- A collection of lists or arrays, where
each list represents the vertices adjacent to a particular vertex, along with
the direction of the edges.
Example of a Directed Graph:
Consider a
directed graph:
A --> B
^ / |
| / v
D <-- C
This directed
graph has four vertices {A, B, C, D} and six directed edges {(A, B), (A, D),
(B, C), (C, A), (C, D), (D, B)}.
In an adjacency
list representation:
A: [B, D]
B: [C]
C: [A, D]
D: [B]
In an adjacency
matrix representation:
A
B C D
A [0, 1, 0, 1]
B [0, 0, 1, 0]
C [1, 0, 0, 1]
D [0, 1, 0, 0]
This example
illustrates the basic concepts of a directed graph, its vertices, directed
edges, and different ways to represent it.
One of the
fundamental algorithms used for directed graphs is the Depth-First Search (DFS)
algorithm. DFS is used to traverse and explore vertices in a directed graph,
and it can also be adapted to detect cycles, find strongly connected
components, and perform other tasks.
----------------------------------------------------
Depth-First Search (DFS) on Directed Graph:
# Example in C++: cpp
#include
<iostream>
#include
<vector>
#include
<stack>
#include
<unordered_set>
using namespace
std;
class
DirectedGraph {
public:
int vertices;
vector<vector<int>>
adjacencyList;
DirectedGraph(int v) : vertices(v),
adjacencyList(v) {}
void addEdge(int u, int v) {
adjacencyList[u].push_back(v);
}
void DFS(int start) {
vector<bool> visited(vertices,
false);
stack<int> s;
s.push(start);
while (!s.empty()) {
int vertex = s.top();
s.pop();
if (!visited[vertex]) {
cout << vertex <<
" ";
visited[vertex] = true;
for (int neighbor :
adjacencyList[vertex]) {
if (!visited[neighbor]) {
s.push(neighbor);
}
}
}
}
}
};
int main() {
DirectedGraph graph(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
cout << "DFS starting from
vertex 0: ";
graph.DFS(0);
return 0;
}
---------------------------------------------
# Example in
Python: python
from collections
import defaultdict
class
DirectedGraph:
def __init__(self, vertices):
self.vertices = vertices
self.adjacency_list = defaultdict(list)
def add_edge(self, u, v):
self.adjacency_list[u].append(v)
def DFS(self, start):
visited = [False] * self.vertices
stack = [start]
while stack:
vertex = stack.pop()
if not visited[vertex]:
print(vertex, end="
")
visited[vertex] = True
for neighbor in
self.adjacency_list[vertex]:
if not visited[neighbor]:
stack.append(neighbor)
if __name__ ==
"__main__":
graph = DirectedGraph(4)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 3)
print("DFS starting from vertex
0:", end=" ")
graph.DFS(0)
These examples
demonstrate the Depth-First Search algorithm on a directed graph in both C++
and Python. The algorithm starts from a specified vertex and explores as far as
possible along each branch before backtracking. It's important to note that DFS
can be adapted for various applications on directed graphs.
------------------------------------------------------------------
Directed Graph Types:
1. Weakly
Connected Graph:
- A directed graph is weakly connected if
replacing all of its directed edges with undirected edges produces a connected
undirected graph.
2. Strongly
Connected Graph:
- A directed graph is strongly connected if
there is a directed path from every vertex to every other vertex.
3. Cyclic Directed
Graph:
- Contains at least one directed cycle,
forming closed loops.
4. Acyclic
Directed Graph:
- Does not contain any directed cycles.
--------------------------------------------------------------------
Advantages of Directed Graphs:
1. Representation
of Relationships:
- Directed graphs are well-suited for
representing relationships with a clear direction, such as dependencies, flow,
and influence.
2. Modelling
Processes:
- Directed graphs are used to model
processes, workflows, and dependencies between tasks in various applications.
3. Graph
Algorithms:
- Algorithms designed for directed graphs,
such as topological sorting and shortest path algorithms, can efficiently solve
specific problems.
4. Strongly
Connected Components:
- Directed graphs help identify strongly
connected components, which are essential in various applications, including
network analysis and circuit design.
------------------------------------------------------------------------
Disadvantages of
Directed Graphs:
1. Complexity:
- Analysing and designing algorithms for
directed graphs can be more complex than for undirected graphs, especially in
the presence of cycles.
2. Storage
Overhead:
- Depending on the representation used,
directed graphs may have higher storage overhead compared to simpler data
structures.
Applications of Directed Graphs:
1. Dependency
Resolution:
- Representing dependencies between tasks or
components in software development, build systems, and project management.
2. Network
Routing:
- Modelling directed edges as connections in
network routing applications, where the direction indicates the flow of data.
3. Workflow Modelling:
- Describing workflows and processes in
various domains, such as business process modeling and scientific simulations.
4. Transportation
Networks:
- Modelling traffic flow, routes, and
dependencies in transportation networks.
5. Circuit Design:
- Analysing and optimizing electrical
circuits with directed edges representing connections and dependencies.
6. Web Link
Analysis:
- Analysing the structure of hyperlinks on
the web, where directed edges represent links from one webpage to another.
7. Compiler
Design:
- Representing dependencies between code
modules and optimizing the compilation process.
8. Social Network
Analysis:
- Studying relationships and influence in
social networks, where directed edges can represent followership or influence.
Directed graphs
play a crucial role in modeling and analyzing complex relationships with
directionality. Their applications are diverse and extend to various domains
where understanding dependencies and flow is essential. Despite their
complexity, directed graphs provide a powerful tool for representing and
solving problems in fields such as computer science, engineering, and social
sciences.
--------------------------------------------
Undirected Graph
An Undirected
Graph is a type of graph in which edges have no direction, representing
symmetric relationships between vertices.
In an undirected
graph, the edges connect pairs of vertices, and the connection is mutual. If
there is an edge between vertex \(u\) and vertex \(v\), it implies that there
is also an edge between \(v\) and \(u\). Undirected graphs are widely used to
model various scenarios where relationships are bidirectional.
Basic Terminology
of Undirected Graphs:
1. Vertex (Node):
- A fundamental unit of an undirected graph
representing a point or entity. Denoted by \(V\) or \(N\).
2. Edge:
- A connection between two vertices with no
direction. Represented as an unordered pair \(\{u, v\}\).
3. Adjacent
Vertices:
- Two vertices are adjacent if there is an
edge connecting them.
4. Degree of a
Vertex:
- The number of edges incident to a vertex.
In undirected graphs, there is no distinction between in-degree and out-degree.
5. Path:
- A sequence of vertices where each adjacent
pair is connected by an edge.
6. Cycle:
- A path that starts and ends at the same
vertex, forming a closed loop.
Features of Undirected Graphs:
1. Symmetry:
- Edges in undirected graphs represent
symmetric relationships, and the order of vertices in an edge does not matter.
2. Bidirectional
Relationships:
- Relationships between vertices are
bidirectional, meaning if there is an edge between \(u\) and \(v\), there is
also an edge between \(v\) and \(u\).
3. Connectivity:
- Undirected graphs can be connected, where
there is a path between every pair of vertices, or disconnected, where there
are pairs of vertices without a path between them.
------------------------------------------------------
Structure of Undirected Graphs:
1. Adjacency
Matrix:
- A 2D matrix where each cell (i, j)
represents whether there is an edge between vertex \(i\) and vertex \(j\). The
matrix is symmetric for undirected graphs.
2. Adjacency List:
- A collection of lists or arrays, where
each list represents the vertices adjacent to a particular vertex.
Example: Consider an
undirected graph:
A
/ \
B - C
This undirected
graph has three vertices {A, B, C} and three undirected edges \(\{A, B\}, \{A,
C\}, \{B, C\}\).
In an adjacency
list representation:
A: [B, C]
B: [A, C]
C: [A, B]
In an adjacency
matrix representation:
A
B C
A [0, 1, 1]
B [1, 0, 1]
C [1, 1, 0]
One of the
fundamental algorithms used for undirected graphs is the Depth-First Search
(DFS) algorithm. DFS is used to traverse and explore vertices in an undirected
graph and can also be adapted for other tasks such as cycle detection and
connected component analysis.
Depth-First Search (DFS) on Undirected Graph:
# Example in C++: cpp
#include
<iostream>
#include
<vector>
#include
<stack>
#include <unordered_set>
using namespace
std;
class
UndirectedGraph {
public:
int vertices;
vector<vector<int>>
adjacencyList;
UndirectedGraph(int v) : vertices(v),
adjacencyList(v) {}
void addEdge(int u, int v) {
adjacencyList[u].push_back(v);
adjacencyList[v].push_back(u);
}
void DFS(int start) {
vector<bool> visited(vertices,
false);
stack<int> s;
s.push(start);
while (!s.empty()) {
int vertex = s.top();
s.pop();
if (!visited[vertex]) {
cout << vertex <<
" ";
visited[vertex] = true;
for (int neighbor :
adjacencyList[vertex]) {
if (!visited[neighbor]) {
s.push(neighbor);
}
}
}
}
}
};
int main() {
UndirectedGraph graph(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
cout << "DFS starting from
vertex 0: ";
graph.DFS(0);
return 0;
}
======================================
# Example in
Python:python
from collections
import defaultdict
class
UndirectedGraph:
def __init__(self, vertices):
self.vertices = vertices
self.adjacency_list = defaultdict(list)
def add_edge(self, u, v):
self.adjacency_list[u].append(v)
self.adjacency_list[v].append(u)
def DFS(self, start):
visited = [False] * self.vertices
stack = [start]
while stack:
vertex = stack.pop()
if not visited[vertex]:
print(vertex, end="
")
visited[vertex] = True
for neighbor in
self.adjacency_list[vertex]:
if not visited[neighbor]:
stack.append(neighbor)
if __name__ ==
"__main__":
graph = UndirectedGraph(4)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
print("DFS starting from vertex
0:", end=" ")
graph.DFS(0)
--------------------------------------------------------------------------------
Undirected Graph Types:
1. Connected
Graph:
- A graph in which there is a path between
every pair of vertices.
2. Disconnected
Graph:
- A graph in which there are at least two
vertices without a path between them.
3. Cyclic Graph:
- Contains at least one cycle, a closed path
where a sequence of edges returns to the starting vertex.
4. Acyclic Graph:
- Does not contain any cycles.
-------------------------------------------------------
Advantages of Undirected Graphs:
1. Simplicity:
- Undirected graphs are simpler to work with
compared to directed graphs because edges have no direction.
2. Ease of
Representation:
- Can be easily represented using adjacency
matrices or adjacency lists.
3. Connectivity
Analysis:
- Useful for analyzing and determining the
connectivity between different components of a system.
4. Graph
Algorithms:
- Many fundamental graph algorithms, such as
depth-first search and breadth-first search, can be applied directly to
undirected graphs.
----------------------------------------------------------
Disadvantages of
Undirected Graphs:
1. Lack of
Directionality:
- For scenarios where relationships have a
clear direction, undirected graphs may not capture the full complexity of the
relationships.
2. Limited Modelling
Capability:
- Not suitable for modeling scenarios where
directionality is essential, such as dependencies and flow in certain systems.
---------------------------------------------------
Applications of
Undirected Graphs:
1. Social Network
Analysis:
- Modelling friendships and connections
between individuals in a social network.
2. Recommendation
Systems:
- Analyzing and recommending items based on
user preferences and connections.
3. Transportation
Networks:
- Modelling connections between locations in
transportation systems, where the direction of travel is bidirectional.
4. Puzzle Solving:
- Solving puzzles and games where
connections between elements are bidirectional.
5. Wireless Sensor
Networks:
- Analyzing connectivity and communication
patterns in wireless sensor networks.
6. Molecular
Biology:
- Representing interactions between
molecules in biological systems.
7. Computer
Networks:
- Analyzing the connectivity and
relationships between devices in a computer network.
8. Map Routing:
- Finding the shortest paths between
locations on a map.
----------------------------------------------
Weighted Graph
A Weighted Graph
is a type of graph in which each edge has an associated numerical value called
a "weight." These weights can represent various measures, such as
distance, cost, time, or any other metric depending on the context of the
problem. Weighted graphs are commonly used to model scenarios where the
relationships between vertices have quantitative significance.
Basic Terminology
of Weighted Graphs:
1. Vertex (Node):
- A fundamental unit of a weighted graph
representing a point or entity. Denoted by \(V\) or \(N\).
2. Edge:
- A connection between two vertices with an
associated numerical value or weight.
3. Weight:
- The numerical value associated with an
edge representing the cost, distance, or other metric between connected
vertices.
4. Path Weight:
- The sum of the weights of the edges in a
path between two vertices.
5. Minimum Weight
Path:
- The path between two vertices with the
smallest sum of edge weights.
----------------------------------
Features of
Weighted Graphs:
1. Quantitative
Relationships:
- Weighted graphs represent relationships
between vertices with quantitative measures, providing a more realistic model
for certain scenarios.
2. Diverse
Applications:
- Weighted graphs are used in various
applications where the quantitative aspect of relationships is crucial, such as
network design, optimization problems, and routing.
----------------------------
Structure of
Weighted Graphs:
1. Adjacency
Matrix:
- A 2D matrix where each cell (i, j)
represents the weight of the edge between vertex \(i\) and vertex \(j\). A
value of infinity or a special symbol may indicate the absence of an edge.
2. Adjacency List:
- A collection of lists or arrays, where
each list represents the vertices adjacent to a particular vertex, along with
the weights of the corresponding edges.
Example of a Weighted Graph:
Consider a
weighted graph:
A
/ \
B - C
| |
D - E
This weighted
graph has five vertices {A, B, C, D, E} and seven weighted edges:
- \(w(A, B) = 2\)
- \(w(A, C) = 1\)
- \(w(B, C) = 3\)
- \(w(B, D) = 5\)
- \(w(C, E) = 4\)
- \(w(D, E) = 2\)
- \(w(B, E) = 1\)
In an adjacency
list representation:
A: [(B, 2), (C,
1)]
B: [(A, 2), (C,
3), (D, 5), (E, 1)]
C: [(A, 1), (B,
3), (E, 4)]
D: [(B, 5), (E,
2)]
E: [(C, 4), (D,
2), (B, 1)]
In an adjacency
matrix representation:
A
B C D E
A [0, 2, 1, 0, 0]
B [2, 0, 3, 5, 1]
C [1, 3, 0, 0, 4]
D [0, 5, 0, 0, 2]
E [0, 1, 4, 2, 0]
One of the
fundamental algorithms used for weighted graphs is Dijkstra's Algorithm,
which is employed to find the shortest paths from a source vertex to all other
vertices in a weighted graph.
Dijkstra's Algorithm on Weighted Graph:
Sure, let's walk
through an example of Dijkstra's algorithm on a weighted graph. Suppose we have
the following graph:
Each edge is labeled
with its weight. We want to find the shortest path from node A to all other
nodes.
1. Initialization:
- Assign a tentative distance value to each
node. Initialize it as 0 for the start node (A) and infinity (∞) for all other
nodes.
- Set the initial node as current and mark
it as visited.
Node | Tentative Distance | Visited
-------------------------------------
A |
0 | ✓
B |
∞ |
✗
C |
∞ |
✗
D |
∞ |
✗
E |
∞ |
✗
F |
∞ |
✗
2. Update Neighbour
Distances:
- For each neighbor of the current node,
calculate its tentative distance by adding the weight of the edge from the
current node to that neighbor.
- If this tentative distance is less than
the current assigned value, update the tentative distance.
Node | Tentative Distance | Visited
-------------------------------------
A
| 0 | ✓
B
| 4 | ✗
C
| ∞ | ✗
D
| 2 | ✗
E
| ∞ | ✗
F
| ∞ | ✗
3. Select Next
Node:
- Choose the unvisited node with the
smallest tentative distance. In this case, it's node D with a tentative
distance of 2.
4. Update Current
Node:
- Set the selected node (D) as the current
node and mark it as visited.
Node | Tentative Distance | Visited
-------------------------------------
A
| 0 | ✓
B
| 4 | ✗
C
| ∞ | ✗
D
| 2 | ✓
E
| 3 | ✗
F
| ∞ | ✗
5. Repeat Steps
2-4:
- Continue updating neighbour distances and
selecting the next node until all nodes are visited.
6. Final Result:
After completing the algorithm, the
tentative distances from node A to all other nodes are as follows:
- A to B: 4
- A to C: 7
- A to D: 2
- A to E: 3
- A to F: 9
So, the shortest
path from A to each node is:
- A -> D ->
E
- A -> E
- A -> B
- A -> C
- A -> D ->
E -> F
---------------------------------------------------------
# Example in C++: cpp
#include
<iostream>
#include
<vector>
#include
<queue>
#include
<limits>
using namespace
std;
class
WeightedGraph {
public:
int vertices;
vector<vector<pair<int,
int>>> adjacencyList;
WeightedGraph(int v) : vertices(v),
adjacencyList(v) {}
void addEdge(int u, int v, int weight) {
adjacencyList[u].push_back({v,
weight});
adjacencyList[v].push_back({u,
weight}); // For undirected graph
}
void dijkstra(int start) {
vector<int> distance(vertices,
numeric_limits<int>::max());
distance[start] = 0;
priority_queue<pair<int, int>,
vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, start});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (const auto& edge :
adjacencyList[u]) {
int v = edge.first;
int weight = edge.second;
if (distance[u] + weight <
distance[v]) {
distance[v] = distance[u] +
weight;
pq.push({distance[v], v});
}
}
}
cout << "Shortest distances
from vertex " << start << ":\n";
for (int i = 0; i < vertices; ++i) {
cout << "Vertex "
<< i << ": " << distance[i] <<
"\n";
}
}
};
int main() {
WeightedGraph graph(5);
graph.addEdge(0, 1, 2);
graph.addEdge(0, 2, 1);
graph.addEdge(1, 3, 5);
graph.addEdge(2, 3, 3);
graph.addEdge(2, 4, 4);
graph.addEdge(3, 4, 1);
cout << "Dijkstra's Algorithm
from vertex 0:\n";
graph.dijkstra(0);
return 0;
}
------------------------------------------------------
# Example in
Python: python
import heapq
class
WeightedGraph:
def __init__(self, vertices):
self.vertices = vertices
self.adjacency_list = [[] for _ in
range(vertices)]
def add_edge(self, u, v, weight):
self.adjacency_list[u].append((v,
weight))
self.adjacency_list[v].append((u,
weight)) # For undirected graph
def dijkstra(self, start):
distance = [float('inf')] *
self.vertices
distance[start] = 0
priority_queue = [(0, start)]
while priority_queue:
dist_u, u =
heapq.heappop(priority_queue)
for v, weight in
self.adjacency_list[u]:
if distance[u] + weight <
distance[v]:
distance[v] = distance[u] +
weight
heapq.heappush(priority_queue, (distance[v], v))
print("Shortest distances from
vertex", start)
for i in range(self.vertices):
print(f"Vertex {i}:
{distance[i]}")
if __name__ ==
"__main__":
graph = WeightedGraph(5)
graph.add_edge(0, 1, 2)
graph.add_edge(0, 2, 1)
graph.add_edge(1, 3, 5)
graph.add_edge(2, 3, 3)
graph.add_edge(2, 4, 4)
graph.add_edge(3, 4, 1)
print("Dijkstra's Algorithm from
vertex 0:")
graph.dijkstra(0)
-----------------------------------------------
Weighted Graph Types:
1. Positive
Weighted Graph:
- All edge weights are positive.
2. Negative
Weighted Graph:
- At least one edge has a negative weight.
----------------------------------------------
Advantages of
Weighted Graphs:
1. Realistic Modelling:
- Weighted graphs allow for more realistic modeling
of scenarios where relationships have quantitative significance.
2. Optimization
Problems:
- Useful for solving optimization problems
such as finding the shortest path, minimum spanning tree, etc.
--------------------------------------------------------------------
Disadvantages of
Weighted Graphs:
1. Increased
Complexity:
- Weighted graphs and their algorithms tend
to be more complex than their unweighted counterparts.
-----------------------------------------------------------------
Applications of Weighted Graphs:
1. Network
Routing:
- Finding the shortest path between two
locations in a network.
2. Transportation
Planning:
- Modelling and optimizing transportation
networks.
3. Circuit Design:
- Analyzing and optimizing electrical
circuits.
4. Game
Development:
- Implementing pathfinding algorithms in
games.
5. Logistics and
Supply Chain:
- Optimizing routes for delivery and supply
chain management.
6. Social Network
Analysis:
- Analyzing influence and relationships in
social networks.
---------------------------------------------------------------------------------
Weighted Graph Types:
1. Positive
Weighted Graph:
- All edge weights are positive. It is
common in scenarios where the weights represent distances, costs, or durations.
2. Negative
Weighted Graph:
- At least one edge has a negative weight.
Negative weights can introduce challenges in algorithms, and specific
algorithms, like Bellman-Ford, are designed to handle negative weights.
----------------------------------------
Advantages of Weighted Graphs:
1. Realistic Modelling:
- Weighted graphs allow for more accurate
modeling of scenarios where relationships have quantitative significance,
providing a realistic representation.
2. Optimization
Problems:
- Useful for solving optimization problems
such as finding the shortest path, minimum spanning tree, and other
optimization-based graph problems.
3. Decision
Support:
- Weighted graphs assist in decision-making
by providing quantitative information about the relationships between entities.
--------------------------------------------
Disadvantages of Weighted Graphs:
1. Increased
Complexity:
- Weighted graphs and their algorithms tend
to be more complex than their unweighted counterparts, requiring more
sophisticated algorithms and data structures.
2. Ambiguity in
Weight Interpretation:
- Depending on the context, the
interpretation of weights may vary, leading to potential challenges in defining
and understanding the significance of weights.
----------------------------------------------------------------------
Applications of Weighted Graphs:
1. Network
Routing:
- Finding the shortest path between two
locations in a network, which is crucial in network routing and navigation
systems.
2. Transportation
Planning:
- Modelling and optimizing transportation
networks, such as determining the most efficient routes for delivery trucks.
3. Circuit Design:
- Analyzing and optimizing electrical
circuits, where weights may represent resistances or other electrical
properties.
4. Game
Development:
- Implementing pathfinding algorithms in
games to find the optimal paths for characters or objects.
5. Logistics and
Supply Chain:
- Optimizing routes for delivery vehicles
and managing supply chain logistics efficiently.
6. Social Network
Analysis:
- Analyzing influence and relationships in
social networks, where weights may represent the strength of connections.
7. Financial
Networks:
- Modelling financial transactions and
optimizing financial networks, where weights can represent transaction costs or
risks.
8.
Telecommunication Networks:
- Optimizing data transmission in
telecommunication networks by finding paths with minimal latency.
9. Facility
Location Planning:
- Determining optimal locations for
facilities based on transportation costs and distances.
---------------------------------
Representation of
Graphs with algorithms and examples according to C++ and Python.
Graph Representation:
Image from the web resource
1. Adjacency
Matrix:
In an adjacency
matrix, a graph is represented as a 2D array of size V x V, where V is the
number of vertices in the graph. The value `graph[i][j]` is 1 if there is an
edge between vertex i and vertex j, and 0 otherwise (for an unweighted graph).
Example:- C++: cpp
#include
<iostream>
#include
<vector>
using namespace
std;
class Graph {
private:
int V;
vector<vector<int>> adjMatrix;
public:
Graph(int vertices) : V(vertices) {
adjMatrix.resize(V,
vector<int>(V, 0));
}
void addEdge(int i, int j) {
adjMatrix[i][j] = 1;
adjMatrix[j][i] = 1; // For undirected
graph
}
void printGraph() {
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
cout << adjMatrix[i][j]
<< " ";
}
cout << endl;
}
}
};
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.printGraph();
return 0;
}
Python:
python
class Graph:
def __init__(self, vertices):
self.V = vertices
self.adjMatrix = [[0] * self.V for _ in
range(self.V)]
def addEdge(self, i, j):
self.adjMatrix[i][j] = 1
self.adjMatrix[j][i] = 1 # For undirected graph
def printGraph(self):
for row in self.adjMatrix:
print(" ".join(map(str,
row)))
# Example usage:
g = Graph(4)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.printGraph()
2. Adjacency List:
In an adjacency
list, each vertex maintains a list of its adjacent vertices.
C++: cpp
#include
<iostream>
#include
<list>
using namespace
std;
class Graph {
private:
int V;
list<int> *adjList;
public:
Graph(int vertices) : V(vertices) {
adjList = new list<int>[V];
}
void addEdge(int i, int j) {
adjList[i].push_back(j);
adjList[j].push_back(i); // For
undirected graph
}
void printGraph() {
for (int i = 0; i < V; ++i) {
cout << "Vertex "
<< i << ": ";
for (int neighbor : adjList[i]) {
cout << neighbor <<
" ";
}
cout << endl;
}
}
};
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.printGraph();
return 0;
}
--------------------------------------------
Python:
class Graph:
def __init__(self, vertices):
self.V = vertices
self.adjList = [[] for _ in
range(self.V)]
def addEdge(self, i, j):
self.adjList[i].append(j)
self.adjList[j].append(i) # For undirected graph
def printGraph(self):
for i in range(self.V):
print(f"Vertex {i}:
{self.adjList[i]}")
# Example usage:
g = Graph(4)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.printGraph()
-------------------------------------------------------
Graph Algorithms:
1. Depth-First Search (DFS):
Example:- C++: cpp
#include
<iostream>
#include
<vector>
#include
<stack>
using namespace
std;
class Graph {
private:
int V;
vector<vector<int>> adjList;
public:
Graph(int vertices) : V(vertices),
adjList(vertices) {}
void addEdge(int i, int j) {
adjList[i].push_back(j);
adjList[j].push_back(i); // For
undirected graph
}
void DFS(int start) {
vector<bool> visited(V, false);
stack<int> s;
s.push(start);
while (!s.empty()) {
int current = s.top();
s.pop();
if (!visited[current]) {
cout << current <<
" ";
visited[current] = true;
}
for (int neighbor :
adjList[current]) {
if (!visited[neighbor]) {
s.push(neighbor);
}
}
}
}
};
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
cout << "DFS starting from
vertex 0: ";
g.DFS(0);
return 0;
}
------------------------------------------------
Python:
class Graph:
def __init__(self, vertices):
self.V = vertices
self.adjList = [[] for _ in
range(self.V)]
def addEdge(self, i, j):
self.adjList[i].append(j)
self.adjList[j].append(i) # For undirected graph
def DFS(self, start):
visited = [False] * self.V
stack = [start]
while stack:
current = stack.pop()
if not visited[current]:
print(current, end="
")
visited[current] = True
stack.extend(neighbor for neighbor
in self.adjList[current] if not visited[neighbor])
# Example usage:
g = Graph(4)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
print("DFS
starting from vertex 0:", end=" ")
g.DFS(0)
--------------------------------------------
TRAVERSING GRAPH
Graph traversal is
the process of visiting all the vertices and edges of a graph systematically. There are two main graph traversal techniques: Depth-First Search (DFS)
and Breadth-First Search (BFS). Both techniques can be applied to both directed
and undirected graphs.
1. Depth-First Search (DFS):
DFS explores as
far as possible along each branch before backtracking. It uses a stack (either
explicit or recursive call stack) to keep track of the vertices to visit.
# Algorithm:
1. Start from an
initial vertex.
2. Mark the vertex
as visited.
3. Explore an
adjacent unvisited vertex and repeat step 2.
4. If there is no
unvisited adjacent vertex, backtrack to the previous vertex.
C++ Example: cpp
void DFS(int
start) {
vector<bool> visited(V, false);
stack<int> s;
s.push(start);
while (!s.empty()) {
int current = s.top();
s.pop();
if (!visited[current]) {
cout << current <<
" ";
visited[current] = true;
}
for (int neighbor : adjList[current]) {
if (!visited[neighbor]) {
s.push(neighbor);
}
}
}
}
----------------------------------------
Python Example: python
def DFS(self,
start):
visited = [False] * self.V
stack = [start]
while stack:
current = stack.pop()
if not visited[current]:
print(current, end=" ")
visited[current] = True
stack.extend(neighbor for neighbor in
self.adjList[current] if not visited[neighbor])
---------------------------------------------------------------------
2. Breadth-First Search (BFS):
BFS explores all
the vertices at the current level before moving on to the next level. It uses a
queue to keep track of the vertices to visit.
# Algorithm:
1. Start from an
initial vertex.
2. Mark the vertex
as visited.
3. Enqueue the
vertex.
4. While the queue
is not empty, dequeue a vertex and:
- Visit the vertex.
- Enqueue all unvisited neighbors.
C++ Example: cpp
void BFS(int
start) {
vector<bool> visited(V, false);
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int current = q.front();
q.pop();
cout << current << "
";
for (int neighbor : adjList[current]) {
if (!visited[neighbor]) {
q.push(neighbor);
visited[neighbor] = true;
}
}
}
}
------------------------------------------------
Python Example: python
from collections
import deque
def BFS(self,
start):
visited = [False] * self.V
queue = deque([start])
visited[start] = True
while queue:
current = queue.popleft()
print(current, end=" ")
for neighbor in self.adjList[current]:
if not visited[neighbor]:
queue.append(neighbor)
visited[neighbor] = True
These are the
basic algorithms for traversing graphs. Depending on the specific requirements,
variations, and optimizations of these algorithms can be used.
--------------------------
Depth First Graph
Traversal
Graph Traversal:
Basic Terminology:
1. Vertex (Node): A fundamental
unit of a graph.
2. Edge: A connection
between two vertices that may have a direction (in the case of a directed
graph).
3. Graph: A collection of
vertices and edges that may be directed or undirected.
4. Adjacency: Two vertices are
adjacent if there is an edge connecting them.
5. Visited: A vertex is
marked as visited during traversal to avoid infinite loops.
6. Stack (or
Recursion): Used to keep track of vertices to visit.
Features:
1. Depth-First
Nature:
DFS explores as deeply as possible before moving on to the next branch.
2. Stack Usage (or
Recursion):
A stack is employed to keep track of vertices to visit. Alternatively,
recursion implicitly utilizes the call stack.
3. Backtracking: DFS involves
backtracking when a path leads to a dead end (no unvisited neighbors).
4. Applications: DFS is used for
topological sorting, connected components, cycle detection, and solving maze
problems.
5. Memory
Efficiency:
DFS typically uses less memory compared to BFS because it only needs to store
the stack or recursion stack.
Structure:
1. Initialization: Start from an
initial vertex and mark it as visited.
2. Explore and
Recurse:
Explore an adjacent unvisited vertex and repeat the process. If using
recursion, the recursion stack implicitly takes care of exploration.
3. Backtrack: If there are no
unvisited neighbors, backtrack to the previous vertex (pop from the stack or
return from the recursive call).
4. Completion: Continue the
process until all vertices are visited.
C++ Example: cpp
#include
<iostream>
#include
<vector>
#include
<stack>
using namespace
std;
class Graph {
private:
int V;
vector<vector<int>> adjList;
public:
Graph(int vertices) : V(vertices),
adjList(vertices) {}
void addEdge(int i, int j) {
adjList[i].push_back(j);
adjList[j].push_back(i); // For
undirected graph
}
void DFS(int start) {
vector<bool> visited(V, false);
stack<int> s;
s.push(start);
while (!s.empty()) {
int current = s.top();
s.pop();
if (!visited[current]) {
cout << current <<
" ";
visited[current] = true;
}
for (int neighbor :
adjList[current]) {
if (!visited[neighbor]) {
s.push(neighbor);
}
}
}
}
};
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
cout << "DFS starting from
vertex 0: ";
g.DFS(0);
return 0;
}
In this example,
the DFS algorithm is applied to a simple graph. It starts from vertex 0 and
traverses the graph in a depth-ward motion. The visited vertices are printed in
the order they are explored.
----------------------------------------------
Python Example: python
class Graph:
def __init__(self, vertices):
self.V = vertices
self.adjList = [[] for _ in
range(self.V)]
def addEdge(self, i, j):
self.adjList[i].append(j)
self.adjList[j].append(i) # For undirected graph
def DFS(self, start):
visited = [False] * self.V
stack = [start]
while stack:
current = stack.pop()
if not visited[current]:
print(current, end="
")
visited[current] = True
stack.extend(neighbor for neighbor
in self.adjList[current] if not visited[neighbor])
# Example usage:
g = Graph(4)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
print("DFS
starting from vertex 0:", end=" ")
g.DFS(0)
In both examples,
the graph has four vertices, and DFS is initiated from vertex 0. The visited
vertices are printed in the order they are explored. The stack is utilized to
keep track of vertices to visit. The DFS algorithm ensures that each branch is
fully explored before moving on to the next branch.
Depth-First Graph Traversal Types:
1. Classic Depth-First Search (DFS):
- Description: Visit a vertex and then
recursively explore each unvisited neighbor before backtracking.
- Implementation: Utilizes a stack or
recursion.
2. Topological Sorting:
- Description: Use DFS to linearly order the
vertices of a directed acyclic graph (DAG) such that for every directed edge
(u, v), vertex u comes before vertex v in the ordering.
- Application: Useful in scheduling tasks
with dependencies.
3. Connected Components:
- Description: Identify and label the
connected components of an undirected graph.
- Application: Network analysis, identifying
clusters or groups.
4. Cycle Detection:
- Description: Detect cycles in a graph
using back edges encountered during DFS.
- Application: Ensuring a graph remains
acyclic, such as in dependency graphs.
Advantages of DFS:
1. Memory
Efficiency:
- Uses less memory compared to Breadth-First
Search (BFS) as it only needs to store the stack or recursion stack.
2. Simplicity of
Implementation:
- Relatively straightforward to implement,
especially with recursion.
3. Applications in
Graph Problems:
- Useful for solving various graph-related
problems like topological sorting, connected components, and cycle detection.
--------------------------------------------
Disadvantages of DFS:
1. Incomplete Path
Information:
- In its basic form, DFS might not retain
information about all paths between two vertices.
2. Non-Optimal for
Shortest Path:
- DFS may not find the shortest path between
two vertices in an unweighted graph.
3. Stack Overflow:
- For very deep graphs, DFS using recursion
might lead to a stack overflow.
---------------------------------------------------
Applications:
1. Path Finding:
- DFS can be used to find paths in mazes or
maps.
2. Network
Analysis:
- Identifying connected components helps in
network analysis, such as finding clusters in social networks.
3. Database Query
Optimization:
- Used in query optimization in databases.
4. Puzzle Solving:
- Solving puzzles like the N-Queens problem.
5. Dependency
Resolution:
- In software development, DFS can be used
to resolve dependencies between modules or libraries.
------------------------------------------------------------
Breadth First
Graph Traversal
Breadth-first search (BFS) is a graph traversal algorithm that explores all the vertices of a
graph level by level, visiting all the neighbours of a vertex before moving on
to the next level. BFS uses a queue to maintain the order of vertices to be
processed.
Basic Terminology:
1. Vertex (Node): A fundamental
unit of a graph.
2. Edge: A connection
between two vertices that may have a direction (in the case of a directed
graph).
3. Graph: A collection of
vertices and edges that may be directed or undirected.
4. Adjacency: Two vertices are
adjacent if there is an edge connecting them.
5. Visited: A vertex is
marked as visited during traversal to avoid revisiting the same vertex.
6. Queue: Used to keep
track of vertices to visit.
--------------------------------------
Features:
1. Breadth-First
Nature:
BFS explores all the vertices at the current level before moving on to the next
level.
2. Queue Usage: A queue is
employed to maintain the order of vertices to be processed.
3. Optimal for
Shortest Paths:
BFS can find the shortest path in an unweighted graph because it explores
vertices in increasing order of distance from the starting vertex.
4. Applications: BFS is used for
shortest path finding, minimum spanning trees, network flow problems, and
solving puzzles.
------------------------------------------
Structure:
1. Initialization: Start from an
initial vertex and mark it as visited.
2. Enqueue: Enqueue the
initial vertex into the queue.
3. While Queue is
Not Empty:
- Dequeue a vertex from the front of the
queue.
- Visit the dequeued vertex.
- Enqueue all unvisited neighbors of the
dequeued vertex.
4. Completion: Continue the
process until the queue is empty.
------------------------------------------------------------------------
C++ Example: cpp
#include
<iostream>
#include
<vector>
#include
<queue>
using namespace
std;
class Graph {
private:
int V;
vector<vector<int>> adjList;
public:
Graph(int vertices) : V(vertices),
adjList(vertices) {}
void addEdge(int i, int j) {
adjList[i].push_back(j);
adjList[j].push_back(i); // For
undirected graph
}
void BFS(int start) {
vector<bool> visited(V, false);
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int current = q.front();
q.pop();
cout << current <<
" ";
for (int neighbor :
adjList[current]) {
if (!visited[neighbor]) {
q.push(neighbor);
visited[neighbor] = true;
}
}
}
}
};
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
cout << "BFS starting from
vertex 0: ";
g.BFS(0);
return 0;
}
--------------------------------------------
Python Example: python
from collections
import deque
class Graph:
def __init__(self, vertices):
self.V = vertices
self.adjList = [[] for _ in
range(self.V)]
def addEdge(self, i, j):
self.adjList[i].append(j)
self.adjList[j].append(i) # For undirected graph
def BFS(self, start):
visited = [False] * self.V
queue = deque([start])
visited[start] = True
while queue:
current = queue.popleft()
print(current, end=" ")
for neighbor in
self.adjList[current]:
if not visited[neighbor]:
queue.append(neighbor)
visited[neighbor] = True
# Example usage:
g = Graph(4)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
print("BFS
starting from vertex 0:", end=" ")
g.BFS(0)
In both examples,
the graph has four vertices, and BFS is initiated from vertex 0. The visited vertices
are printed in the order they are explored, following the breadth-first
traversal pattern. The queue is used to maintain the order of vertices to be
processed.
------------------------------------
Breadth-First Graph Traversal Types:
1. Classic Breadth-First Search (BFS):
- Description: Visit a vertex and enqueue
all its neighbors before moving on to the next level.
- Implementation: Utilizes a queue.
2. Shortest Path Finding:
- Description: BFS can be used to find the
shortest path in an unweighted graph.
- Application: Navigation systems, network
routing.
3. Minimum Spanning Tree (BFS Tree):
- Description: Construct a minimum spanning
tree using BFS.
- Application: Network design, circuit
wiring.
4. Network Flow:
- Description: BFS is used in algorithms
like the Edmonds-Karp algorithm for maximum flow in a network.
- Application: Network optimization, traffic
engineering.
----------------------------------------------------------
Advantages of BFS:
1. Shortest Path
Finding:
- Finds the shortest path in an unweighted
graph.
2. Completeness:
- Visits all vertices and edges, ensuring
completeness.
3. Optimality for
Shortest Path:
- In an unweighted graph, the first time a
vertex is visited, it is reached via the shortest path.
4. Applications in
Networking:
- Used in network-related problems like
routing and flow control.
----------------------------------------------
Disadvantages of BFS:
1. Memory
Requirements:
- Can be memory-intensive for large graphs,
especially with sparse adjacency matrices.
2. Limited Use for
Weighted Graphs:
- Not suitable for finding the shortest path
in graphs with weighted edges.
3. Inefficiency in
Dense Graphs:
- In dense graphs, where the number of edges
is close to the maximum possible, BFS might be less efficient.
------------------------------------------------------
Applications:
1. Shortest Path
Finding:
- Navigation systems, network routing.
2. Network
Connectivity:
- Ensuring network connectivity, and identifying
unreachable areas.
3. Data Crawling
and Search Engines:
- BFS can be used to crawl and index web
pages.
4. Maze Solving:
- Finding a path through a maze.
5. Garbage
Collection:
- Used in garbage collection algorithms in
programming languages.
Breadth-First Search is a versatile algorithm with applications in various domains. Its ability to find the shortest path in unweighted graphs and its role in network flow problems make it a valuable tool in graph theory and computer science.
=====================================================
0 Comments