In computing, a graph is an abstract data structure that represents relationships between objects through a collection of nodes (also called vertices) connected by edges. Graphs are fundamental mathematical structures used to model pairwise relations between objects and serve as the foundation for numerous algorithms and applications in computer science, from social networks to route planning and beyond.
Structure and Components
A graph G is formally defined as an ordered pair G = (V, E) where V is a set of vertices or nodes, and E is a set of edges connecting these vertices. Each edge represents a relationship between two nodes. In an undirected graph, edges have no direction and represent bidirectional relationships, while in a directed graph (or digraph), edges have a specific direction from one vertex to another, indicating a one-way relationship.
Vertices can contain data or represent entities, while edges may have associated weights or costs that represent the strength, distance, or expense of the relationship. A weighted graph assigns numerical values to edges, enabling algorithms to optimize paths based on these weights. Graphs can also be classified as connected (where there is a path between any two vertices) or disconnected, and as cyclic (containing cycles) or acyclic.
Types of Graphs
Several specialized graph types exist based on their structural properties. A complete graph contains edges between every pair of vertices, while a sparse graph has relatively few edges compared to the number of vertices. A tree is a special type of graph that is connected and acyclic, with exactly one path between any two vertices. A bipartite graph divides vertices into two disjoint sets where edges only connect vertices from different sets.
Directed acyclic graphs (DAGs) are directed graphs containing no directed cycles, making them useful for representing dependencies and partial orders. Planar graphs can be drawn on a plane without edge crossings, while regular graphs have the same degree (number of edges) for every vertex.
Graph Representation
Graphs can be represented in computer memory through several methods, each with distinct advantages. The adjacency matrix uses a two-dimensional array where rows and columns represent vertices, with boolean values or weights indicating connections. This representation provides O(1) edge lookup time but requires O(V²) space, making it suitable for dense graphs.
The adjacency list representation stores a list of neighbors for each vertex, typically using arrays, linked lists, or hash tables. This approach requires O(V + E) space and is more memory-efficient for sparse graphs, though edge lookup takes O(degree) time. Edge lists simply store all edges as pairs of vertices, useful for certain algorithms but inefficient for neighbor queries.
Graph Traversal Algorithms
Two fundamental graph traversal algorithms are breadth-first search (BFS) and depth-first search (DFS). BFS explores vertices level by level, using a queue data structure, and guarantees finding the shortest path in unweighted graphs. DFS explores as far as possible along each branch before backtracking, using a stack or recursion, and is useful for detecting cycles and exploring connected components.
Both algorithms have O(V + E) time complexity and are foundational for more complex graph algorithms. Variations include iterative deepening DFS, bidirectional search, and priority-first search variants.
Applications and Use Cases
Graphs have extensive applications across computing domains. Social networks model users as vertices and relationships as edges, enabling friend recommendation and influence analysis. Web page linking structures form directed graphs used by search engines for page ranking algorithms like PageRank.
Network routing protocols use weighted graphs to determine optimal paths for data transmission, while transportation systems model roads and connections for GPS navigation. Dependency management in software builds uses directed acyclic graphs to determine compilation order. Knowledge graphs represent entities and their relationships for semantic search and artificial intelligence applications.
Database systems employ graph databases for storing and querying highly connected data, while compilers use control flow graphs to represent program execution paths. Game development utilizes graphs for pathfinding algorithms like A* and for representing game states and transitions.
Graph Algorithms
Numerous specialized algorithms solve specific graph problems. Dijkstra's algorithm finds shortest paths from a source vertex in weighted graphs with non-negative edge weights, while the Bellman-Ford algorithm handles negative weights. The Floyd-Warshall algorithm computes all-pairs shortest paths.
Minimum spanning tree algorithms like Kruskal's and Prim's find subsets of edges connecting all vertices with minimum total weight. Topological sorting arranges vertices in directed acyclic graphs according to dependency order. Graph coloring algorithms assign colors to vertices such that adjacent vertices have different colors, useful for scheduling and register allocation.
Network flow algorithms solve problems involving flow through networks with capacity constraints, while matching algorithms find optimal pairings in bipartite graphs. Community detection algorithms identify clusters and subgroups within large graphs, essential for social network analysis and recommendation systems.