26.2. Graphs

A graph is a non-linear data structure consisting of vertices (nodes) and edges (connections). It can be:

• Directed or Undirected
• Weighted or Unweighted
• Cyclic or Acyclic

A graph is a structure made up of vertices (which can be thought of as points or nodes) connected by edges (which can be considered as lines or links). Graphs can be categorized based on several characteristics:

1. Directed vs. Undirected: In a directed graph, edges have a direction, meaning they point from one vertex to another. In contrast, undirected graphs have edges that don’t have a fixed direction, establishing a mutual connection.
2. Weighted vs. Unweighted: In weighted graphs, edges have weights or costs associated with them, which could represent distance, time, etc. Unweighted graphs treat all edges as having the same weight.
3. Cyclic vs. Acyclic: A cyclic graph contains at least one closed loop where you can start at a vertex and return to it without retracing any edges. An acyclic graph does not have such loops.

Think of a graph like a city map. Each intersection is a vertex (node), and the roads connecting them are the edges (links). If roads have speed limits (representing weights), the map becomes a weighted graph. If you can travel both ways on the roads, it’s undirected; if some roads only allow travel one way, it’s directed. If you can start at one intersection, go around the city, and return to where you started, that’s cyclic; if you can only go one way and never return, it’s acyclic.

1. Adjacency Matrix:
   • 2D array: matrix[i][j] = 1 if edge exists.
   • Space: O(V²)
2. Adjacency List:
   • Each vertex stores a list of adjacent vertices.
   • Space: O(V + E)

Graphs can be represented in mainly two ways:

1. Adjacency Matrix: This is a two-dimensional array (a grid) where rows and columns represent vertices. If there's an edge between vertex i and vertex j, then matrix[i][j] is set to 1 (or the weight of the edge if it's a weighted graph). This representation is straightforward but can consume a lot of space, especially for sparse graphs (graphs with relatively few edges), leading to O(V²) space complexity.

2. Adjacency List: In this representation, each vertex has a list that contains all vertices it is connected to (its adjacent vertices). This is more memory efficient, especially for sparse graphs, with space complexity of O(V + E), where V is the number of vertices and E is the number of edges.

Imagine representing your group of friends with an adjacency matrix on a piece of paper, where each friend is a row and a column in a grid. If two friends know each other, you can mark it with a check. However, if you have a huge group and only a few connections, this grid can look mostly empty. On the other hand, using an adjacency list, each friend can create a personal list of who they know. This method is more efficient and only lists the connections rather than filling a whole grid.

Breadth-First Search (BFS):

• Uses a queue.
• Explores neighbors level by level.
• Time: O(V + E) Depth-First Search (DFS):
• Uses a stack or recursion.
• Explores one branch deeply before backtracking.
• Time: O(V + E)

Graph traversal is the process of visiting all the vertices in a graph in a systematic way. The two primary methods are:

1. Breadth-First Search (BFS): This technique uses a queue to explore the graph. It starts from a selected vertex (the source), visits all its neighbors, then moves on to their neighbors, effectively exploring level by level. BFS is beneficial for finding the shortest path in unweighted graphs. Its time complexity is O(V + E), where V is vertices and E is edges.

2. Depth-First Search (DFS): This method can be implemented using a stack (or recursion). It explores as deep as possible down one branch before backtracking to explore other branches. DFS is useful for searching paths, detecting cycles, and topological sorting. It also has a time complexity of O(V + E).

Imagine exploring a large library. In a BFS, you would check every bookshelf on the main floor before going upstairs, like visiting each neighbor before moving on. In contrast, a DFS would be like picking one bookshelf, checking every book before moving to another bookshelf, delving deep into each section before returning to explore others. Both methods help you eventually find all the books, just in different orders.

• Shortest Path (Dijkstra, Bellman-Ford)
• Cycle Detection
• Topological Sorting (for DAGs)
• Minimum Spanning Tree (Kruskal’s, Prim’s)
• Network Flow (Ford-Fulkerson)

Graphs have various practical applications in computer science and real-world problem solving. Some key applications include:

1. Shortest Path Algorithms: These are used to find the shortest distance between two vertices in weighted graphs. Dijkstra’s and Bellman-Ford are two popular algorithms for this purpose.
2. Cycle Detection: It's important to determine if there are cycles in a graph, which helps understand the structure or behavior of networks and dependency graphs.
3. Topological Sorting: Used for Directed Acyclic Graphs (DAGs), this orders vertices in a way that each vertex appears before its successors, useful in scheduling tasks.
4. Minimum Spanning Tree (MST): This helps in connecting all vertices with the minimum possible total edge weight using algorithms like Kruskal’s and Prim’s.
5. Network Flow: Algorithms such as the Ford-Fulkerson method are used to find the maximum flow in flow networks, applicable in resource management and logistics.

Consider a city’s transportation system. Finding the shortest path, like which subway route to take, uses Dijkstra’s algorithm. If you’re organizing event workflows, you might use topological sorting to schedule tasks, ensuring prerequisites are met. Detecting cycles can help in project management to avoid any tasks looping back unnecessarily.

Used in weighted graphs (non-negative edges) to find the shortest path from a source to all vertices.

• Time: O((V + E) log V) with Min-Heap

Dijkstra's Algorithm is specifically designed for finding the shortest path in graphs with non-negative weights (costs on edges). The algorithm works as follows:

1. Initialize the source vertex distance to 0 and all other distances to infinity.
2. While there are vertices to explore, select the vertex with the smallest known distance and explore its neighbors, updating their distances if a shorter path is found through the current vertex.
3. Use a priority queue (like a Min-Heap) to efficiently retrieve the next vertex with the smallest distance to explore. The time complexity is O((V + E) log V) due to the operations on the priority queue.

Imagine you're using a GPS navigation app to find the quickest route to a destination. Dijkstra's algorithm works similarly: it starts from your current location (the source), then looks at all possible routes, keeping track of the shortest distances to other locations, until it finds the quickest path to your destination.

Prim’s Algorithm:

• Starts from any node, adds the cheapest edge to the growing MST.
• Uses priority queue. Kruskal’s Algorithm:
• Sorts all edges and adds the smallest edge that doesn’t form a cycle.
• Uses Union-Find.

Minimum Spanning Tree (MST) refers to a subset of the edges in a graph that connects all vertices without cycles and with the minimum possible total edge weight. There are primarily two algorithms to find the MST:

1. Prim’s Algorithm: It begins with a single vertex and progressively adds the smallest edge that connects a vertex in the growing MST to a vertex outside of it, using a priority queue to keep track of the most promising edges.
2. Kruskal’s Algorithm: This algorithm starts by sorting all the edges based on their weights. It then adds edges one by one, ensuring that adding an edge does not create a cycle (using a Union-Find data structure to track connected components).

Imagine building a network of roads to connect several towns efficiently. Prim’s algorithm is like starting from one town and always building the cheapest road possible to connect to another town. Kruskal’s algorithm is like surveying all possible roads in advance, sorting them by cost, then adding the cheapest ones until all towns are connected without any loops.

--