Graph
Graph Terminology
Vertex (Node): Fundamental part of a graph where data is stored.
Edge: Connection between two vertices.
Adjacency: Two vertices are adjacent if they are connected by an edge.
Degree: Number of edges connected to a vertex.
Path: Sequence of vertices connected by edges.
Cycle: Path that starts and ends at the same vertex.
Directed Graph (Digraph): Graph where edges have a direction.
Undirected Graph: Graph where edges do not have a direction.
Weighted Graph: Graph where edges have weights (values).
Graph Representation
Adjacency Matrix: 2D array where
matrix[i][j]indicate presence/weight of edge between vertexiandj.Adjacency List: Array of lists, where each list represents the neighbors of a vertex.
Adjacency Matrix:
#include <iostream>
#include <vector>
using namespace std;
void printMatrix(vector<vector<int>>& matrix) {
for (const auto& row : matrix) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
}
int main() {
int n = 4; // Number of vertices
vector<vector<int>> adjMatrix(n, vector<int>(n, 0));
// Adding edges
adjMatrix[0][1] = 1;
adjMatrix[1][2] = 1;
adjMatrix[2][3] = 1;
adjMatrix[3][0] = 1;
printMatrix(adjMatrix);
return 0;
}Breadth-First Search (BFS)
Breadth-first search (BFS) is an algorithm for traversing tree or graph data structures. Given a node, the algorithm explores all the neighbor nodes first before moving to the next level neighbors, repeating this process until there are no more nodes to visit.
Concept
BFS explores all neighbors of a vertex before moving to the next level.
Uses a queue to keep track of vertices to visit.
Good for finding shortest paths in unweighted graphs.
ComplexityTime and Space Complexity Time complexity:
O(V + E)Space complexity:
O(V)where
Vis the number of vertices andEis the number of edges
BFS Algorithm
Start from a source vertex.
Mark the source vertex as visited and enqueue it.
While the queue is not empty:
Dequeue a vertex.
For each adjacent vertex, if it hasn't been visited, mark it as visited and enqueue it.
Where to use BFS Algorithm?
When we need to print or analyze data by level in the graph or tree
Finding the shortest distance between two nodes
When we need to compare a parent to its direct children
BFS Example in C++
void bfs(int start, vector<vector<int>>& adjList) {
vector<bool> visited(adjList.size(), false);
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int vertex = q.front();
q.pop();
cout << vertex << " ";
// Visit all neighbors of that vertex : adjList[vertex]
for (int neighbor : adjList[vertex]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
int main() {
int n = 4;
vector<vector<int>> adjList(n);
adjList[0].push_back(1);
adjList[0].push_back(2);
adjList[1].push_back(3);
adjList[1].push_back(4);
cout << "BFS starting from vertex 0: ";
bfs(0, adjList); // 0 1 2 3 4
return 0;
}BFS related Leet code questions:
Depth-First Search (DFS)
Depth-First Search (DFS) is a type of search algorithm that explores a graph by traversing as far as possible along each branch before backtracking. It's considered "depth-first" because at each node, if there are children, the algorithm always explores deeper paths until a leaf node is finally visited or some condition is met. The algorithm starts at the root node and explores the left and right subtrees by going deeper into the tree as it processes nodes, instead of visiting all the children of a given node before moving on.
Concept
DFS explores as far as possible along each branch before backtracking.
Uses a stack (or recursive function call stack) to keep track of vertices to visit.
Good for exploring all vertices and edges, finding connected components, and topological sorting
DFS Algorithm
Iterative approaches to DFS traversal involve using a loop and a stack for traversal
Start from a source vertex.
Mark the source vertex as visited.
For each adjacent vertex, if it hasn't been visited, recursively perform DFS on it.
Where to use DFS Algorithm?
DFS is particularly useful for backtracking algorithms
DFS is better suited for finding the connected components of a graph and for detecting cycles in a graph.
In binary trees or n-ary trees, DFS is used for preorder, inorder, and postorder traversals.
DFS Example in C++
Recursive version:
#include <iostream>
#include <vector>
using namespace std;
// Function to perform DFS on the graph
void dfs(int node, vector<int> adj[], vector<bool>& vis, vector<int>& ans) {
vis[node] = true; // Mark the current node as visited
ans.push_back(node); // Add the current node to the result
// Visit all the adjacent nodes of the current node
for (auto a : adj[node]) {
if (!vis[a]) { // If the adjacent node is not visited
dfs(a, adj, vis, ans); // Recursively visit the adjacent node
}
}
}
// Function to return a list containing the DFS traversal of the graph
vector<int> dfsOfGraph(int n, vector<int> adj[]) {
vector<bool> vis(n, false); // Initialize a visited array with false
vector<int> ans; // Vector to store the result of DFS traversal
// Perform DFS from each node (in case the graph is disconnected)
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
dfs(i, adj, vis, ans);
}
}
return ans; // Return the result of DFS traversal
}
int main() {
int n = 5; // Number of nodes in the graph
vector<int> adj[n]; // Adjacency list representation of the graph
// Add edges to the graph
adj[0].push_back(1);
adj[0].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
// Perform DFS and get the result
vector<int> result = dfsOfGraph(n, adj);
// Print the result
for (int i : result) {
cout << i << " ";
}
return 0;
}
Iterative version:
void dfs(vector<vector<int>> &adjList, int start) {
vector<bool> visited(adjList.size(), false);
stack<int> s;
s.push(start);
while (!s.empty()) {
int vertex = s.top();
s.pop();
if (!visited[vertex]) {
visited[vertex] = true;
cout << vertex << " ";
// Reverse the order in which neighbors are added to the stack
for (auto it = adjList[vertex].rbegin(); it != adjList[vertex].rend(); ++it) {
if (!visited[*it]) {
s.push(*it);
}
}
}
}
}
int main() {
int n = 4;
vector<vector<int>> adjList(n);
adjList[0].push_back(1);
adjList[0].push_back(2);
adjList[1].push_back(3);
adjList[1].push_back(4);
cout << "DFS starting from vertex 0: ";
dfs(0, adjList); // 0 1 3 4 2
return 0;
}Difference Between BFS and DFS?
BFS is a traversal approach in which we first walk through all nodes on the same level before moving on to the next level.
DFS is also a traversal approach in which the traverse begins at the root node and proceeds through the nodes as far as possible until we reach the node with no unvisited nearby nodes.
BFS uses Queue data structure
DFS uses Stack Data Structure
It works on the concept of FIFO (First In First Out).
It works on the concept of LIFO (Last In First Out).
BFS is more suitable for searching vertices closer to the given source
DFS is more suitable when there are solutions away from source.
If the tree is very deep and solutions are rare, depth first search (DFS) might take an extremely long time, but BFS could be faster.
If the tree is very wide, a BFS might need too much memory, so it might be completely impractical. DFS is faster
BFS acts better when the target stays closer to the source.
DFS acts better when the target stays farther from the source.
It traverses a path according to the tree level.
It traverses a path according to the tree depth.
Dijkstra's Algorithm
Concept
Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph.
Uses a priority queue to always extend the shortest known path.
Works only with graphs that have non-negative weights.
Dijkstra's Algorithm Steps
Initialize the distance to the source vertex as 0 and to all other vertices as infinity.
Use a priority queue to explore the vertex with the smallest known distance.
For each neighbor of the current vertex, if a shorter path is found, update the distance and enqueue the neighbor.
Repeat until all vertices are processed.
How Dijkstra's Algorithm Works
Initialization:
Set the distance to the source node to zero (
dist[source] = 0).Set the distance to all other nodes to infinity (
dist[node] = ∞for allnode ≠ source).Create a priority queue (or a min-heap) and insert the source node with distance zero.
Processing Nodes:
While the priority queue is not empty:
Extract the node
uwith the smallest distance from the priority queue.For each neighbor
vofu:Calculate the distance from the source to
vthroughu(i.e.,dist[u] + weight(u, v)).If this distance is less than the currently known distance to
v(dist[v]):Update
dist[v]with the new shorter distance.Insert
vinto the priority queue with the updated distance.
Termination:
The algorithm terminates when all nodes have been processed. The resulting
distarray contains the shortest distances from the source node to all other nodes.
Complexity of Dijkstra's Algorithm
The complexity of Dijkstra's algorithm depends on the implementation of the priority queue:
Using a simple array or linked list:
O(V^2), where V is the number of vertices.Using a binary heap:
O((V+E)logV), where E is the number of edges.
In practice, the binary heap implementation is often used due to its simplicity and efficiency.
Dijkstra's Algorithm Example in C++
void dijkstra(int start, vector<vector<pair<int, int>>>& adjList) {
vector<int> dist(adjList.size(), INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int>;
greater<pair<int, int>>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
int currentDist = pq.top().first;
int vertex = pq.top().second;
pq.pop();
if (currentDist > dist[vertex]) continue;
for (auto& edge : adjList[vertex]) {
int neighbor = edge.first;
int weight = edge.second;
if (dist[vertex] + weight < dist[neighbor]) {
dist[neighbor] = dist[vertex] + weight;
pq.push({dist[neighbor], neighbor});
}
}
}
cout << "Shortest distances from vertex " << start << ":\n";
for (int i = 0; i < dist.size(); ++i) {
cout << "Vertex " << i << ": " << dist[i] << endl;
}
}
int main() {
int n = 4;
vector<vector<pair<int, int>>> adjList(n);
adjList[0].push_back({1, 1});
adjList[1].push_back({2, 1});
adjList[2].push_back({3, 1});
adjList[3].push_back({0, 1});
dijkstra(0, adjList);
return 0;
}Leet Code Problems:
Sum of Each Level in BFS Traversal
void BFS(vector<vector<int>> &adj, int source)
{
vector<bool> visited(adj.size(), false);
queue<int> q;
visited[source] = true;
q.push(source);
q.push(-1); // Marker for the end of a level
int levelSum = 0; // Initialize sum of the current level
while (!q.empty())
{
int top = q.front();
q.pop();
if (top == -1)
{
cout << "Sum of level: " << levelSum << endl;
levelSum = 0; // Reset sum for the next level
if (!q.empty())
{
q.push(-1); // Marker for the next level
}
}
else
{
levelSum += top; // Assuming the node value is the index
cout << top << endl;
for (auto i : adj[top])
{
if (!visited[i])
{
visited[i] = true;
q.push(i);
}
}
}
}
}
void solve()
{
//* Sometimes you win, sometimes you learn..." - Good Wisher
int n = 7; // Assuming there are 5 nodes in the graph
vector<vector<int>> adj(n); // Initialize with size n
adj[0].push_back(1);
adj[0].push_back(2);
adj[1].push_back(3);
adj[1].push_back(4);
adj[2].push_back(5);
adj[2].push_back(6);
BFS(adj, 0);
}Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.
class Solution {
public:
vector<double> ans;
void levelBySum(TreeNode* root) {
double sum = 0;
double n = 0;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
double n = size(q);
sum = 0;
for (int i = 0; i < n; i++) {
auto top = q.front();
q.pop();
sum += top->val;
if (top->left)
q.push(top->left);
if (top->right)
q.push(top->right);
}
double value = (double)sum / n;
ans.push_back(value);
}
}
vector<double> averageOfLevels(TreeNode* root) {
levelBySum(root);
return ans;
}
};iven the root of a binary tree, return the sum of values of its deepest leaves.
class Solution {
public:
int deepestLeavesSum(TreeNode* root) {
int sum = 0;
int n = 0;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int n = size(q);
sum = 0; // reset after level
for (int i = 0; i < n; i++) {
auto top = q.front();
q.pop();
sum += top -> val;
if (top->left)
q.push(top->left);
if (top->right)
q.push(top->right);
}
}
return sum;
}
};Last updated