Graph (computer science)
A graph is a non-linear data structure consisting of a finite set of vertices (nodes) and a set of edges that connect pairs of vertices. Graphs can be directed (edges have a direction) or undirected, and weighted (edges carry a cost) or unweighted. They are used to model real-world problems such as social networks, transportation systems, web page link structures, and dependency resolution.
Graph Representation Methods Comparison
| Representation | Space | Add Edge | Check Edge | Best For |
|---|---|---|---|---|
| Adjacency Matrix | O(V²) | O(1) | O(1) | Dense graphs |
| Adjacency List | O(V + E) | O(1) | O(degree) | Sparse graphs |
| Edge List | O(E) | O(1) | O(E) | Edge-centric algorithms |
| Incidence Matrix | O(V × E) | O(1) | O(E) | Hypergraphs |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Disjoint Set
A disjoint set (also called union-find or merge-find set) is a data structure that keeps track of a collection of non-overlapping sets and supports two primary operations: Union (merging two sets) and Find (determining which set an element belongs to by returning a representative). With path compression and union by rank optimizations, operations run in nearly O(1) amortized time per operation (Inverse Ackermann function). Disjoint sets are foundational in Kruskal's minimum spanning tree algorithm, network connectivity checking, and image segmentation.
Binary Tree
A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. It is one of the most fundamental structures in computer science, forming the basis for more specialized trees like binary search trees and heaps. Binary trees are widely used in expression parsing, Huffman coding, and database indexing.
Trie (data structure)
A trie (also called a prefix tree or digital tree) is a tree-like data structure used to store strings where each node represents a single character of a key, and paths from root to leaf spell out complete keys. The root represents an empty string, and each edge corresponds to a character. Tries are highly efficient for prefix-based search operations, making them ideal for autocomplete systems, spell checkers, and IP routing tables.
The mathematical study of graphs was initiated by Leonhard Euler in 1736 with his solution to the Königsberg bridge problem. The word "graph" derives from the Greek "graphein," meaning "to write or draw," referring to the visual representation of vertices and edges.