Graphs

Imagine a city with several locations connected by roads.

        A
       / \
      B   C
      |   |
      D---E

Here:

• A, B, C, D, E are locations

• The connections between them are roads

This is exactly the kind of relationship that a Graph represents.

A graph is a non-linear data structure made up of vertices (nodes) and edges (connections between nodes).

Graphs are one of the most important topics in DSA because they can represent relationships between almost anything.

What is a Graph?

A graph consists of two fundamental components:

Vertices + Edges

Vertex

A vertex, also called a node, represents an entity.

For example:

A
B
C
D

Each one can represent:

• A city

• A person

• A computer

• A webpage

• A social media account

• A course

• A device

Edge

An edge represents a relationship or connection between two vertices.

For example:

A ─── B

The line between A and B is an edge.

So:

Graph
├── Vertices → Things
└── Edges    → Connections

A Simple Graph

Consider:

      A
     / \
    B   C
    |   |
    D---E

The vertices are:

A, B, C, D, E

Some of the edges are:

A-B
A-C
B-D
C-E
D-E

We can represent the graph as:

V = {A, B, C, D, E}

E = {
    (A,B),
    (A,C),
    (B,D),
    (C,E),
    (D,E)
}

Here:

V → Set of vertices
E → Set of edges

Graph Terminology

Before working with graphs, you need to understand some common terms.

Vertex

A node in the graph.

A

Edge

A connection between two vertices.

A ─ B

Adjacent Vertices

Two vertices are adjacent if they are directly connected by an edge.

For:

A ─ B ─ C

A and B are adjacent.

B and C are adjacent.

But A and C are not directly adjacent.

Degree

The degree of a vertex is the number of edges connected to it in an undirected graph.

For:

    A
   /|\
  B C D

the degree of A is:

3

because three edges connect to A.

Directed Graph

In some graphs, connections have a direction.

For example:

A → B

This means we can travel from A to B.

But that doesn't necessarily mean we can travel from B to A.

This is called a Directed Graph, or Digraph.

For example:

A → B → C

The edges have direction.

This is useful for relationships such as:

Instagram user → follows → another user
Webpage A → links to → Webpage B
Course A → prerequisite → Course B

Undirected Graph

In an Undirected Graph, edges don't have a direction.

For example:

A ─ B

This means the relationship works both ways.

If A is connected to B, then B is also connected to A.

A road between two cities is a common example:

Kolkata ─ Durgapur

You can generally travel in either direction.

Directed vs Undirected Graph

The difference is:

Undirected:

A ─ B

A ↔ B

Directed:

A → B

So:

Weighted Graph

Sometimes edges have a value associated with them.

For example, roads may have distances:

       5
   A ───── B
   |       |
  10       3
   |       |
   C ───── D
       7

The numbers represent the weight of each edge.

For example:

A → B = 5
A → C = 10
B → D = 3
C → D = 7

This is a Weighted Graph.

Weights can represent:

• Distance

• Cost

• Time

• Network latency

• Fuel consumption

• Risk

Unweighted Graph

If edges don't have weights:

A ─ B
|   |
C ─ D

we have an Unweighted Graph.

Every connection is simply treated as an edge.

This distinction becomes important when solving shortest-path problems.

Connected Graph

A graph is connected if every vertex can be reached from every other vertex through some path.

For example:

A ─ B
|   |
C ─ D

Every node can reach every other node.

So this is connected.

Disconnected Graph

Consider:

A ─ B       C ─ D

There is no connection between the two groups.

Therefore, the graph is disconnected.

The separate groups are called connected components.

Component 1 → A, B
Component 2 → C, D

Cycle

A cycle exists when we can start at a vertex, follow edges, and eventually return to the same vertex.

For example:

A
| \
|  \
B---C

We can travel:

A → B → C → A

So this graph contains a cycle.

A graph with no cycles is called acyclic.

Graph vs Tree

A tree is actually a special type of graph.

For example:

       A
      / \
     B   C
    /
   D

A tree:

• Is connected

• Has no cycles

• Has exactly n - 1 edges for n vertices

A general graph doesn't necessarily satisfy these rules.

For example:

A ─ B
| \ |
|  \|
C ─ D

can contain cycles and may have more edges.

So:

Graph
  ↓
More general structure

Tree
  ↓
Special type of graph

Graph Representation

There are several ways to represent a graph in a program.

The most important ones are:

1. Adjacency Matrix
2. Adjacency List
3. Edge List

For DSA problems, adjacency lists are extremely common.

Adjacency Matrix

Consider this graph:

A ─ B
|   |
C ─ D

We can create a matrix where:

matrix[i][j] = 1

means there is an edge between i and j.

For example:

     A B C D
A    0 1 1 0
B    1 0 0 1
C    1 0 0 1
D    0 1 1 0

For an undirected graph, the matrix is symmetric.

For example:

A → B

means:

matrix[A][B] = 1

and in an undirected graph:

matrix[B][A] = 1

Java Adjacency Matrix

We can represent the graph using a 2D array:

int[][] graph = new int[4][4];

Suppose:

0 → A
1 → B
2 → C
3 → D

We can add an undirected edge between A and B:

graph[0][1] = 1;
graph[1][0] = 1;

Another edge between A and C:

graph[0][2] = 1;
graph[2][0] = 1;

Adjacency List

An adjacency list stores the neighbors of each vertex.

For:

A ─ B
|   |
C ─ D

we can write:

A → B, C
B → A, D
C → A, D
D → B, C

This is generally more space-efficient for sparse graphs, where relatively few possible edges actually exist.

Java Adjacency List

A common Java representation is:

import java.util.ArrayList;

ArrayList<ArrayList<Integer>> graph =
    new ArrayList<>();

We first create the lists:

int vertices = 5;

for (int i = 0; i < vertices; i++) {
    graph.add(new ArrayList<>());
}

Then add an undirected edge:

graph.get(0).add(1);
graph.get(1).add(0);

This represents:

0 ─ 1

We need both entries because the graph is undirected.

Edge List

Another simple representation is an edge list.

For example:

A ─ B
B ─ C
A ─ C

can be represented as:

(A, B)
(B, C)
(A, C)

For weighted edges:

(A, B, 5)
(B, C, 10)
(A, C, 7)

Edge lists are particularly useful in algorithms such as Kruskal's algorithm, where we process edges directly.

Adjacency Matrix vs Adjacency List

Here:

V = Number of vertices
E = Number of edges

For most graph traversal problems, an adjacency list is usually the natural choice.

Adding Edges

Let's build this graph:

0 ─ 1
|   |
2 ─ 3

Using an adjacency list:

import java.util.ArrayList;

class Main {

    static void addEdge(
        ArrayList<ArrayList<Integer>> graph,
        int u,
        int v
    ) {

        graph.get(u).add(v);
        graph.get(v).add(u);
    }

    public static void main(String[] args) {

        int vertices = 4;

        ArrayList<ArrayList<Integer>> graph =
            new ArrayList<>();

        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        addEdge(graph, 0, 1);
        addEdge(graph, 0, 2);
        addEdge(graph, 1, 3);
        addEdge(graph, 2, 3);
    }
}

Because this is an undirected graph, each edge is stored in both directions.

Graph Traversal

Just like trees, graphs need traversal algorithms.

The two most important graph traversal techniques are:

DFS → Depth-First Search
BFS → Breadth-First Search

You've already seen these ideas with trees.

The major difference is that graphs can contain cycles.

For example:

A ─ B
|   |
C ─ D

If we start at A and keep following edges without keeping track of visited nodes, we could repeatedly travel around the cycle.

That's why graph traversal usually needs a:

visited[]

array or set.

DFS — Depth-First Search

DFS explores as deeply as possible before backtracking.

For:

0 ─ 1
|   |
2 ─ 3

one possible DFS traversal from 0 is:

0 → 1 → 3 → 2

The exact order can depend on how neighbors are stored.

DFS commonly uses:

Recursion

or:

Stack

DFS in Java

static void dfs(
    int node,
    ArrayList<ArrayList<Integer>> graph,
    boolean[] visited
) {

    visited[node] = true;

    System.out.print(node + " ");

    for (int neighbor : graph.get(node)) {

        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

We can call it:

boolean[] visited =
    new boolean[vertices];

dfs(0, graph, visited);

The key line is:

visited[node] = true;

This prevents us from repeatedly visiting the same node.

BFS — Breadth-First Search

BFS explores the graph level by level.

It uses a:

Queue

Suppose:

      0
     / \
    1   2
   / \
  3   4

Starting at 0:

Level 0 → 0
Level 1 → 1, 2
Level 2 → 3, 4

So BFS gives:

0 → 1 → 2 → 3 → 4

BFS in Java

import java.util.LinkedList;
import java.util.Queue;

static void bfs(
    int start,
    ArrayList<ArrayList<Integer>> graph
) {

    boolean[] visited =
        new boolean[graph.size()];

    Queue<Integer> queue =
        new LinkedList<>();

    queue.add(start);
    visited[start] = true;

    while (!queue.isEmpty()) {

        int node = queue.remove();

        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {

            if (!visited[neighbor]) {

                visited[neighbor] = true;

                queue.add(neighbor);
            }
        }
    }
}

The basic pattern is:

Start
 ↓
Mark visited
 ↓
Add to queue
 ↓
Remove from queue
 ↓
Visit neighbors
 ↓
Repeat

DFS vs BFS

This is one of the most important comparisons in graph DSA.

For example:

DFS:
0 → 1 → 3 → 2

BFS:
0 → 1 → 2 → 3

The exact DFS order can vary based on neighbor ordering.

Shortest Path in an Unweighted Graph

BFS has an important property.

If all edges have equal cost, BFS can find the shortest path in terms of the number of edges.

Consider:

        1
       / \
      2   3
      |   |
      4---5

If we start from 1 and want to reach 5, BFS explores nodes by distance:

Distance 0 → 1
Distance 1 → 2, 3
Distance 2 → 4, 5

Therefore, the shortest number of edges from 1 to 5 is:

2

through:

1 → 3 → 5

For weighted graphs, however, ordinary BFS is not generally enough. Algorithms such as Dijkstra's algorithm are used when edge weights satisfy the algorithm's requirements.

Connected Components

Consider:

0 ─ 1       3 ─ 4
|           /
2          5

There are two separate groups.

We can use DFS or BFS to find them.

Start from 0:

0 → 1 → 2

That's one component.

Then find an unvisited vertex, 3:

3 → 4 → 5

That's the second component.

So the graph has:

2 connected components

This is a very common graph problem.

Cycle Detection

Graphs can contain cycles:

A ─ B
|   |
C ─ D

We can travel:

A → B → D → C → A

So a cycle exists.

Detecting cycles is a common DSA problem.

The exact technique depends on whether the graph is:

Directed

or:

Undirected

and whether we use DFS, BFS, or another method.

Directed Graphs and Indegree

For directed graphs, another important concept is indegree.

Consider:

A → B
C → B
B → D

The number of edges coming into a vertex is its indegree.

For B:

A → B
C → B

So:

indegree(B) = 2

The number of edges going out is called the outdegree.

For B:

B → D

So:

outdegree(B) = 1

Indegree becomes particularly important in Topological Sorting.

Topological Sorting

Suppose we have tasks with dependencies:

Learn Java
    ↓
Learn DSA
    ↓
Learn Algorithms
    ↓
Solve Problems

You cannot solve certain tasks before completing their prerequisites.

This type of relationship can be represented using a Directed Acyclic Graph, or DAG.

A topological ordering might be:

Learn Java
→ Learn DSA
→ Learn Algorithms
→ Solve Problems

Topological sorting is used in:

• Course prerequisites

• Build systems

• Task scheduling

• Package dependencies

• Project planning

Weighted Graphs

Suppose cities are connected by roads:

        5
   A -------- B
   |          |
  10          3
   |          |
   C -------- D
        7

The weights represent distances.

If we want the shortest path from A to D, we need to consider the weights.

Possible paths:

A → B → D
5 + 3 = 8

and:

A → C → D
10 + 7 = 17

So the shortest path is:

A → B → D

with total cost:

8

This leads to important shortest-path algorithms.

Important Graph Algorithms

Once you understand basic graphs, several major algorithms become important.

BFS

Used for:

• Graph traversal

• Shortest path in unweighted graphs

• Level-based problems

DFS

Used for:

• Traversal

• Connected components

• Cycle detection

• Backtracking

• Topological sorting

Dijkstra's Algorithm

Used for:

Shortest paths in graphs with non-negative edge weights.

Bellman-Ford

Used for:

Shortest paths when negative edge weights may exist.

It can also detect reachable negative-weight cycles.

Floyd-Warshall

Used for:

Shortest paths between all pairs of vertices.

Prim's Algorithm

Used for:

Minimum Spanning Tree.

Kruskal's Algorithm

Also used for:

Minimum Spanning Tree.

Topological Sort

Used for:

Ordering vertices in a Directed Acyclic Graph according to dependencies.

Minimum Spanning Tree

Suppose several cities need to be connected with roads while keeping the total construction cost as low as possible.

A graph can represent:

Cities → Vertices
Roads  → Edges
Costs  → Weights

We want to select edges that:

• Connect all vertices

• Don't create cycles

• Have minimum total weight

This is called a Minimum Spanning Tree (MST).

Two famous algorithms are:

Prim's Algorithm
Kruskal's Algorithm

Real-Life Applications of Graphs

Graphs are everywhere.

Social Networks

People → Vertices
Friendships → Edges

For example:

Alice ─ Bob
  |
Charlie

Maps

Cities → Vertices
Roads → Edges
Distance → Weight

Internet

Routers → Vertices
Connections → Edges

Flight Networks

Airports → Vertices
Flights → Directed Edges
Flight Cost → Weight

Recommendation Systems

Users → Vertices
Interactions → Edges

Web Pages

Webpages → Vertices
Links → Directed Edges

Course Prerequisites

Courses → Vertices
Prerequisites → Directed Edges

A Complete Graph Example in Java

Let's create an undirected graph using an adjacency list and perform DFS and BFS.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Main {

    static void addEdge(
        ArrayList<ArrayList<Integer>> graph,
        int u,
        int v
    ) {

        graph.get(u).add(v);
        graph.get(v).add(u);
    }

    static void dfs(
        int node,
        ArrayList<ArrayList<Integer>> graph,
        boolean[] visited
    ) {

        visited[node] = true;

        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {

            if (!visited[neighbor]) {
                dfs(neighbor, graph, visited);
            }
        }
    }

    static void bfs(
        int start,
        ArrayList<ArrayList<Integer>> graph
    ) {

        boolean[] visited =
            new boolean[graph.size()];

        Queue<Integer> queue =
            new LinkedList<>();

        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {

            int node = queue.remove();

            System.out.print(node + " ");

            for (int neighbor : graph.get(node)) {

                if (!visited[neighbor]) {

                    visited[neighbor] = true;

                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {

        int vertices = 5;

        ArrayList<ArrayList<Integer>> graph =
            new ArrayList<>();

        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        addEdge(graph, 0, 1);
        addEdge(graph, 0, 2);
        addEdge(graph, 1, 3);
        addEdge(graph, 2, 4);

        System.out.print("DFS: ");

        boolean[] visited =
            new boolean[vertices];

        dfs(0, graph, visited);

        System.out.print("\nBFS: ");

        bfs(0, graph);
    }
}

One possible output is:

DFS: 0 1 3 2 4
BFS: 0 1 2 3 4

The exact DFS order depends on the order in which neighbors are stored.

Graph Complexity

If we use an adjacency list, storing a graph takes:

O(V + E)

space.

Why?

We store:

V → Vertices
E → Edges

For an adjacency matrix:

O(V²)

space is required.

For BFS or DFS using an adjacency list:

Time → O(V + E)

because we may visit every vertex and inspect every edge.

This is one of the most important graph complexity formulas to remember:

BFS/DFS with an adjacency list: O(V + E)

The Main Idea

A Graph represents relationships between objects using:

Vertices + Edges

For example:

       A
      / \
     B   C
     |   |
     D---E

The most important graph concepts are:

Vertex
Edge
Directed Graph
Undirected Graph
Weighted Graph
Unweighted Graph
Degree
Cycle
Connected Components

The three common ways to represent a graph are:

Adjacency Matrix
Adjacency List
Edge List

And the two fundamental traversal algorithms are:

DFS → Depth-First Search
BFS → Breadth-First Search

Remember this relationship:

DFS
 ↓
Recursion / Stack

BFS
 ↓
Queue

And the most important graph algorithms you'll encounter later include:

BFS
DFS
Dijkstra
Bellman-Ford
Floyd-Warshall
Prim
Kruskal
Topological Sort

Graphs are one of the most powerful DSA structures because they can model almost any system where objects have relationships or connections.

Once you understand vertices, edges, graph representations, BFS, and DFS, you have the foundation for solving much more advanced problems involving shortest paths, minimum spanning trees, cycles, dependencies, and network connectivity.