owlingcode

Graph Terminology

A graph G = (V, E) consists of a set of vertices (nodes) V and a set of edges E that connect pairs of vertices.

Types of Graphs

Directed vs Undirected

In a directed graph, edges have direction. In an undirected graph, edges are bidirectional.

// Directed graph example
// Edge from A to B doesn't imply edge from B to A
vector<vector<int>> directed_graph(n);
directed_graph[a].push_back(b); // Only a -> b

// Undirected graph example  
// Edge between A and B implies both directions
vector<vector<int>> undirected_graph(n);
undirected_graph[a].push_back(b);
undirected_graph[b].push_back(a); // Both a -> b and b -> a

Weighted vs Unweighted

Weighted graphs have values (weights) associated with edges, while unweighted graphs treat all edges equally.

// Unweighted graph
vector<vector<int>> unweighted(n);

// Weighted graph using pairs (neighbor, weight)
vector<vector<pair<int, int>>> weighted(n);
weighted[a].push_back({b, weight});

Graph Representation

Adjacency List (Recommended)

Most efficient for sparse graphs. Each vertex maintains a list of its neighbors.

int n, m; // n vertices, m edges
vector<vector<int>> adj(n + 1); // 1-indexed

// Reading edges
for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a); // For undirected graph
}

// Iterate through neighbors of vertex v
for (int neighbor : adj[v]) {
    // Process neighbor
}

Adjacency Matrix

Uses a 2D array where adj[i][j] = 1 if there's an edge from i to j.

int n;
vector<vector<int>> adj_matrix(n + 1, vector<int>(n + 1, 0));

// Add edge
adj_matrix[a][b] = 1;
adj_matrix[b][a] = 1; // For undirected graph

// Check if edge exists
if (adj_matrix[a][b]) {
    // Edge exists
}

Weighted Graph Representation

// Method 1: Vector of pairs
vector<vector<pair<int, int>>> adj(n + 1); // {neighbor, weight}

// Add weighted edge
adj[a].push_back({b, weight});
adj[b].push_back({a, weight}); // For undirected

// Method 2: Separate weight array (if needed)
vector<vector<int>> adj(n + 1);
map<pair<int, int>, int> edge_weight;

adj[a].push_back(b);
edge_weight[{a, b}] = weight;

Common Graph Input Formats

Standard Format

int n, m;
cin >> n >> m; // vertices, edges

vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
}

Weighted Graph Input

int n, m;
cin >> n >> m;

vector<vector<pair<int, int>>> adj(n + 1);
for (int i = 0; i < m; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    adj[a].push_back({b, w});
    adj[b].push_back({a, w});
}

Grid as Graph

int rows, cols;
cin >> rows >> cols;

vector<string> grid(rows);
for (int i = 0; i < rows; i++) {
    cin >> grid[i];
}

// 4-directional movement
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool isValid(int x, int y) {
    return x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] != '#';
}

Basic Graph Properties

// Calculate degree of each vertex
vector<int> degree(n + 1, 0);
for (int v = 1; v <= n; v++) {
    degree[v] = adj[v].size();
}

// Check if graph is complete
bool isComplete(int n, vector<vector<int>>& adj) {
    for (int v = 1; v <= n; v++) {
        if (adj[v].size() != n - 1) return false;
    }
    return true;
}

// Count edges in undirected graph
int countEdges(vector<vector<int>>& adj) {
    int edges = 0;
    for (int v = 1; v <= n; v++) {
        edges += adj[v].size();
    }
    return edges / 2; // Each edge counted twice
}

Graph Construction Examples

Building a Tree from Parent Array

vector<int> parent(n + 1);
vector<vector<int>> tree(n + 1);

for (int i = 2; i <= n; i++) {
    cin >> parent[i]; // Parent of node i
    tree[parent[i]].push_back(i);
    tree[i].push_back(parent[i]);
}

Creating Graph from Edge List

struct Edge {
    int from, to, weight;
};

vector<Edge> edges;
vector<vector<int>> adj(n + 1);

for (int i = 0; i < m; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    edges.push_back({a, b, w});
    adj[a].push_back(b);
    adj[b].push_back(a);
}

Practical Tips