🔁Data Structures Unit 10 – Graphs and their Representations

What Are Graphs?

• Graphs are non-linear data structures consisting of vertices (nodes) and edges that connect them
• Vertices represent entities or objects, while edges represent relationships or connections between vertices
• Graphs can be directed (edges have a specific direction) or undirected (edges have no specific direction)
• The degree of a vertex is the number of edges connected to it
  • In directed graphs, the in-degree is the number of incoming edges, and the out-degree is the number of outgoing edges
• Graphs can be weighted, where edges have associated values or costs, or unweighted, where all edges are considered equal
• Graphs are used to model various real-world scenarios, such as social networks, transportation networks, and computer networks
• The order of a graph is the number of vertices it contains, while the size of a graph is the number of edges it has

Types of Graphs

• Simple graphs have no self-loops (edges that connect a vertex to itself) or multiple edges between the same pair of vertices
• Multigraphs allow multiple edges between the same pair of vertices
• Directed acyclic graphs (DAGs) are directed graphs with no cycles, meaning there is no path that starts and ends at the same vertex
• Complete graphs have an edge between every pair of vertices
  • In a complete graph with $n$ vertices, there are $\frac{n(n-1)}{2}$ edges
• Bipartite graphs have vertices that can be divided into two disjoint sets, such that every edge connects a vertex from one set to a vertex in the other set
• Planar graphs can be drawn on a plane without any edges crossing each other
• Weighted graphs have edges with associated values or costs, representing distances, capacities, or other attributes
• Trees are connected acyclic undirected graphs, where there is exactly one path between any pair of vertices

Graph Representations

• Adjacency matrix represents a graph using a 2D array of size $V \times V$, where $V$ is the number of vertices
  • The element at position $(i, j)$ is 1 if there is an edge from vertex $i$ to vertex $j$, and 0 otherwise
  • Adjacency matrices are suitable for dense graphs and provide constant-time access to check if an edge exists between two vertices
• Adjacency list represents a graph using an array of linked lists, where each element in the array corresponds to a vertex
  • Each linked list contains the vertices that are adjacent to the corresponding vertex
  • Adjacency lists are suitable for sparse graphs and provide efficient traversal of the graph
• Edge list represents a graph as a list of edges, where each edge is represented as a pair of vertices
  • Edge lists are simple to implement but may require additional processing to determine adjacency or perform graph traversals
• Incidence matrix represents a graph using a 2D array of size $V \times E$, where $V$ is the number of vertices and $E$ is the number of edges
  • The element at position $(i, j)$ is 1 if vertex $i$ is incident to edge $j$, and 0 otherwise
  • Incidence matrices are less commonly used due to their higher space complexity compared to adjacency matrices or lists

Graph Traversal Algorithms

• Depth-first search (DFS) explores a graph by visiting as far as possible along each branch before backtracking
  • DFS can be implemented using a stack data structure or recursion
  • DFS is useful for detecting cycles, finding connected components, and solving maze or puzzle problems
• Breadth-first search (BFS) explores a graph by visiting all the neighbors of a vertex before moving to the next level
  • BFS can be implemented using a queue data structure
  • BFS is useful for finding the shortest path in unweighted graphs, detecting bipartite graphs, and solving level-based problems
• Topological sorting is an ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge $(u, v)$, vertex $u$ comes before vertex $v$ in the ordering
  • Topological sorting can be performed using DFS or Kahn's algorithm
  • Topological sorting is useful for scheduling tasks with dependencies, course prerequisites, and build systems
• Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights
  • Dijkstra's algorithm maintains a priority queue of vertices based on their tentative distances from the source
  • Dijkstra's algorithm is widely used in network routing protocols and GPS navigation systems

Graph Applications

• Social networks use graphs to represent connections between users, where vertices represent individuals and edges represent friendships or interactions
  • Graph algorithms can be used to recommend friends, detect communities, and analyze influence propagation
• Transportation networks model roads, railways, or flight routes as graphs, with vertices representing locations and edges representing connections
  • Graph algorithms can be used to find the shortest path, minimize travel time, or optimize resource allocation
• Computer networks represent devices (routers, switches) as vertices and communication links as edges
  • Graph algorithms can be used for network topology design, routing protocols, and fault tolerance analysis
• Dependency graphs model relationships between tasks or components, where vertices represent tasks and edges represent dependencies
  • Graph algorithms can be used for task scheduling, resource allocation, and deadlock detection
• Compiler optimization uses graphs to represent program flow, with vertices representing basic blocks and edges representing control flow
  • Graph algorithms can be used for code optimization, dead code elimination, and register allocation
• Bioinformatics uses graphs to represent biological networks, such as protein-protein interaction networks or metabolic pathways
  • Graph algorithms can be used for network analysis, community detection, and drug target identification

Implementing Graphs in Code

• Graph implementations typically use classes or structures to represent vertices and edges
  • Vertex classes may contain data fields, such as vertex labels or weights, and methods for adding or removing edges
  • Edge classes may contain data fields, such as source and destination vertices, and weight (if applicable)
• Adjacency matrix implementation uses a 2D array to represent the graph
  • The size of the matrix is $V \times V$, where $V$ is the number of vertices
  • The element at position $(i, j)$ represents the presence or absence of an edge between vertices $i$ and $j$
  • Adjacency matrices provide constant-time access to check if an edge exists but require $O(V^2)$ space complexity
• Adjacency list implementation uses an array of linked lists to represent the graph
  • Each element in the array corresponds to a vertex, and the linked list contains the adjacent vertices
  • Adjacency lists are space-efficient for sparse graphs and provide efficient traversal of the graph
  • Adjacency lists require $O(V + E)$ space complexity, where $E$ is the number of edges
• Graph traversal algorithms (DFS and BFS) can be implemented using recursive or iterative approaches
  • Recursive implementations use function calls and backtracking to explore the graph
  • Iterative implementations use data structures like stacks (for DFS) or queues (for BFS) to keep track of the vertices to visit
• Shortest path algorithms (Dijkstra's algorithm) can be implemented using priority queues to efficiently select the vertex with the minimum tentative distance
  • The priority queue can be implemented using a heap data structure for efficient updates and extractions

Common Graph Problems

• Shortest path problem aims to find the path with the minimum total weight between two vertices in a weighted graph
  • Dijkstra's algorithm is commonly used for solving the single-source shortest path problem
  • Floyd-Warshall algorithm can be used to find the shortest paths between all pairs of vertices
• Minimum spanning tree (MST) problem seeks to find a tree that connects all vertices in a weighted undirected graph with the minimum total edge weight
  • Kruskal's algorithm builds the MST by selecting edges in increasing order of weight, avoiding cycles
  • Prim's algorithm builds the MST by starting from an arbitrary vertex and greedily adding the nearest vertex to the tree
• Graph coloring problem aims to assign colors to vertices such that no two adjacent vertices have the same color
  • Graph coloring has applications in scheduling, register allocation, and frequency assignment
  • The minimum number of colors required to color a graph is called the chromatic number
• Maximum flow problem seeks to find the maximum flow that can be sent from a source vertex to a sink vertex in a flow network
  • Ford-Fulkerson algorithm and its variations (Edmonds-Karp, Dinic's algorithm) are used to solve the maximum flow problem
  • Maximum flow algorithms have applications in network connectivity, bipartite matching, and image segmentation
• Traveling salesman problem (TSP) aims to find the shortest possible route that visits each vertex exactly once and returns to the starting vertex
  • TSP is an NP-hard problem, and exact solutions are computationally expensive for large instances
  • Heuristic algorithms, such as nearest neighbor, Christofides algorithm, and genetic algorithms, provide approximate solutions to TSP

Advanced Graph Concepts

• Strongly connected components (SCCs) are maximal subgraphs in a directed graph where there is a path from each vertex to every other vertex within the subgraph
  • Kosaraju's algorithm and Tarjan's algorithm can be used to find SCCs in a directed graph
  • SCCs have applications in social network analysis, web graph analysis, and model checking
• Minimum cut problem aims to find the minimum number of edges that need to be removed to disconnect a graph into two or more components
  • The max-flow min-cut theorem states that the maximum flow in a network is equal to the capacity of the minimum cut
  • Karger's algorithm and Stoer-Wagner algorithm are used to find minimum cuts in undirected graphs
• Network flow problems involve finding the maximum flow or minimum cost flow in a network with edge capacities and costs
  • Minimum cost flow problem seeks to find the flow with the minimum total cost while satisfying flow conservation and capacity constraints
  • Successive shortest path algorithm and cycle canceling algorithm are used to solve minimum cost flow problems
• Matchings in graphs are sets of edges that do not share any common vertices
  • Maximum matching problem aims to find a matching with the maximum number of edges
  • Bipartite matching problem seeks to find a maximum matching in a bipartite graph
  • Hungarian algorithm and Hopcroft-Karp algorithm are used to solve bipartite matching problems
• Graph isomorphism problem determines whether two graphs are isomorphic, i.e., they have the same structure but may have different vertex labels
  • Graph isomorphism is a computationally challenging problem, and no polynomial-time algorithm is known for the general case
  • Practical algorithms, such as Nauty and Bliss, use canonical labeling and backtracking to test graph isomorphism