How Graphs Work — Networks, Dependencies, and Connections

A tree has one path between any two nodes. A graph can have many — or none. Graphs represent relationships where structure isn't hierarchical: networks, dependencies, routes, social connections, state machines. The internet itself is a graph.

A graph has nodes (vertices) and edges (connections between nodes). That's the entire definition. Everything else — directed vs undirected, weighted vs unweighted, cyclic vs acyclic — is a property of a specific graph.

What Are the Types of Graphs?

Undirected — edges go both ways. If A connects to B, B connects to A. A road network (most roads are two-way), a social network (friendship is mutual).

Directed — edges have direction. A → B doesn't imply B → A. A dependency graph (A depends on B), a link graph (page A links to page B), a DNS resolution chain.

Weighted — edges have costs. A road network with distances, a network with latency per link, a flight route with ticket prices.

Cyclic — contains at least one cycle (a path from a node back to itself). Most real-world graphs are cyclic.

Acyclic — no cycles. A DAG (Directed Acyclic Graph) is the most useful variant: task dependencies, build systems (Makefile), Git commit history, topological ordering.

How Are Graphs Stored?

Two standard representations:

Adjacency list — each node stores a list of its neighbors. Memory: O(V + E) where V is nodes and E is edges. Fast neighbor lookup. This is the standard representation for sparse graphs (few edges relative to nodes).

A → [B, C]
B → [A, D]
C → [A, D, E]
D → [B, C]
E → [C]

In practice: a hash map from node to array of neighbors. Or an array of arrays if nodes are numbered 0 to V-1.

Adjacency matrix — a V×V matrix where matrix[i][j] = 1 if there's an edge from i to j. Memory: O(V²). Fast edge-existence check (O(1)), but wastes memory on sparse graphs.

Most real-world graphs are sparse — a social network with 1 billion users where each person has 500 friends has 1 billion nodes and 250 billion edges, but the matrix would have 10^18 cells. Adjacency lists win.

How Do You Traverse a Graph?

Two fundamental traversal strategies:

BFS — Breadth-First Search

Explore all neighbors before going deeper. Uses a queue (FIFO).

Starting from node A:

1. Visit A. Enqueue A's neighbors: [B, C].
2. Dequeue B. Visit B. Enqueue B's unvisited neighbors: [D].
3. Dequeue C. Visit C. Enqueue C's unvisited neighbors: [E].
4. Dequeue D. Visit D. No unvisited neighbors.
5. Dequeue E. Visit E. No unvisited neighbors.

Order: A, B, C, D, E — layer by layer, closest first.

Use BFS when: you want the shortest path (in unweighted graphs), level-order traversal, or need to explore nearby nodes first. Web crawlers use BFS to discover pages level by level. DNS resolution traverses the hierarchy level by level.

DFS — Depth-First Search

Explore as deep as possible before backtracking. Uses a stack (LIFO) or recursion.

Starting from node A:

1. Visit A. Push A's neighbors: [B, C].
2. Pop C. Visit C. Push C's unvisited neighbors: [D, E].
3. Pop E. Visit E. No unvisited neighbors.
4. Pop D. Visit D. Push D's unvisited neighbors: [B].
5. Pop B. Visit B. No unvisited neighbors.

Order: A, C, E, D, B — goes deep before going wide.

Use DFS when: you want to detect cycles, find connected components, topological sort, solve mazes, or explore exhaustively. Compiler analysis uses DFS on control flow graphs. Git uses DFS to walk commit history.

Both BFS and DFS are O(V + E) — they visit every node and traverse every edge once.

What Is a Shortest Path?

In an unweighted graph, BFS finds the shortest path (fewest edges). In a weighted graph, you need Dijkstra's algorithm:

1. Start at the source. Distance = 0. All other distances = infinity.
2. Visit the unvisited node with the smallest known distance.
3. For each neighbor, calculate current_distance + edge_weight. If it's less than the neighbor's known distance, update it.
4. Mark the current node as visited. Repeat from step 2.

Dijkstra's is O((V + E) log V) with a priority queue (min-heap). It's the algorithm behind network routing — routers compute shortest paths to determine where to send packets.

What Is a Topological Sort?

In a DAG (no cycles), a topological sort orders nodes so that every edge goes from earlier to later in the order. This is the "safe build order" — compile dependencies before dependents.

A → B → D
A → C → D

Topological order: A, B, C, D (or A, C, B, D). D comes last because it depends on both B and C.

Build systems (Make, Bazel, Cargo), task schedulers, package managers (resolving dependency order), and spreadsheet recalculation all use topological sort. It's O(V + E) using DFS or BFS (Kahn's algorithm).

Where Do Graphs Appear?

The internet — routers and links form a graph. Routing protocols (BGP, OSPF) compute shortest paths to decide where packets go.

Social networks — users are nodes, connections are edges. Friend recommendations = finding nodes 2 edges away. Influence = graph centrality.

Dependency management — npm, pip, cargo — package dependencies form a DAG. Resolving versions is graph traversal. Circular dependencies are cycles in a directed graph.

Git — commits form a DAG. Each commit points to its parents. Merge commits have two parents. git log --graph visualizes this.

HNSW — the vector index used in semantic search is a layered graph. Nearest-neighbor search is graph traversal — greedy search through connected nodes.

Knowledge graphs — entities and relationships. "8Vast is-a product. 8Vast built-by 8Network." The content you're reading is structured as a knowledge graph.

State machines — states are nodes, transitions are directed edges. TCP connection states (LISTEN → SYN_RECEIVED → ESTABLISHED → FIN_WAIT → CLOSED) form a directed graph.

Graphs vs Trees

A tree is a special case of a graph: connected, acyclic, undirected, with exactly one path between any two nodes. Every tree is a graph, but not every graph is a tree.

Property	Tree	Graph
Cycles	No	Can have cycles
Root	Yes (one)	No designated root
Path between nodes	Exactly one	Zero, one, or many
Edges	V-1	Any number
Use case	Hierarchies	Arbitrary relationships

If your data is hierarchical, use a tree. If it has arbitrary connections, use a graph.

Next Steps

This completes the data structures foundation. From here:

• Algorithms — sorting, searching, and graph algorithms that operate on these structures.
• How Indexing Works — how search engines build on hash maps (inverted indexes) and graphs (HNSW).
• How the Kernel Works — how the OS uses these structures to manage hardware.