10. Graph Algorithms

Graph Algorithms

Graph algorithms are critical tools in computer science for modeling and solving problems that involve interconnected objects. These algorithms operate on graphs, which consist of vertices (nodes) and edges connecting them. Graphs are used in various domains such as networking, social media analysis, pathfinding, and more.

---

What is a Graph?

A graph is defined as a collection of vertices connected by edges. The nature of these connections determines the type of graph and the algorithms applicable to it.

---

Types of Graphs

1. Undirected Graphs:

   • In these graphs, edges do not have a direction.
   • Example: A social network where friendships are mutual.

2. Directed Graphs:

   • Edges in these graphs have direction, meaning they go from one vertex to another in a specific order.
   • Example: Web pages linking to each other.

3. Weighted Graphs:

   • Here, edges have weights, representing costs, distances, or capacities.
   • Example: Road networks where each road has a different travel time.

4. Cyclic vs. Acyclic Graphs:

   • Cyclic Graph: Contains at least one cycle where a path starts and ends at the same node.
   • Acyclic Graph: Contains no cycles, such as a tree.

5. Connected vs. Disconnected Graphs:

   • Connected Graph: Every pair of vertices is reachable by some path.
   • Disconnected Graph: There are at least two vertices that cannot be connected by any path.

---

Basic Graph Algorithms

1. Breadth-First Search (BFS)

Breadth-First Search (BFS) explores a graph by starting from a source node and exploring all neighboring nodes level by level. It’s commonly used for shortest path algorithms on unweighted graphs.

Algorithm:

• Initialize a queue with the starting node.
• Mark the starting node as visited.
• While the queue is not empty:
  • Dequeue a node, visit it, and enqueue its unvisited neighbors.

Python Example:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node, end=" ")

        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

# Example graph (adjacency list representation)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(graph, 'A')  # Output: A B C D E F

---

2. Depth-First Search (DFS)

Depth-First Search (DFS) explores a graph by going as deep as possible before backtracking. It’s useful for exploring all nodes in a graph and detecting cycles.

Algorithm:

• Start at the root node (or an arbitrary node in a graph).
• Explore each branch completely before moving to the next branch (depth-wise exploration).

Python Example:

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Example graph (same as BFS)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

dfs(graph, 'A')  # Output: A B D E F C

---

3. Dijkstra’s Algorithm

Dijkstra's Algorithm finds the shortest path from a source node to all other nodes in a weighted graph. It uses a priority queue to repeatedly select the node with the smallest tentative distance and update the distances of its neighbors.

Python Example:

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# Example graph with weights (adjacency list)
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'D': 2, 'E': 5},
    'C': {'A': 4, 'F': 3},
    'D': {'B': 2},
    'E': {'B': 5, 'F': 1},
    'F': {'C': 3, 'E': 1}
}

print(dijkstra(graph, 'A'))  # Output: {'A': 0, 'B': 1, 'C': 4, 'D': 3, 'E': 6, 'F': 7}

---

4. Topological Sorting

Topological Sorting applies to directed acyclic graphs (DAGs). It produces an ordering of vertices such that for any directed edge ( u \rightarrow v ), vertex ( u ) comes before vertex ( v ) in the ordering.

Python Example:

def topological_sort(graph):
    visited = set()
    stack = []

    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)

    for node in graph:
        if node not in visited:
            dfs(node)

    return stack[::-1]

# Example graph (adjacency list)
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

print(topological_sort(graph))  # Output: ['A', 'C', 'B', 'D']

---

5. Bellman-Ford Algorithm

Bellman-Ford Algorithm computes the shortest paths from a source vertex to all vertices in a graph with possibly negative edge weights. It’s slower than Dijkstra’s algorithm but can handle graphs with negative weights.

---

6. Floyd-Warshall Algorithm

Floyd-Warshall Algorithm is an all-pairs shortest path algorithm for finding the shortest paths between every pair of vertices in a weighted graph.

---

Conclusion

Graph algorithms are essential for solving a wide variety of real-world problems, from navigation systems to social network analysis. Understanding the fundamentals of graph theory and how these algorithms work will help you tackle many complex problems in computer science.

---