Step 1 of 6

17% Complete

Introduction to Graphs

Learn the fundamentals of graph data structures

What is a Graph?

A graph is a data structure consisting of a set of vertices (nodes) connected by edges. Graphs are used to represent relationships, networks, and connections between objects. They are one of the most important data structures in computer science.

Unlike trees or lists with linear relationships, graphs can model complex, non-linear relationships including cycles, multiple connections, and bidirectional relationships.

Key Terminology

Vertex (Node)

A point in the graph representing an entity or object

Edge

A connection between two vertices representing a relationship

Degree

The number of edges connected to a vertex

Path

A sequence of vertices where each consecutive pair is connected by an edge

Cycle

A path that starts and ends at the same vertex

Connected Component

A maximal set of vertices where every pair is connected by a path

Types of Graphs

1. Directed vs Undirected

Directed Graph

Edges have direction (A → B)

Example: Twitter follows, roads with one-way streets

Undirected Graph

Edges have no direction (A ↔ B)

Example: Social networks, Road networks

2. Weighted vs Unweighted

Weighted Graph

Edges have weights/costs

Example: GPS distance, Flight costs

Unweighted Graph

All edges have equal weight

Example: Social networks, Game maps

3. Cyclic vs Acyclic

Cyclic Graph

Contains at least one cycle

Example: Most real-world networks

Acyclic Graph (DAG)

No cycles present

Example: Task scheduling, Dependency graphs

4. Dense vs Sparse

Dense Graph

Many edges (≈ V²)

Use adjacency matrix

Sparse Graph

Few edges (≈ V)

Use adjacency list

Graph Representation Comparison

Aspect	Adjacency Matrix	Adjacency List
Space	O(V²)	O(V + E)
Edge Lookup	O(1)	O(degree)
Add Edge	O(1)	O(1)
Get Neighbors	O(V)	O(degree)
Best For	Dense graphs	Sparse graphs

Graph Basics Example

Graph Basic Structure

public class Graph {
    private int V;  // Number of vertices
    private int E;  // Number of edges
    private List<Integer>[] adj;  // Adjacency list
    
    // Constructor
    public Graph(int V) {
        this.V = V;
        this.E = 0;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }
    
    // Add edge (undirected graph)
    public void addEdge(int u, int v) {
        adj[u].add(v);
        adj[v].add(u);  // For undirected, add both directions
        E++;
    }
    
    // Get neighbors of vertex
    public List<Integer> getNeighbors(int v) {
        return adj[v];
    }
    
    // Get vertex count
    public int getVertexCount() {
        return V;
    }
    
    // Get edge count
    public int getEdgeCount() {
        return E;
    }
    
    public static void main(String[] args) {
        Graph g = new Graph(5);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);
        
        System.out.println("Graph has " + g.getVertexCount() + " vertices");
        System.out.println("Graph has " + g.getEdgeCount() + " edges");
        System.out.println("Neighbors of vertex 1: " + g.getNeighbors(1));
    }
}

Graph Properties

Number of Edges

In a simple undirected graph: E ≤ V(V-1)/2

In a simple directed graph: E ≤ V(V-1)

Complete Graph

A graph where every pair of vertices is connected

Edges in complete graph: V(V-1)/2 (undirected)

Handshake Lemma

Sum of all vertex degrees = 2E

Useful for calculating graph properties

Real-World Graph Applications

Social Networks: Facebook, Twitter (vertices=people, edges=connections)

GPS/Maps: Google Maps (vertices=locations, edges=roads)

Recommendations: Netflix, Amazon (vertices=items, edges=similarity)

Web Pages: Google PageRank (vertices=pages, edges=links)

Flight Routes: Airlines (vertices=airports, edges=routes)

Key Takeaways

Graphs model relationships and connections between objects
Vertices are entities; edges are relationships
Different graph types have different properties and use cases
Choice of representation (matrix vs list) depends on graph density
Graphs appear everywhere in real-world applications
Understanding graph structure is key to solving graph problems
Graph algorithms (DFS, BFS, Dijkstra) build on basic graph concepts