Graphs Explained

A graph is a collection of vertices (nodes) connected by edges (links). Unlike a tree, a graph has no root and no hierarchy: any vertex can connect to any other, connections can form cycles, and there may be several paths between two vertices. Graphs model networks of every kind — roads between cities, friendships on a social platform, web pages and their links.

Core terminology

• Vertex — a single node in the graph.
• Edge — a connection between two vertices.
• Directed — edges have a direction (a one-way street); an edge from A to B does not imply B to A.
• Undirected — edges go both ways (a two-way road).
• Weighted — each edge carries a number, such as distance or cost.
• Path — a sequence of edges connecting one vertex to another.
• Cycle — a path that returns to where it started.

A social network is usually undirected (friendship is mutual); a follower network is directed (you can follow someone who does not follow you back).

How to store a graph

The two standard representations are:

• Adjacency list — each vertex keeps a list of the vertices it connects to. Compact for sparse graphs (few edges), and the common default.
• Adjacency matrix — a grid where cell [i][j] marks whether an edge exists between vertices i and j. Simple, but uses O(V2) space, which is wasteful when most pairs are unconnected.

For most real graphs, which are sparse, the adjacency list wins on memory.

Breadth-first search

Exploring a graph means visiting its vertices systematically. Breadth-first search (BFS) explores level by level using a queue: visit a vertex, enqueue all its unvisited neighbours, then move on. It naturally finds the shortest path (in number of edges) from the start in an unweighted graph.

import java.util.*;

class Graph {
    // adjacency list: index = vertex, value = list of neighbours
    private List<List<Integer>> adj;

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

    // Add an undirected edge between u and v.
    void addEdge(int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }

    // Breadth-first search from a start vertex.
    // Visits every reachable vertex once -> O(V + E).
    void bfs(int start) {
        boolean[] visited = new boolean[adj.size()];
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;     // mark before enqueueing
        queue.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll(); // take the next vertex in FIFO order
            System.out.print(node + " ");
            for (int neighbour : adj.get(node)) {
                if (!visited[neighbour]) {   // skip already-seen vertices
                    visited[neighbour] = true;
                    queue.add(neighbour);
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph(6);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);
        g.addEdge(3, 5);
        g.bfs(0); // a valid BFS order, e.g.: 0 1 2 3 4 5
    }
}

BFS visits each vertex and each edge once, so it runs in O(V + E) time, where V is the number of vertices and E the number of edges. The visited array is what stops cycles from trapping the search in an infinite loop — a concern that trees never have.

Graphs versus trees

Every tree is a graph, but not every graph is a tree. A tree is a connected, acyclic graph with n - 1 edges. Graphs lift those restrictions: they may be disconnected, contain cycles, and have any number of edges. That freedom is what lets them model messy real-world networks.

Common mistakes

• Forgetting the visited set. Without tracking visited vertices, a cycle sends your traversal into an infinite loop. Always mark vertices as you reach them.
• Marking too late. Mark a vertex as visited when you enqueue it, not when you dequeue it, or you may add the same vertex multiple times.
• Wrong representation choice. Using an adjacency matrix for a large sparse graph wastes O(V2) memory. Default to adjacency lists unless the graph is dense.
• Ignoring direction. In a directed graph, adding edge A to B does not add B to A. Mixing this up corrupts your traversal.
• Assuming connectivity. A graph may be split into separate components. A single BFS from one vertex only reaches its own component.

FAQ

BFS or DFS? BFS explores level by level (using a queue) and finds shortest paths in unweighted graphs. Depth-first search dives deep along one path first (using a stack or recursion). Pick based on what you need to find.

How is a graph different from a tree? A tree is a connected graph with no cycles and a single path between any two nodes. Graphs allow cycles, multiple paths, and disconnection.

Keep learning

Build the foundation with Trees Explained, see how the queue powers BFS, and browse the full DSA hub.

Want to implement graph algorithms with instructor feedback in Jalgaon? Join the waitlist for our Data Structures & Algorithms course.