Introduction to Graphs
Graphs are versatile data structures consisting of vertices (nodes) connected by edges. They model relationships and connections in networks, social media, maps, and many algorithms.
What is a Graph?
A graph is a collection of vertices (nodes) connected by edges that represent relationships. Unlike trees, graphs can contain cycles and have multiple paths between vertices.
ā¢ Flexible: Can model any relationship structureā¢ Versatile: Directed or undirected connectionsā¢ Powerful: Cycles and multiple paths allowed
Basic Terms
Vertex: Node in the graph
Edge: Connection between vertices
Degree: Number of edges at vertex
Path: Sequence of connected vertices
Key Formulas
Max edges = V(V-1)/2Sum of degrees = 2 Ć edgesComplete graph = V(V-1)/2Relationships
Adjacent: Vertices connected by edge
Incident: Edge connected to vertex
Cycle: Path that starts and ends at same vertex
Connected: Path exists between all vertices
Graph Structure & Terminology
Types of Graphs
Undirected Graph
Edges have no direction - connections are bidirectional
Graph Algorithms
DFS
Stack-based traversal
Explores as far as possible before backtracking. Used for cycle detection, topological sort, and connected components.
BFS
Queue-based traversal
Explores all neighbors level by level. Finds shortest unweighted paths and minimum spanning trees.
Dijkstra's
Priority queue
Finds shortest weighted paths from source to all vertices. Requires non-negative edge weights.
Topological
DAG ordering
Linear ordering of vertices in directed acyclic graphs. Essential for task scheduling and dependency resolution.
Union Find
Disjoint sets
Efficiently tracks connected components and detects cycles. Key component in Kruskal's MST algorithm.
Kruskal's
MST algorithm
Finds minimum spanning tree by sorting edges and using Union Find to avoid cycles in the result.
Prim's
MST algorithm
Grows a minimum spanning tree from a starting vertex by adding the cheapest edge to a new vertex.
Bellman-Ford
Shortest path
Finds shortest paths from a single source, even with negative edge weights. Can detect negative cycles.
Floyd-Warshall
All-pairs shortest path
Calculates the shortest paths between all pairs of vertices in a weighted graph. Handles negative weights.
Graph Representations
Adjacency Matrix
2D array representation
Space: O(VĀ²), Edge lookup: O(1)
A
B
C
A
0
1
0
B
1
0
1
C
0
1
0
Adjacency List
Array of lists
Space: O(V+E), Neighbors: O(degree)
A:
B
B:
A
C
C:
B
Edge List
List of edges
Space: O(E), Simple storage
Edge 1:
A
āB
Edge 2:
B
āC