C# Coding Test Course, Representation of Graphs

Author: [Author Name] | Date: [Date]

Introduction

Algorithms play a very important role in coding tests. In particular, graph algorithms are one of the frequently encountered topics in evaluating problem-solving abilities. In this article, we will take a closer look at how to represent a graph using C# and the process of solving algorithm problems using graphs.

What is a Graph?

A graph is a data structure consisting of nodes (or vertices) and edges that represent the relationships between them. A graph can be divided into two main elements:

Vertices: The nodes of the graph.
Edges: The connections between the vertices.

A graph can be directed (directed graph) or undirected (undirected graph). It can also be classified as connected graph and disconnected graph.

Methods of Graph Representation

There are several ways to represent a graph, but the two commonly used methods are the Adjacency Matrix and the Adjacency List.

1. Adjacency Matrix

The adjacency matrix uses an n x n sized 2D array to represent the graph according to the number of vertices. If vertex i and vertex j are connected, it is set as matrix[i][j] = 1 (for a directed graph) or matrix[i][j] = matrix[j][i] = 1 (for an undirected graph). The advantage of the adjacency matrix is that it can check the existence of edges in O(1) time complexity. However, it may lead to memory waste in sparse graphs, where there are many vertices with few connections.

2. Adjacency List

The adjacency list uses a list of connected vertices for each vertex to represent the graph. Each vertex has a list containing the information of connected vertices, which uses less memory but takes O(V) (where V is the number of vertices) time to find vertices connected to a specific vertex. For graphs with a small number of vertices, the adjacency list is more advantageous than the adjacency matrix.

Algorithm Problem: Finding the Shortest Path

Problem Description

Given the node and edge information of a graph, implement an algorithm to find the shortest path distance from a specific starting node to all other nodes. This problem can be solved using Dijkstra’s algorithm.

Input Format

            - First line: Number of vertices V and number of edges E
            - From the second line: E lines of edge information u v w (weight w from vertex u to vertex v)
            - Last line: Starting vertex S

Sample Input

Sample Output

Solution Process

Dijkstra’s algorithm proceeds by using a priority queue to select the node with the shortest distance found so far and updating the distances of the nodes adjacent to that node.

Initialize the graph in the form of an adjacency list.
Use a priority queue to initialize the distances from the starting vertex.
Select the vertex with the shortest distance from the priority queue and update the distances of all vertices connected to that vertex.
Repeat steps 2-3 until all vertices are processed.

C# Code Implementation


using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split();
        int V = int.Parse(input[0]); // Number of vertices
        int E = int.Parse(input[1]); // Number of edges

        List> edges = new List>();
        for (int i = 0; i < E; i++)
        {
            var edgeInput = Console.ReadLine().Split();
            int u = int.Parse(edgeInput[0]) - 1; // 0-indexed
            int v = int.Parse(edgeInput[1]) - 1; // 0-indexed
            int w = int.Parse(edgeInput[2]);
            edges.Add(Tuple.Create(u, v, w));
        }
        
        int startVertex = int.Parse(Console.ReadLine()) - 1; // 0-indexed
        Dijkstra(V, edges, startVertex);
    }

    static void Dijkstra(int V, List> edges, int startVertex)
    {
        // Initialize the graph
        List>> graph = Enumerable.Range(0, V)
                                                        .Select(x => new List>())
                                                        .ToList();

        foreach (var edge in edges)
        {
            graph[edge.Item1].Add(Tuple.Create(edge.Item2, edge.Item3));
            graph[edge.Item2].Add(Tuple.Create(edge.Item1, edge.Item3)); // Undirected graph
        }

        // Initialize distance array
        int[] distances = new int[V];
        for (int i = 0; i < V; i++)
            distances[i] = int.MaxValue;
        distances[startVertex] = 0;

        // Initialize priority queue
        var priorityQueue = new SortedSet>();
        priorityQueue.Add(Tuple.Create(0, startVertex)); // (distance, vertex)

        while (priorityQueue.Any())
        {
            var current = priorityQueue.Min;
            priorityQueue.Remove(current);
            int currentDistance = current.Item1;
            int currentVertex = current.Item2;

            // Skip if a shorter path has already been found
            if (currentDistance > distances[currentVertex])
                continue;

            foreach (var neighbor in graph[currentVertex])
            {
                int neighborVertex = neighbor.Item1;
                int edgeWeight = neighbor.Item2;

                // Update distance
                if (distances[currentVertex] + edgeWeight < distances[neighborVertex])
                {
                    distances[neighborVertex] = distances[currentVertex] + edgeWeight;
                    priorityQueue.Add(Tuple.Create(distances[neighborVertex], neighborVertex));
                }
            }
        }

        // Output results
        for (int i = 0; i < V; i++)
        {
            if (distances[i] == int.MaxValue)
                Console.WriteLine("INF");
            else
                Console.WriteLine(distances[i]);
        }
    }
}

Conclusion

This course taught the basic concepts and methods of graph representation, and how to implement Dijkstra's algorithm in C# to solve the shortest path problem. Algorithm problems require continuous practice. I hope you find your own solutions by solving various problems.