Introduction to Graphs

What are Graphs?

A graph is a non-linear data structure consisting of vertices (nodes) and edges that connect these vertices.

Unlike trees, which have a strict hierarchical structure, graphs can represent more complex relationships where connections can form cycles and nodes can have multiple paths between them.

Types of Graphs

1. Directed vs Undirected

   • Directed (Digraph): All edges have a direction (one-way connection). Each edge is represented as an ordered pair (u, v), meaning there is a connection from vertex u to vertex v.
   • Undirected: Edges have no direction (two-way connection). Each edge is represented as an unordered pair {u, v}.
   

2. Weighted vs Unweighted

   • Weighted: Edges have associated costs or weights (e.g. distance, time, or cost between two nodes)
   • Unweighted: All edges have equal importance
   

   Note

   In applications, weight may represent the cost of a route. For example, if vertices A and B are towns in a road network, the weight on edge AB may represent the travel cost between them.

3. Cyclic vs Acyclic

   • Cyclic: Graph that has at least one cycle — a path that starts and ends at the same node.
   • Acyclic: Graph with no cycles.

   Note

   A graph's classification as directed or undirected is independent of whether it is cyclic or acyclic. A graph can be directed and cyclic, directed and acyclic (DAG), undirected and cyclic, or undirected and acyclic.

4. Special Types

   • Complete Graph: Every vertex is connected to every other vertex
   • Bipartite Graph: Vertices can be divided into two sets with edges only between sets
   • Tree: Connected acyclic undirected graph
   • DAG (Directed Acyclic Graph): Directed graph with no cycles

Components of a Graph

Not all nodes in a graph need to be connected to each other. A component is a group of nodes that are connected to each other (directly or indirectly) but have no connection to nodes in any other group.

For example, a graph with nodes 1–10 might have these components: {1, 2, 3, 4}, {5, 6, 7}, {8, 9}, and {10}.

Path in a Graph

A path is a sequence of vertices where each adjacent pair is connected by an edge. A path must contain unique nodes — no node can appear twice.

• Simple Path: A path where no vertex is repeated.
• Closed Path (Cycle): A path that starts and ends at the same vertex, with no other repeated vertices or edges.

Degree of a Node

The degree of a node is a measure of the number of edges connected to it.

Undirected Graphs

The degree of a vertex is the total number of edges connected to it.

Directed Graphs

Since edges have directions, each node has two types of degree:

• In-degree: Number of incoming edges to a vertex.
• Out-degree: Number of outgoing edges from a vertex.

Common Graph Operations

• Basic Operations

  • Add vertex: O(1)
  • Add edge: O(1) for adjacency list, O(1) for matrix
  • Remove vertex: O(V + E) for list, O(V²) for matrix
  • Remove edge: O(E) for list, O(1) for matrix
  • Check if edge exists: O(V) for list, O(1) for matrix

• Traversal Operations

  • Depth First Search (DFS): O(V + E)
  • Breadth First Search (BFS): O(V + E)

Code Examples

Here's how you implement a basic graph in different languages:

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

class Graph {
private:
    int V;
    vector<vector<int>> adj;

public:
    Graph(int vertices) {
        V = vertices;
        adj.resize(V);
    }

    void addEdge(int v, int w) {
        adj[v].push_back(w);
        adj[w].push_back(v);  // For undirected graph
    }

    void BFS(int s) {
        vector<bool> visited(V, false);
        queue<int> queue;

        visited[s] = true;
        queue.push(s);

        while (!queue.empty()) {
            s = queue.front();
            cout << s << " ";
            queue.pop();

            for (int adjacent : adj[s]) {
                if (!visited[adjacent]) {
                    visited[adjacent] = true;
                    queue.push(adjacent);
                }
            }
        }
    }
};

int main() {
    Graph g(5); // Create a graph with 5 vertices

    // Add edges
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);

    cout << "BFS starting from vertex 0: ";
    g.BFS(0); // Perform BFS starting from vertex 0

    return 0;
}

Common Graph Algorithms

• Depth-First Search (DFS)

• Breadth-First Search (BFS)

• Dijkstra's Algorithm

• Bellman-Ford Algorithm

• Floyd-Warshall Algorithm

• Kruskal's Algorithm

• Prim's Algorithm

• Topological Sort

• Articulation Points

Problems to Solve

Important Problems on Graphs

Resources

• Graphs (Grokking Data Structures)
• Graphs: Edge List, Adjacency Matrix, Adjacency List, DFS, BFS
• Graph Series by Striver
• Algorithm Gym :: Graph Algorithms