Introduction to Graph Algorithms and Implementation

Explore the fundamentals of graph algorithms in C#. Understand graph representations like adjacency lists and matrices, identify graph types such as directed and undirected, and grasp key concepts including paths, cycles, and connectivity. This lesson equips you to implement graph data structures and lays the groundwork for solving graph problems efficiently.

We'll cover the following...

What is a graph?
Representing graphs
- Adjacency list
- Adjacency matrix
Types of graphs
Mathematical notation
Properties
The graph class

In this chapter, we will be studying graph algorithms. These algorithms use the basic graph structure.

Before we begin, let’s briefly discuss what graphs are.

What is a graph?

A graph is an abstract notation used to represent the connection between pairs of objects. It can be used to represent networks: systems of roads, airline flights from city to city, how the internet is connected, or social connectivity on Facebook, Twitter, etc. We use some standard graph algorithms to solve these otherwise difficult problems.

Representing graphs

Graphs represent pairwise relationships between objects. Graphs are mathematical structures and, therefore, can be visualized by using two basic components: nodes and edges.

A node, also known as a vertex, is a fundamental part of a graph. It is the entity that has a name, known as the key, and other information related to that entity. A relationship between nodes is expressed using edges. An edge between two nodes expresses the relationship between the nodes.

Graphs can be represented as an adjacency matrix or adjacency list.

Note: For the remainder of this chapter, we will be using adjacency lists because algorithms can be performed more efficiently using this form of representation.

Adjacency list

An adjacency list is used to represent a finite graph. The adjacency list representation allows us to iterate through the neighbors of a node easily. Each index in the list represents the vertex and each node that is linked with that index represents its neighboring vertices.

Mathematical notation

The set of vertices of graph $G$ is denoted by $V(G)$ , or just $V$ if there is no ambiguity.

An edge between vertices $u$ and $v$ is written as ${u, v}$ . The set of edges of $G$ is denoted $E(G)$ , or just $E$ if there is no ambiguity.

The graph in this picture has the vertex set $V = [1, 2, 3, 4, 5, 6]$ .

The edge set $E = [[1, 2], [1, 5], [2, 3], [2, 5], [3, 4], [4, 5], [4, 6]]$ .

Properties

Here are some properties of a graph:

Path

A path in a graph $G$ $=$ $(V, E)$ is a sequence of vertices $v1, v2, …, vk$ , with the property that there are edges between $vi$ and $vi+1$ . We say that the path goes from $v1$ to $vk$ . The sequence $6, 4, 5, 1, 2$ defines a path from node $6$ to node $2$ . Similarly, other paths can be created by traversing the edges of the graph. A path is simple if its vertices are all different.

Cycle

A cycle is a path $v1, v2, …, vk$ for which

$k > 2$ ,
the first $k - 1$ vertices are all different, and
$v1 = vk$

The sequence $4, 5, 2, 3, 4$ is a cycle in the graph above.

Connectedness

A graph is connected if, for every pair of vertices $u$ and $v$ , there is a path from $u$ to $v$ .

The graph class

The graph class consists of two data members:

The total number of vertices in the graph
A list to store adjacent vertices

So, let’s get down to the implementation!

C# 9.0

using System;
// A class to represent the adjacency list of the node
public class AdjNode
{
    // Constructor
    public AdjNode(int data)
    {
        Vertex = data;
        Next = null;
    }
    public int Vertex;
    public AdjNode Next;
}
// Graph Class ADT
public class Graph
{
    // Constructor
    public Graph(int vertices)
    {
        V = vertices;
        graph = new AdjNode[V];     
    }
    private int V;
    private AdjNode[] graph;
    // Method to add an edge in an undirected graph
    public void AddEdge(int source, int destination)
    {
        // Adding the node to the source node
        AdjNode node = new AdjNode(destination);
        node.Next = graph[source];
        graph[source] = node;
        // Adding the source node to the destination if undirected graph
        // Intentionally commented the lines
        //node = new AdjNode(source);
        //node.Next = graph[destination];
        //graph[destination] = node;
    }
    // A method to print a graph
    public void PrintGraph()
    {
        for (int i = 0; i < V; i++)
        {
            Console.Write("Adjacency list of vertex " + i + "\n head");
            AdjNode temp = graph[i];
            while (temp != null)
            {
                Console.Write(" -> " + temp.Vertex);
                temp = temp.Next;
            }
            Console.WriteLine(" \n");
        }
    }
}
public class Program
{
    // Main program
    static void Main(string[] args)
    {
        int V = 5;  // Total vertices
        Graph g = new Graph(V);
        g.AddEdge(0, 1);
        g.AddEdge(0, 4);
        g.AddEdge(1, 2);
        g.AddEdge(1, 3);
        g.AddEdge(1, 4);
        g.AddEdge(2, 3);
        g.AddEdge(3, 4);
        g.PrintGraph();
    }
}

1.Introduction

2.Algorithmic Paradigms

3.Asymptotic Analysis

4.Sorting and Searching

5.Graph Algorithms

6.Greedy Algorithms

7.Dynamic Programming

8.Divide and Conquer

9.Conclusion