Graph
Learning Roadmap
Solid arrows are prerequisites - master the source before the target. Dashed nodes are the stretch tier, worth visiting once the core is solid.
What is a graph
Graph is a non-linear data structure that consists of vertices and edges. A vertex is called a node, a point or object in the Graph and an edge is used to connect two vertices with each other. The reason why graoh is called non-linear data structre is because it allows us to have different paths to get from one vertex to another.
Graph Properties
-
A weighted graph is a graph where the edges have values where this weight represents things such as distance, capacity or time.
-
A connected graph is when all the vertices are connected through edges. A graph that is not connected which has either isolated subgraphs or single vertices.
-
A directed graph is when the edges between vertex pair have a direction where this direction represents either hierarchy or flow.
-
An undirected graph is when the edges between vertex pair have no direction - you can traverse them in either direction.
-
A cycle is a path in a graph where you start and end at the same vertex, visiting at least one other vertex along the way. The defination chanages with slightly with dircted and undirected graphs.
- In an undirected graph, any path of 3+ vertices that returns to the start vertex forms a cycle.
- Must follow edges direction to form a valid cycle.
-
Play around with the below interactive visual to have a good understanding of all the graph properties.
Graph Representations
Three ways to store a graph, three household objects: an adjacency list is a phone contact list - every vertex keeps its own short list of direct neighbors. An adjacency matrix is a giant checkerboard - cell (i, j) says whether i connects to j. An edge list is a pile of receipts - just the raw connections, one per line.
"List for neighbors, Matrix for lookups, Edges for algorithms that eat edges." Need "who is next to X?" - adjacency list. Need "are i and j connected?" in O(1) - matrix. Running an algorithm that consumes edges one by one (like Kruskal's) - edge list.
Learners often reach for the matrix "because it's simpler" - but it costs O(V²) space no matter how few edges exist. A sparse graph with 10,000 vertices and 20,000 roads burns ~100 million cells to store 20 thousand facts. Default to the adjacency list (O(V + E)); pick the matrix only when the graph is small or dense and you truly need O(1) edge checks.
Adjacency Matrix Graph Representation
Adjacency Matrix is a 2D array where each cell on index (i, j) stores information about the edge from vertex i to j. You can either store the value '1' indicating that a edge ecists or the weight value indicating the cost to go to from vertex i to j. For an undirected graph, the values in the adjaceny matrix is symmetrical as the edges can both ways where as in a directed graph, we must decide which vertices the edges go from and to and then insert the value at the correct (i, j). This approach is better when the graph size is small and memory is not a constraint.
"Every pair gets a square." Constant-time "is i connected to j?", but O(V²) space whether or not the edges exist - so reach for it only when the graph is dense or you need those O(1) edge checks repeatedly.
Adjacency List Graph Representation
Adjacency List is an array that contains all the vertices in the graph and each vertex linked to a Linked List with the vertex's edges. For a weighted graph, each vertex pointer has a pointer to a Linked List with edges stores as i, w where i is the index of the vertex the edge goes to and w is the weight of that edge.
"Everyone keeps their own contacts." Each vertex holds its own short list of neighbors, so "who is next to X?" is a direct lookup and space is only O(V + E). This is the default representation for almost every graph problem, because real graphs are sparse.
Edge List Graph Representation
Edge List is the rawest form - just the collection of connections, one entry per edge, such as [(0, 1), (1, 2), (0, 4)] (add a third value per tuple for weights). It is the most compact way to store a graph, but answering "who is next to X?" means scanning the whole list, so it is rarely used for traversal. It shines when an algorithm consumes the edges one at a time - most notably Kruskal's minimum-spanning-tree algorithm, which sorts the edge list and walks it in order.
"A receipt per edge." Compact and perfect for edge-hungry algorithms (sort-then-scan like Kruskal's), but a poor fit for neighbor lookups - you would have to dig through the whole pile.