Skip to main content

6.7 - Graphs

Graphs are versatile data structures that represent a collection of nodes (vertices) connected by edges. Unlike trees, which are a specific type of graph with hierarchical relationships, graphs can represent more complex relationships between objects. This section explores graph representations, algorithms, and applications in C#.

6.7.1 - Graph Terminology​

Before diving into specific graph types and algorithms, let's understand some common terminology:

  • Vertex (Node): A fundamental unit of a graph that represents an entity.
  • Edge: A connection between two vertices that represents a relationship.
  • Adjacent Vertices: Two vertices connected by an edge.
  • Path: A sequence of vertices where each adjacent pair is connected by an edge.
  • Cycle: A path that starts and ends at the same vertex.
  • Connected Graph: A graph where there is a path between every pair of vertices.
  • Disconnected Graph: A graph that is not connected.
  • Directed Graph (Digraph): A graph where edges have a direction.
  • Undirected Graph: A graph where edges have no direction.
  • Weighted Graph: A graph where edges have weights or costs.
  • Unweighted Graph: A graph where edges have no weights.
  • Degree: The number of edges connected to a vertex.
  • In-degree: The number of incoming edges to a vertex (in a directed graph).
  • Out-degree: The number of outgoing edges from a vertex (in a directed graph).

6.7.2 - Types of Graphs​

There are various types of graphs, each with its own characteristics and use cases:

6.7.2.1 - Undirected Graph​

In an undirected graph, edges have no direction. If there is an edge between vertices A and B, then there is also an edge between vertices B and A.

A --- B
|     |
|     |
C --- D

6.7.2.2 - Directed Graph (Digraph)​

In a directed graph, edges have a direction. If there is an edge from vertex A to vertex B, it doesn't necessarily mean there is an edge from vertex B to vertex A.

A --> B
|     |
v     v
C <-- D

6.7.2.3 - Weighted Graph​

In a weighted graph, edges have weights or costs associated with them.

A --5-- B
|       |
|       |
2       3
|       |
v       v
C --1-- D

6.7.2.4 - Cyclic Graph​

A cyclic graph contains at least one cycle, which is a path that starts and ends at the same vertex.

A --> B
^     |
|     v
C <-- D

6.7.2.5 - Acyclic Graph​

An acyclic graph contains no cycles.

A --> B
|     |
v     v
C --> D

6.7.2.6 - Connected Graph​

A connected graph has a path between every pair of vertices.

A --- B
|     |
|     |
C --- D

6.7.2.7 - Disconnected Graph​

A disconnected graph has at least one pair of vertices with no path between them.

A --- B    E --- F
|     |    |     |
|     |    |     |
C --- D    G --- H

6.7.3 - Graph Representations​

There are several ways to represent a graph in code:

6.7.3.1 - Adjacency Matrix​

An adjacency matrix is a 2D array where the element at position (i, j) represents the edge between vertices i and j. For an unweighted graph, the value is 1 if there is an edge, and 0 otherwise. For a weighted graph, the value is the weight of the edge, or a special value (like infinity) if there is no edge.

public class AdjacencyMatrixGraph
{
    private int[,] matrix;
    private int vertices;
    private bool isDirected;

    public AdjacencyMatrixGraph(int vertices, bool isDirected = false)
    {
        this.vertices = vertices;
        this.isDirected = isDirected;
        matrix = new int[vertices, vertices];
    }

    public void AddEdge(int source, int destination, int weight = 1)
    {
        matrix[source, destination] = weight;

        if (!isDirected)
            matrix[destination, source] = weight;
    }

    public void RemoveEdge(int source, int destination)
    {
        matrix[source, destination] = 0;

        if (!isDirected)
            matrix[destination, source] = 0;
    }

    public bool HasEdge(int source, int destination)
    {
        return matrix[source, destination] != 0;
    }

    public int GetWeight(int source, int destination)
    {
        return matrix[source, destination];
    }

    public List<int> GetNeighbors(int vertex)
    {
        List<int> neighbors = new List<int>();

        for (int i = 0; i < vertices; i++)
        {
            if (matrix[vertex, i] != 0)
                neighbors.Add(i);
        }

        return neighbors;
    }
}

6.7.3.2 - Adjacency List​

An adjacency list is a collection of lists or arrays, where each list represents the neighbors of a vertex. For a weighted graph, each neighbor can be represented as a pair of (vertex, weight).

public class AdjacencyListGraph
{
    private List<List<(int Vertex, int Weight)>> adjacencyList;
    private int vertices;
    private bool isDirected;

    public AdjacencyListGraph(int vertices, bool isDirected = false)
    {
        this.vertices = vertices;
        this.isDirected = isDirected;
        adjacencyList = new List<List<(int, int)>>(vertices);

        for (int i = 0; i < vertices; i++)
            adjacencyList.Add(new List<(int, int)>());
    }

    public void AddEdge(int source, int destination, int weight = 1)
    {
        adjacencyList[source].Add((destination, weight));

        if (!isDirected)
            adjacencyList[destination].Add((source, weight));
    }

    public void RemoveEdge(int source, int destination)
    {
        adjacencyList[source].RemoveAll(e => e.Vertex == destination);

        if (!isDirected)
            adjacencyList[destination].RemoveAll(e => e.Vertex == source);
    }

    public bool HasEdge(int source, int destination)
    {
        return adjacencyList[source].Any(e => e.Vertex == destination);
    }

    public int GetWeight(int source, int destination)
    {
        var edge = adjacencyList[source].FirstOrDefault(e => e.Vertex == destination);
        return edge.Weight;
    }

    public List<int> GetNeighbors(int vertex)
    {
        return adjacencyList[vertex].Select(e => e.Vertex).ToList();
    }
}

6.7.3.3 - Edge List​

An edge list is a collection of all edges in the graph. Each edge is represented as a tuple of (source, destination, weight).

public class EdgeListGraph
{
    private List<(int Source, int Destination, int Weight)> edges;
    private int vertices;
    private bool isDirected;

    public EdgeListGraph(int vertices, bool isDirected = false)
    {
        this.vertices = vertices;
        this.isDirected = isDirected;
        edges = new List<(int, int, int)>();
    }

    public void AddEdge(int source, int destination, int weight = 1)
    {
        edges.Add((source, destination, weight));

        if (!isDirected)
            edges.Add((destination, source, weight));
    }

    public void RemoveEdge(int source, int destination)
    {
        edges.RemoveAll(e => e.Source == source && e.Destination == destination);

        if (!isDirected)
            edges.RemoveAll(e => e.Source == destination && e.Destination == source);
    }

    public bool HasEdge(int source, int destination)
    {
        return edges.Any(e => e.Source == source && e.Destination == destination);
    }

    public int GetWeight(int source, int destination)
    {
        var edge = edges.FirstOrDefault(e => e.Source == source && e.Destination == destination);
        return edge.Weight;
    }

    public List<int> GetNeighbors(int vertex)
    {
        return edges
            .Where(e => e.Source == vertex)
            .Select(e => e.Destination)
            .ToList();
    }
}

6.7.4 - Graph Traversal​

Graph traversal is the process of visiting each vertex in a graph exactly once. There are two main traversal algorithms:

6.7.4.1 - Depth-First Search (DFS)​

Depth-First Search explores as far as possible along each branch before backtracking.

public void DepthFirstSearch(int startVertex, Action<int> action)
{
    bool[] visited = new bool[vertices];
    DepthFirstSearchRecursive(startVertex, visited, action);
}

private void DepthFirstSearchRecursive(int vertex, bool[] visited, Action<int> action)
{
    visited[vertex] = true;
    action(vertex);

    foreach (int neighbor in GetNeighbors(vertex))
    {
        if (!visited[neighbor])
            DepthFirstSearchRecursive(neighbor, visited, action);
    }
}

6.7.4.2 - Breadth-First Search (BFS)​

Breadth-First Search explores all vertices at the present depth before moving on to vertices at the next depth level.

public void BreadthFirstSearch(int startVertex, Action<int> action)
{
    bool[] visited = new bool[vertices];
    Queue<int> queue = new Queue<int>();

    visited[startVertex] = true;
    queue.Enqueue(startVertex);

    while (queue.Count > 0)
    {
        int vertex = queue.Dequeue();
        action(vertex);

        foreach (int neighbor in GetNeighbors(vertex))
        {
            if (!visited[neighbor])
            {
                visited[neighbor] = true;
                queue.Enqueue(neighbor);
            }
        }
    }
}

6.7.5 - Graph Algorithms​

Here are some common graph algorithms:

6.7.5.1 - Shortest Path Algorithms​

6.7.5.1.1 - Dijkstra's Algorithm​

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights.

public int[] Dijkstra(int source)
{
    int[] distance = new int[vertices];
    bool[] visited = new bool[vertices];

    for (int i = 0; i < vertices; i++)
        distance[i] = int.MaxValue;

    distance[source] = 0;

    for (int count = 0; count < vertices - 1; count++)
    {
        int u = MinimumDistance(distance, visited);
        visited[u] = true;

        for (int v = 0; v < vertices; v++)
        {
            if (!visited[v] && HasEdge(u, v) && distance[u] != int.MaxValue &&
                distance[u] + GetWeight(u, v) < distance[v])
            {
                distance[v] = distance[u] + GetWeight(u, v);
            }
        }
    }

    return distance;
}

private int MinimumDistance(int[] distance, bool[] visited)
{
    int min = int.MaxValue;
    int minIndex = -1;

    for (int v = 0; v < vertices; v++)
    {
        if (!visited[v] && distance[v] <= min)
        {
            min = distance[v];
            minIndex = v;
        }
    }

    return minIndex;
}

6.7.5.1.2 - Bellman-Ford Algorithm​

The Bellman-Ford algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph, even if the graph contains negative edge weights (but no negative cycles).

public int[] BellmanFord(int source)
{
    int[] distance = new int[vertices];

    for (int i = 0; i < vertices; i++)
        distance[i] = int.MaxValue;

    distance[source] = 0;

    // Relax all edges |V| - 1 times
    for (int i = 1; i < vertices; i++)
    {
        for (int u = 0; u < vertices; u++)
        {
            foreach (var edge in GetEdges(u))
            {
                int v = edge.Destination;
                int weight = edge.Weight;

                if (distance[u] != int.MaxValue && distance[u] + weight < distance[v])
                    distance[v] = distance[u] + weight;
            }
        }
    }

    // Check for negative-weight cycles
    for (int u = 0; u < vertices; u++)
    {
        foreach (var edge in GetEdges(u))
        {
            int v = edge.Destination;
            int weight = edge.Weight;

            if (distance[u] != int.MaxValue && distance[u] + weight < distance[v])
                throw new InvalidOperationException("Graph contains a negative-weight cycle");
        }
    }

    return distance;
}

private List<(int Destination, int Weight)> GetEdges(int vertex)
{
    // Implementation depends on the graph representation
    // For adjacency list, it's straightforward
    return adjacencyList[vertex];
}

6.7.5.1.3 - Floyd-Warshall Algorithm​

The Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in a weighted graph.

public int[,] FloydWarshall()
{
    int[,] distance = new int[vertices, vertices];

    // Initialize the distance matrix
    for (int i = 0; i < vertices; i++)
    {
        for (int j = 0; j < vertices; j++)
        {
            if (i == j)
                distance[i, j] = 0;
            else if (HasEdge(i, j))
                distance[i, j] = GetWeight(i, j);
            else
                distance[i, j] = int.MaxValue;
        }
    }

    // Find the shortest path between all pairs of vertices
    for (int k = 0; k < vertices; k++)
    {
        for (int i = 0; i < vertices; i++)
        {
            for (int j = 0; j < vertices; j++)
            {
                if (distance[i, k] != int.MaxValue && distance[k, j] != int.MaxValue &&
                    distance[i, k] + distance[k, j] < distance[i, j])
                {
                    distance[i, j] = distance[i, k] + distance[k, j];
                }
            }
        }
    }

    return distance;
}

6.7.5.2 - Minimum Spanning Tree Algorithms​

6.7.5.2.1 - Prim's Algorithm​

Prim's algorithm finds a minimum spanning tree for a connected weighted undirected graph.

public List<(int Source, int Destination, int Weight)> Prim()
{
    List<(int, int, int)> mst = new List<(int, int, int)>();
    bool[] inMST = new bool[vertices];
    int[] key = new int[vertices];
    int[] parent = new int[vertices];

    for (int i = 0; i < vertices; i++)
    {
        key[i] = int.MaxValue;
        inMST[i] = false;
    }

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < vertices - 1; count++)
    {
        int u = MinimumKey(key, inMST);
        inMST[u] = true;

        for (int v = 0; v < vertices; v++)
        {
            if (HasEdge(u, v) && !inMST[v] && GetWeight(u, v) < key[v])
            {
                parent[v] = u;
                key[v] = GetWeight(u, v);
            }
        }
    }

    for (int i = 1; i < vertices; i++)
    {
        mst.Add((parent[i], i, GetWeight(parent[i], i)));
    }

    return mst;
}

private int MinimumKey(int[] key, bool[] inMST)
{
    int min = int.MaxValue;
    int minIndex = -1;

    for (int v = 0; v < vertices; v++)
    {
        if (!inMST[v] && key[v] < min)
        {
            min = key[v];
            minIndex = v;
        }
    }

    return minIndex;
}

6.7.5.2.2 - Kruskal's Algorithm​

Kruskal's algorithm finds a minimum spanning tree for a connected weighted undirected graph.

public List<(int Source, int Destination, int Weight)> Kruskal()
{
    List<(int, int, int)> mst = new List<(int, int, int)>();
    List<(int Source, int Destination, int Weight)> edges = GetAllEdges();
    
    // Sort edges by weight
    edges.Sort((a, b) => a.Weight.CompareTo(b.Weight));
    
    DisjointSet disjointSet = new DisjointSet(vertices);
    
    foreach (var edge in edges)
    {
        int source = edge.Source;
        int destination = edge.Destination;
        
        if (disjointSet.Find(source) != disjointSet.Find(destination))
        {
            mst.Add(edge);
            disjointSet.Union(source, destination);
        }
    }
    
    return mst;
}

private List<(int Source, int Destination, int Weight)> GetAllEdges()
{
    // Implementation depends on the graph representation
    // For edge list, it's straightforward
    return edges;
}

private class DisjointSet
{
    private int[] parent;
    private int[] rank;
    
    public DisjointSet(int n)
    {
        parent = new int[n];
        rank = new int[n];
        
        for (int i = 0; i < n; i++)
        {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    
    public int Find(int x)
    {
        if (parent[x] != x)
            parent[x] = Find(parent[x]);
        return parent[x];
    }
    
    public void Union(int x, int y)
    {
        int xRoot = Find(x);
        int yRoot = Find(y);
        
        if (xRoot == yRoot)
            return;
        
        if (rank[xRoot] < rank[yRoot])
            parent[xRoot] = yRoot;
        else if (rank[xRoot] > rank[yRoot])
            parent[yRoot] = xRoot;
        else
        {
            parent[yRoot] = xRoot;
            rank[xRoot]++;
        }
    }
}

6.7.5.3 - Topological Sort​

Topological sort is an ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering.

public List<int> TopologicalSort()
{
    List<int> result = new List<int>();
    bool[] visited = new bool[vertices];
    Stack<int> stack = new Stack<int>();
    
    for (int i = 0; i < vertices; i++)
    {
        if (!visited[i])
            TopologicalSortUtil(i, visited, stack);
    }
    
    while (stack.Count > 0)
        result.Add(stack.Pop());
    
    return result;
}

private void TopologicalSortUtil(int vertex, bool[] visited, Stack<int> stack)
{
    visited[vertex] = true;
    
    foreach (int neighbor in GetNeighbors(vertex))
    {
        if (!visited[neighbor])
            TopologicalSortUtil(neighbor, visited, stack);
    }
    
    stack.Push(vertex);
}

6.7.5.4 - Cycle Detection​

6.7.5.4.1 - Cycle Detection in Undirected Graph​

public bool HasCycle()
{
    bool[] visited = new bool[vertices];
    
    for (int i = 0; i < vertices; i++)
    {
        if (!visited[i])
        {
            if (HasCycleUtil(i, visited, -1))
                return true;
        }
    }
    
    return false;
}

private bool HasCycleUtil(int vertex, bool[] visited, int parent)
{
    visited[vertex] = true;
    
    foreach (int neighbor in GetNeighbors(vertex))
    {
        if (!visited[neighbor])
        {
            if (HasCycleUtil(neighbor, visited, vertex))
                return true;
        }
        else if (neighbor != parent)
        {
            return true;
        }
    }
    
    return false;
}

6.7.5.4.2 - Cycle Detection in Directed Graph​

public bool HasCycle()
{
    bool[] visited = new bool[vertices];
    bool[] recStack = new bool[vertices];
    
    for (int i = 0; i < vertices; i++)
    {
        if (HasCycleUtil(i, visited, recStack))
            return true;
    }
    
    return false;
}

private bool HasCycleUtil(int vertex, bool[] visited, bool[] recStack)
{
    if (!visited[vertex])
    {
        visited[vertex] = true;
        recStack[vertex] = true;
        
        foreach (int neighbor in GetNeighbors(vertex))
        {
            if (!visited[neighbor] && HasCycleUtil(neighbor, visited, recStack))
                return true;
            else if (recStack[neighbor])
                return true;
        }
    }
    
    recStack[vertex] = false;
    return false;
}

6.7.5.5 - Strongly Connected Components​

A strongly connected component (SCC) is a subgraph in which every vertex is reachable from every other vertex.

6.7.5.5.1 - Kosaraju's Algorithm​

public List<List<int>> StronglyConnectedComponents()
{
    List<List<int>> sccs = new List<List<int>>();
    bool[] visited = new bool[vertices];
    Stack<int> stack = new Stack<int>();
    
    // Fill the stack with vertices in order of finishing time
    for (int i = 0; i < vertices; i++)
    {
        if (!visited[i])
            FillOrder(i, visited, stack);
    }
    
    // Create a transposed graph
    AdjacencyListGraph transposed = Transpose();
    
    // Reset visited array
    for (int i = 0; i < vertices; i++)
        visited[i] = false;
    
    // Process vertices in order of finishing time
    while (stack.Count > 0)
    {
        int vertex = stack.Pop();
        
        if (!visited[vertex])
        {
            List<int> scc = new List<int>();
            transposed.DFSUtil(vertex, visited, scc);
            sccs.Add(scc);
        }
    }
    
    return sccs;
}

private void FillOrder(int vertex, bool[] visited, Stack<int> stack)
{
    visited[vertex] = true;
    
    foreach (int neighbor in GetNeighbors(vertex))
    {
        if (!visited[neighbor])
            FillOrder(neighbor, visited, stack);
    }
    
    stack.Push(vertex);
}

private AdjacencyListGraph Transpose()
{
    AdjacencyListGraph transposed = new AdjacencyListGraph(vertices, true);
    
    for (int i = 0; i < vertices; i++)
    {
        foreach (var edge in GetEdges(i))
        {
            transposed.AddEdge(edge.Destination, i, edge.Weight);
        }
    }
    
    return transposed;
}

private void DFSUtil(int vertex, bool[] visited, List<int> component)
{
    visited[vertex] = true;
    component.Add(vertex);
    
    foreach (int neighbor in GetNeighbors(vertex))
    {
        if (!visited[neighbor])
            DFSUtil(neighbor, visited, component);
    }
}

6.7.6 - Graph Applications​

Graphs are used in various applications:

  1. Social Networks: Representing relationships between people.
  2. Web Pages: Representing links between web pages.
  3. Maps and Navigation: Representing roads and intersections.
  4. Network Routing: Representing network topology and routing information.
  5. Recommendation Systems: Representing relationships between users and items.
  6. Dependency Resolution: Representing dependencies between components.
  7. Compiler Design: Representing control flow and data flow.

6.7.7 - Graph Libraries in C#​

While C# doesn't provide built-in graph data structures, there are several third-party libraries that offer graph functionality:

  1. QuikGraph: A generic graph data structure library.
  2. NodeXL: A library for network analysis and visualization.
  3. Graph#: A graph layout framework.
  4. Microsoft Automatic Graph Layout (MSAGL): A tool for graph layout and viewing.

6.7.8 - Performance Considerations​

When working with graphs, consider the following performance aspects:

  1. Graph Representation: The choice of graph representation affects the performance of operations. Adjacency matrices are better for dense graphs, while adjacency lists are better for sparse graphs.
  2. Algorithm Choice: Different algorithms have different time and space complexities. Choose the appropriate algorithm for your specific requirements.
  3. Memory Usage: Graphs can use a significant amount of memory, especially with many vertices and edges.
  4. Parallelization: Some graph algorithms can be parallelized to improve performance.

6.7.9 - Best Practices​

Here are some best practices for working with graphs in C#:

  1. Choose the Right Representation: Use the appropriate graph representation for your specific requirements.
  2. Use Efficient Algorithms: Choose efficient algorithms for your specific operations.
  3. Consider Memory Usage: Be mindful of memory usage, especially with large graphs.
  4. Use Libraries When Possible: Use third-party libraries for complex graph operations.
  5. Test with Different Graph Sizes: Test your code with different graph sizes to ensure it scales well.
  6. Document Graph Structure: Document the structure of your graph to make it easier to understand and maintain.

In the next section, we'll explore advanced data structures that combine the concepts we've learned so far to solve specific problems efficiently.