Day 78: Graphs - by Harshil Chovatiya

Day 78: Graphs

Day 78 introduces one of the most versatile and powerful data structures in computer science: graphs. Graphs are collections of nodes (vertices) connected by edges, which can be either directed or undirected. They represent a wide range of relationships and connections in real-world scenarios, making them essential for modeling complex systems and solving various problems. We'll explore different types of graphs, traversal algorithms, common operations, and solve problems to deepen our understanding.

Fundamentals of Graphs

1. Definition: A graph G consists of a set of vertices (V) and a set of edges (E), which connect pairs of vertices.

2. Types of Graphs: Directed and undirected graphs, weighted and unweighted graphs, cyclic and acyclic graphs.

3. Representation: Adjacency matrix, adjacency list.

Graph Traversal Algorithms

1. Depth-First Search (DFS): Explores as far as possible along each branch before backtracking.

2. Breadth-First Search (BFS): Explores all neighbors at the present depth before moving on to the next level.

Applications and Problems

1. Shortest Path Algorithms: Dijkstra's algorithm, Bellman-Ford algorithm.

2. Minimum Spanning Tree Algorithms: Prim's algorithm, Kruskal's algorithm.

3. Topological Sorting: Ordering the vertices of a directed graph so that for each directed edge u -> v, vertex u comes before v in the ordering.

In-Depth Examples

Graph Representation using Adjacency List:

                
                
    class Graph {
        constructor() {
            this.adjList = new Map();
        }
        
        addVertex(vertex) {
            if (!this.adjList.has(vertex)) {
                this.adjList.set(vertex, []);
            }
        }
        
        addEdge(vertex1, vertex2) {
            this.adjList.get(vertex1).push(vertex2);
            // For undirected graph, add the reverse edge
            // this.adjList.get(vertex2).push(vertex1);
        }
    }
                
            

Depth-First Search (DFS):

                
                
    function dfs(graph, start, visited = new Set()) {
        visited.add(start);
        console.log(start);
        for (let neighbor of graph.adjList.get(start)) {
            if (!visited.has(neighbor)) {
                dfs(graph, neighbor, visited);
            }
        }
    }
                
            

Breadth-First Search (BFS):

                
                
    function bfs(graph, start) {
        let visited = new Set();
        let queue = [start];
        visited.add(start);
        while (queue.length > 0) {
            let vertex = queue.shift();
            console.log(vertex);
            for (let neighbor of graph.adjList.get(vertex)) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    queue.push(neighbor);
                }
            }
        }
    }
                
            

Problem: Shortest Path using Dijkstra's Algorithm:

                
                
    function dijkstra(graph, start) {
        let distances = new Map();
        let pq = new PriorityQueue();
        distances.set(start, 0);
        pq.enqueue(start, 0);
        while (!pq.isEmpty()) {
            let [vertex, dist] = pq.dequeue();
            if (distances.get(vertex) !== dist) continue;
            for (let [neighbor, weight] of graph.adjList.get(vertex)) {
                let newDist = dist + weight;
                if (!distances.has(neighbor) || newDist < distances.get(neighbor)) {
                    distances.set(neighbor, newDist);
                    pq.enqueue(neighbor, newDist);
                }
            }
        }
        return distances;
    }
                
            

Conclusion

Day 78 has provided a comprehensive understanding of graphs, their representation, traversal algorithms, and applications. Graphs are powerful tools for modeling complex relationships and solving a wide range of problems in various domains, including network analysis, route planning, and social network analysis. As we delve deeper into graph theory, let's continue exploring advanced algorithms and techniques to tackle more complex problems and refine our problem-solving skills.

Social Media