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 vertex i and j.

• 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.

Complexity

Time and Space Complexity Time complexity: O(V + E)

Space complexity: O(V)

where V is the number of vertices and E is the number of edges

BFS Algorithm

1. Start from a source vertex.

2. Mark the source vertex as visited and enqueue it.

3. 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:

Breadth-First Search - LeetCodeLeetCode

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

1. Iterative approaches to DFS traversal involve using a loop and a stack for traversal

2. Start from a source vertex.

3. Mark the source vertex as visited.

4. 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	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

1. Initialize the distance to the source vertex as 0 and to all other vertices as infinity.

2. Use a priority queue to explore the vertex with the smallest known distance.

3. For each neighbor of the current vertex, if a shorter path is found, update the distance and enqueue the neighbor.

4. Repeat until all vertices are processed.

How Dijkstra's Algorithm Works

1. 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 all node ≠ source).

   • Create a priority queue (or a min-heap) and insert the source node with distance zero.

2. Processing Nodes:

   • While the priority queue is not empty:

     • Extract the node u with the smallest distance from the priority queue.

     • For each neighbor v of u:

       • Calculate the distance from the source to v through u (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 v into the priority queue with the updated distance.

3. Termination:

   • The algorithm terminates when all nodes have been processed. The resulting dist array 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:

1. Using a simple array or linked list: O(V^2), where V is the number of vertices.

2. Using a binary heap: O((V+E)log⁡V), 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);
}

637. Average of Levels in Binary Tree :

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;
    }
};

1302. Deepest Leaves Sum

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;
    }
};