Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in Python

Introduction to Graph Algorithms and Implementation

In this lesson, we learn about graphs and how we represent them.

We'll cover the following...

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.

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 you 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.

Adjacency matrix

An adjacency matrix is a square matrix labeled by graph vertices and is used to represent a finite graph. The entries of the matrix indicate whether the vertex pair is adjacent or not in the graph.

In the adjacency matrix representation, you will need to iterate through all the nodes to identify a node’s neighbors.

Types of graphs

There can be two types of graphs in terms of structure:

Directed graph

The directed graph is the one in which all edges are directed from one vertex to another.

Undirected graph

The undirected graph is the one in which all edges are not directed from one vertex to another.

Mathematical notation

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

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

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

The edge set EE = [[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 GG == (V,E)(V, E) is a sequence of vertices v1,v2,…,vkv1, v2, …, vk, with the property that there are edges between vivi and vi+1vi+1. We say that the path goes from v1v1 to vkvk. The sequence 6,4,5,1,26, 4, 5, 1, 2 defines a path from node 66 to node 22. 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,…,vkv1, v2, …, vk for which

  1. k>2k > 2,
  2. the first k−1k - 1 vertices are all different, and
  3. v1=vkv1 = vk

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

Connectedness

A graph is connected, if for every pair of vertices uu and vv, there is a path from uu to vv.

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!

Python 3.5
class AdjNode:
    """
    A class to represent the adjacency list of the node
    """
    def __init__(self, data):
        """
        Constructor
        :param data : vertex
        """
        self.vertex = data
        self.next = None
class Graph:
    """
    Graph Class ADT
    """
    def __init__(self, vertices):
        """
        Constructor
        :param vertices : Total vertices in a graph
        """
        self.V = vertices
        self.graph = [None] * self.V
        # Function to add an edge in an undirected graph
    def add_edge(self, source, destination):
        """
        add edge
        :param source: Source Vertex
        :param destination: Destination Vertex
        """
        # Adding the node to the source node
        node = AdjNode(destination)
        node.next = self.graph[source]
        self.graph[source] = node
        # Adding the source node to the destination if undirected graph
        
        # Intentionally commented the lines
        #node = AdjNode(source)
        #node.next = self.graph[destination]
        #self.graph[destination] = node
    def print_graph(self):
        """
        A function to print a graph
        """
        for i in range(self.V):
            print("Adjacency list of vertex {}\n head".format(i), end="")
            temp = self.graph[i]
            while temp:
                print(" -> {}".format(temp.vertex), end="")
                temp = temp.next
            print(" \n")
# Main program
if __name__ == "__main__":
    V = 5  # Total vertices
    g = Graph(V)
    g.add_edge(0, 1)
    g.add_edge(0, 4)
    g.add_edge(1, 2)
    g.add_edge(1, 3)
    g.add_edge(1, 4)
    g.add_edge(2, 3)
    g.add_edge(3, 4)
    g.print_graph()

We’ve laid down the foundation of our graph class. The variable V contains an integer specifying the total number of vertices.