What Is a Graph?

A graph is a collection of items connected by relationships. Simple as that.

• The items are called nodes (or vertices). Think of them as dots.
• The connections between items are called edges. Think of them as lines between the dots.

Graphs are everywhere. A map of cities connected by roads is a graph. A social network where people are connected by friendships is a graph. Any time you have "things" and "relationships between things," you have a graph.

Directed vs Undirected

An undirected graph has edges with no direction. If Alice is friends with Bob, Bob is also friends with Alice. The connection goes both ways.

A directed graph has edges with a direction. Think of Twitter follows. If Alice follows Bob, that does NOT mean Bob follows Alice.

Weighted vs Unweighted

In an unweighted graph, all edges are equal — a connection just means "these two are connected."

In a weighted graph, each edge has a number on it. This number might represent distance, cost, or travel time. A road map with distances is a weighted graph.

Cycles

A cycle is a path that loops back to where it started. If you can start at city A, travel through some cities, and end up back at city A — that is a cycle.

A graph with no cycles is called acyclic.

Connected Components

A connected component is a group of nodes that can all reach each other. If your graph has some nodes completely cut off from others, those separate groups are different connected components.

Undirected Graph Example

    A --- B
    |     |
    D --- C

Nodes: A, B, C, D

Edges: A-B, A-D, B-C, D-C

This graph is connected (all nodes can reach each other) and has a cycle (A → B → C → D → A).

Directed Graph Example

    A ---> B
    |      |
    v      v
    D      C

Nodes: A, B, C, D

Edges: A→B, A→D, B→C

This graph has no cycles — you can never get back to where you started by following the arrows.

Weighted Graph Example

    A ---5--- B
    |         |
    3         2
    |         |
    D ---4--- C

The numbers on edges are weights. The shortest path from A to C is A→B→C with a total cost of 7.

Disconnected Graph Example

    A --- B      D --- E
          |      |
          C      F

Two separate connected components: {A, B, C} and {D, E, F}. There is no path from A to D.

Real-World Graph Examples

Social network (Undirected): Each user is a node. Each friendship is an undirected edge. If you are friends with someone, they are friends with you.

Twitter follows (Directed): Each user is a node. Each follow is a directed edge. You can follow someone without them following you back.

GPS map (Weighted): Cities are nodes. Roads are edges. The distance between cities is the weight. Your GPS finds the shortest path through this weighted graph.

Task dependencies (Directed, no cycles): Task C depends on Task A and Task B. You cannot start C until A and B are done. Edges point from each task to the tasks that depend on it. This must have no cycles — circular dependencies would mean nothing could ever start.

  compile ---> test ---> deploy