Graph Data Structures in DAA: Vertices, Edges and Representations

What is a Graph?

Graph data structures model relationships with vertices and edges. This lesson focuses on how directed, undirected, weighted, and unweighted graphs represent connected data in algorithm problems.

Compare adjacency matrices and adjacency lists by memory cost, edge lookup, neighbor traversal, and the density of the graph instead of choosing a representation by habit.

A strong graph foundation should include graph terminology, representation tradeoffs, one realistic use case, one edge case, and a small graph that you can trace by hand.

Study graphs as relationship models used by traversal and optimization algorithms. Name the vertices, define what each edge means, and choose a representation that supports the operations the problem performs most often.

A graph is a non-linear data structure used to represent relationships between objects. A graph is written as G = (V, E), where V is the set of vertices (or nodes) and E is the set of edges connecting those vertices.

Graphs are used whenever we need to model connections: roads between cities, friendships in social networks, links between web pages, dependencies among tasks, and communication in computer networks.

Why Graphs Matter

Maps and GPS: cities are vertices and roads are edges.
Social networks: people are vertices and friendships or follows are edges.
Computer networks: routers are vertices and communication links are edges.
Task scheduling: tasks are vertices and dependencies are directed edges.
Recommendation systems: users, items, and interactions can be modeled as graphs.

Basic Graph Notation

Notation	Meaning
G = (V, E)	Graph G with vertices V and edges E
\|V\|	Number of vertices
\|E\|	Number of edges
(u, v)	Edge between vertices u and v
w(u, v)	Weight or cost of edge (u, v)

Types of Graphs

Type	Description	Example
Undirected graph	Edges have no direction, so (u, v) and (v, u) mean the same	Facebook friendships
Directed graph (digraph)	Edges have direction, so u -> v is different from v -> u	Twitter follows, web links
Weighted graph	Edges carry a cost, distance, or score	Road distances, network latency
Unweighted graph	All edges are considered equal	Simple social connections
Cyclic graph	Contains at least one cycle	Road network
Acyclic graph	Contains no cycles	Hierarchical dependencies
DAG	Directed acyclic graph	Task scheduling, Git commit graph
Connected graph	Every vertex is reachable from every other vertex	All cities linked by roads
Disconnected graph	Graph has more than one isolated component	Separate clusters in a network

Sparse vs Dense Graphs

This distinction matters because many graph algorithms are designed differently depending on whether the graph has only a few edges or almost every possible edge.

Graph Type	Meaning	Typical Representation
Sparse graph	Number of edges is much smaller than the maximum possible	Adjacency list
Dense graph	Number of edges is close to the maximum possible	Adjacency matrix

Graph Representations

A graph can be stored in memory in multiple ways. The most common choices are adjacency matrix, adjacency list, and edge list.

Representation	Space	Add Edge	Check Edge	Best For
Adjacency matrix	O(V^2)	O(1)	O(1)	Dense graphs
Adjacency list	O(V + E)	O(1)	O(degree)	Sparse graphs
Edge list	O(E)	O(1)	O(E)	Algorithms like Kruskal's MST

Adjacency List vs Adjacency Matrix

Feature	Adjacency List	Adjacency Matrix
Memory usage	Low for sparse graphs	High because all V^2 entries are stored
Neighbor traversal	Efficient	Need to scan a full row
Edge lookup	Slower	Immediate O(1) lookup
Typical use	BFS, DFS, shortest path on sparse graphs	Dense graphs, Floyd-Warshall, direct edge tests

Graph Representations - Adjacency List and Matrix

import java.util.*;

public class Graph {

    // Adjacency List representation - O(V + E) space
    static class GraphList {
        int V;
        List<List<Integer>> adj;

        GraphList(int v) {
            V = v;
            adj = new ArrayList<>();
            for (int i = 0; i < v; i++) adj.add(new ArrayList<>());
        }

        void addEdge(int u, int v) {
            adj.get(u).add(v);
            adj.get(v).add(u);  // undirected graph
        }

        void printGraph() {
            for (int i = 0; i < V; i++) {
                System.out.println(i + " -> " + adj.get(i));
            }
        }
    }

    // Adjacency Matrix representation - O(V^2) space
    static class GraphMatrix {
        int V;
        int[][] matrix;

        GraphMatrix(int v) {
            V = v;
            matrix = new int[v][v];
        }

        void addEdge(int u, int v) {
            matrix[u][v] = 1;
            matrix[v][u] = 1;  // undirected graph
        }

        void printMatrix() {
            System.out.print("  ");
            for (int i = 0; i < V; i++) System.out.print(i + " ");
            System.out.println();

            for (int i = 0; i < V; i++) {
                System.out.print(i + " ");
                for (int j = 0; j < V; j++) {
                    System.out.print(matrix[i][j] + " ");
                }
                System.out.println();
            }
        }
    }

    public static void main(String[] args) {
        // Graph: 0-1, 0-2, 1-2, 1-3, 2-4
        GraphList gl = new GraphList(5);
        gl.addEdge(0, 1); gl.addEdge(0, 2);
        gl.addEdge(1, 2); gl.addEdge(1, 3); gl.addEdge(2, 4);
        System.out.println("Adjacency List:");
        gl.printGraph();

        GraphMatrix gm = new GraphMatrix(5);
        gm.addEdge(0, 1); gm.addEdge(0, 2);
        gm.addEdge(1, 2); gm.addEdge(1, 3); gm.addEdge(2, 4);
        System.out.println("\nAdjacency Matrix:");
        gm.printMatrix();
    }
}

Graph Terminology

Term	Definition	Example
Vertex (node)	A fundamental unit of a graph	A city in a road map
Edge	A connection between two vertices	A road between two cities
Degree	Number of edges incident to a vertex in an undirected graph	A city with 3 roads has degree 3
In-degree	Number of incoming edges in a directed graph	Number of followers coming into a node
Out-degree	Number of outgoing edges in a directed graph	Number of links leaving a page
Path	A sequence of vertices connected by edges	Route from A to D via B, C
Simple path	A path with no repeated vertices	A -> B -> C -> D
Cycle	A path that starts and ends at the same vertex	A -> B -> C -> A
Connected graph	Every vertex is reachable from every other	All cities connected by roads
Component	A maximal connected part of a graph	One isolated cluster in a network
Weighted graph	Edges have associated cost or weight	Road distances
Tree	Connected acyclic undirected graph	File system hierarchy
Spanning tree	A tree that includes all vertices of a connected graph	Minimum network connecting all cities

Special Graph Structures

Tree: connected and acyclic undirected graph.
Forest: collection of trees.
DAG: directed acyclic graph used in dependency problems.
Complete graph: every pair of vertices has an edge.
Bipartite graph: vertices can be divided into two groups such that no edge joins vertices inside the same group.

Graph Traversal Overview

Two fundamental ways to traverse a graph are BFS and DFS. Most graph algorithms build on one of these two ideas.

Feature	BFS (Breadth-First)	DFS (Depth-First)
Main data structure	Queue (FIFO)	Stack / recursion
Traversal style	Level by level	Deep first, then backtrack
Shortest path in unweighted graph	Yes	No
Common uses	Distance, levels, bipartite check	Cycle detection, topological sort, backtracking
Time complexity	O(V + E)	O(V + E)
Space complexity	O(V)	O(V)

Choosing the Right Representation

Use adjacency list when the graph is sparse and you need to iterate neighbors often.
Use adjacency matrix when the graph is dense or you need fast edge existence checks.
Use edge list when algorithms process edges directly, such as Kruskal's MST or Bellman-Ford.

Graph Introduction Failure Cases

Confusing directed and undirected edges.
Using adjacency matrix for very sparse graphs and wasting memory.
Forgetting that weighted and unweighted graphs need different algorithms for shortest path.
Assuming every graph is connected.

Graph Introduction Rules

A graph models relationships among objects using vertices and edges.
Graphs can be directed, undirected, weighted, unweighted, cyclic, or acyclic.
Adjacency list, adjacency matrix, and edge list are the main ways to store graphs.
BFS and DFS are the two basic traversal techniques that support most graph algorithms.

Graph representation comparison trace

1. List the vertices and edges in a small graph.
2. Represent the same graph with an adjacency matrix.
3. Represent it again with an adjacency list.
4. Compare memory use, edge lookup, and neighbor traversal.

Graph edge-case trace

1. Test an isolated vertex with no edges.
2. Test a self-loop and repeated edge input.
3. Decide whether direction and weight change the representation.
4. Verify that every intended neighbor is still reachable.

Before you move on