Graph Theory Basics: Nodes, Edges, and Connections

Graph theory is one of the most important areas of computer science and mathematics. A graph is a mathematical structure used to model relationships between objects. It consists of vertices (also called nodes) and edges (also called connections or links) that connect pairs of vertices. Graphs are used to model everything from social networks and computer networks to road maps and molecular structures. Understanding the basics of graph theory is essential for solving many real-world problems and is a key topic in computer science.

Types of Graphs

An undirected graph has edges that do not have a direction. If there is an edge between vertices A and B, you can travel from A to B and from B to A. A social network where friendships are mutual is an example of an undirected graph. A directed graph (or digraph) has edges with a direction. If there is a directed edge from A to B, you can travel from A to B but not necessarily from B to A. A Twitter following relationship is an example of a directed graph.

A weighted graph has edges with associated values (weights). These weights might represent distances, costs, or capacities. A road map where the weight of each edge represents the distance between cities is an example of a weighted graph. An unweighted graph treats all edges as having equal weight.

A cyclic graph contains at least one cycle, which is a path that starts and ends at the same vertex. An acyclic graph contains no cycles. A tree is a connected acyclic graph. Trees are a special type of graph that are widely used in computer science for hierarchical data structures.

Representing Graphs

An adjacency matrix is a 2D array where the element at row i and column j indicates whether there is an edge between vertices i and j. For an unweighted graph, the element is 1 if there is an edge and 0 if there is not. For a weighted graph, the element is the weight of the edge (or 0/infinity if there is no edge). Adjacency matrices provide O(1) edge lookup but use O(n²) space, which is wasteful for sparse graphs.

An adjacency list represents each vertex as a list of its neighbors. For example, vertex 0 might be connected to vertices 1 and 2, so its list contains 1 and 2. Adjacency lists use space proportional to the number of edges, which is more efficient for sparse graphs. They are the most common representation of graphs in practice.

Graph Traversal: BFS and DFS

Breadth-First Search (BFS) explores a graph level by level, visiting all neighbors of a vertex before moving to the next level. BFS uses a queue to keep track of vertices to visit. It is useful for finding the shortest path in an unweighted graph, for level-order traversal of trees, and for finding all vertices within a certain distance of a starting vertex.

Depth-First Search (DFS) explores a graph by going as deep as possible along each branch before backtracking. DFS uses a stack (or recursion) to keep track of vertices to visit. It is useful for topological sorting, detecting cycles, finding connected components, and solving puzzles that can be modeled as graphs.

Both BFS and DFS visit every vertex and edge exactly once, so they have the same time complexity: O(V + E), where V is the number of vertices and E is the number of edges. The choice between them depends on the specific problem you are solving.

Shortest Path Algorithms

Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a priority queue to efficiently select the next vertex to visit. Dijkstra's algorithm has a time complexity of O((V + E) log V) when implemented with a binary heap.

The Bellman-Ford algorithm handles graphs with negative edge weights. It relaxes all edges V-1 times, where V is the number of vertices. Bellman-Ford has a time complexity of O(VE), which is slower than Dijkstra's but more general. It can also detect negative cycles.

Trees: A Special Type of Graph

A tree is a connected acyclic graph. Trees have several important properties: there is exactly one path between any two vertices, adding an edge creates a cycle, and removing an edge disconnects the tree. Trees are used to represent hierarchical data, such as file systems, organization charts, and XML/HTML documents.

A binary tree is a tree where each vertex has at most two children, called the left child and the right child. Binary search trees (BSTs) are binary trees where the left subtree of each vertex contains only values less than the vertex's value, and the right subtree contains only values greater. BSTs support O(log n) average-case insertion, deletion, and lookup.

Real-World Applications

Graphs are used in countless real-world applications. Social networks are graphs where vertices are people and edges are friendships. Computer networks are graphs where vertices are routers and edges are connections. Road maps are graphs where vertices are intersections and edges are roads. The internet itself is a graph. Compilers use directed acyclic graphs (DAGs) to represent dependencies between instructions. Search engines use graphs to model the link structure of the web.

Understanding graph theory gives you a powerful tool for modeling and solving problems. Many problems that seem unrelated can be modeled as graph problems, and understanding the connection allows you to apply known algorithms to solve them efficiently.