Understanding Graphs

What Is a Graph?

A graph is a powerful and flexible data structure for representing relationships between objects. It consists of:

  • Vertices (nodes) ? represent entities

  • Edges ? represent connections/relationships

Graphs are used in real-world systems such as:

  • Social networks (users connected to users)

  • Google Maps (cities connected by roads)

  • Recommendation systems

  • Computer networks

Graphs allow modeling of complex, interconnected data that linear structures cannot represent.

Types of Graphs

1. Directed Graph (Digraph)

Edges have a direction.

A ? B

2. Undirected Graph

Edges have no direction.

A — B

3. Weighted Graph

Each edge has a weight (cost/distance).

A —5— B

4. Unweighted Graph

Edges have no weight.

5. Cyclic Graph

Contains at least one cycle.

6. Acyclic Graph

Contains no cycles.
Example: Trees

7. Connected Graph

Every vertex is reachable from every other vertex.

8. Disconnected Graph

Some vertices are isolated.

Graph Representation

Graphs can be represented in two main ways:

1. Adjacency Matrix

A 2D matrix where:

  • 1 means an edge exists

  • 0 means no edge

Example:

  A B C
A 0 1 0
B 1 0 1
C 0 1 0

2. Adjacency List

Uses a list of lists or dictionary.

A ? B
B ? A, C
C ? B

Example in C#

Dictionary<int, List<int>> graph = new();
graph[0] = new List<int> { 1, 2 };
graph[1] = new List<int> { 0, 3 };
graph[2] = new List<int> { 0 };
graph[3] = new List<int> { 1 };

Graph Traversal

Traversal means visiting all nodes in a graph.

There are two main traversal techniques:

1. Breadth-First Search (BFS)

Uses a queue.

  • Visits nodes level by level

  • Good for finding shortest paths

BFS Example

void BFS(int start, Dictionary<int, List<int>> graph)
{
    Queue<int> q = new();
    HashSet<int> visited = new();

    q.Enqueue(start);
    visited.Add(start);

    while (q.Count > 0)
    {
        int node = q.Dequeue();
        Console.Write(node + " ");

        foreach (var neighbor in graph[node])
        {
            if (!visited.Contains(neighbor))
            {
                visited.Add(neighbor);
                q.Enqueue(neighbor);
            }
        }
    }
}

2. Depth-First Search (DFS)

Uses recursion or stack.

  • Goes deep into a branch before backtracking

  • Good for detecting cycles and exploring components

DFS Example

void DFS(int node, Dictionary<int, List<int>> graph, HashSet<int> visited)
{
    visited.Add(node);
    Console.Write(node + " ");

    foreach (var neighbor in graph[node])
    {
        if (!visited.Contains(neighbor))
        {
            DFS(neighbor, graph, visited);
        }
    }
}

Applications of Graphs

Graphs are used everywhere:

1. Social Networks

  • Facebook friend suggestions

  • LinkedIn connections

2. Maps and GPS

  • Shortest route

  • Traffic flow

3. Web Page Ranking

  • Google PageRank algorithm

4. Networking

  • Routers and data packet transfer

5. AI and Machine Learning

  • Game trees and state transitions

6. Biology

  • Gene sequencing

Weighted Graph Algorithms

Graphs allow solving complex problems efficiently using algorithms like:

1. Dijkstra’s Algorithm

  • Finds shortest path in weighted graphs

  • Used in routing and navigation systems

2. Bellman-Ford Algorithm

  • Handles negative weights

3. Floyd–Warshall Algorithm

  • Computes shortest paths between all node pairs

4. Minimum Spanning Tree Algorithms

  • Kruskal's Algorithm

  • Prim’s Algorithm

These will be covered in the next chapters.

Detecting Cycles

Graphs often need cycle detection.

Cycle Detection in DFS

bool DFS_Cycle(int node, int parent, Dictionary<int, List<int>> graph, HashSet<int> visited)
{
    visited.Add(node);

    foreach (var neighbor in graph[node])
    {
        if (!visited.Contains(neighbor))
        {
            if (DFS_Cycle(neighbor, node, graph, visited)) return true;
        }
        else if (neighbor != parent)
        {
            return true;
        }
    }
    return false;
}

Time and Space Complexity

Adjacency Matrix

  • Space: O(n²)

  • Search neighbors: O(n)

Adjacency List

  • Space: O(V + E)

  • Faster and more memory-efficient

Traversal

  • BFS: O(V + E)

  • DFS: O(V + E)

Summary

Graphs are one of the most versatile data structures. They model networks, relationships, routes, and many real-world problems.

Key takeaways:

  • Used for social networks, maps, and recommendation systems

  • Represented using an adjacency list or a matrix

  • Traversal methods: BFS and DFS

  • Basis for many advanced algorithms