Graphs

Introduction to Graphs

A graph is a set of nodes (vertices) connected by edges. Used in maps, networks, social media, etc.

Key Properties

• Vertex (Node): A point
• Edge: Connection between nodes O(1)
• Directed Graph: Edges have direction (A → B)
• Undirected Graph: No direction (A — B)
• Weighted Graph: Edges have weights (costs)
• Cycle: A path that starts and ends at same node
• Connected Graph: Path exists between any two nodes
• Adjacency List / Matrix: Ways to represent a graph

Example in C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int V = 4; // number of vertices
    vector <vector<int>> graph(V);

    // Add edges (undirected)
    graph[0].push_back(1);
    graph[1].push_back(0);

    graph[1].push_back(2);
    graph[2].push_back(1);

    graph[2].push_back(3);
    graph[3].push_back(2);

    // Print adjacency list
    for (int i = 0; i < V; i++) {
        cout << "Node " << i << ": ";
        for (int v : graph[i]) {
            cout << v << " ";
        }
        cout << endl;
    }

    return 0;
}

    

Learning resource

Readings Graphs
more resource Graphs