Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Graph as an Abstract Data Type (ADT)
Table of Contents

Implementing the ADT operations

  1. add_vertex(vertex)
  1. add_edge(vertex1, vertex2)

A complete executable example

As discussed earlier in the course, an abstract data type (ADT) is a theoretical concept that defines a set of operations and their behavior without specifying the internal representation of the data or the algorithms used to implement those operations. It provides a high-level description of the data and the functions that can be performed on it.

Here are some of the operations can be performed on graphs:

  1. Adding a new vertex
  2. Removing a vertex
  3. Adding an edge between two vertices
  4. Removing an edge between two vertices
  5. Getting a list of all the vertices
  6. Checking if two graph nodes are adjacent to each other or not
  7. Getting count of the total vertices in the graph
  8. Getting count of the total edges in the graph
  9. Getting a list of the graph edges
  10. Getting neighbors of a graph vertex

There are a few other ADT operations involving graph searching and traversal. Searching and traversal operations require detailed illustrations. Thereby, we will discuss those in the Graph Traversals section.

Python3
Python3
. . . .

Implementing the ADT operations

In the beginning of this section, we mentioned ten major and the most common ADT operations associated with the graphs. Let's discuss each operation individually - understanding how is it implemented.

1. add_vertex(vertex)

The function add_vertex(vertex) is a common operation in graph theory, where it adds a new vertex (also called a node or point) to a graph data structure. The vertex is a fundamental unit of a graph and represents an entity or an element. Adding a vertex expands the graph and creates potential connections (edges) between this new vertex and existing vertices.

In an adjacency list, each vertex is associated with a list of its adjacent vertices. We are using a dictionary or map for implementing the adjacency list. Thereby, we are able to store node key and value (s) associated with it.

For this course, we assume that graphs don't have any extra satellite data or values associated with it. Therefore, we will add an empty vector or list as a value attribute for the new graph node or vertex.

You can add a new vertex following the two main steps:

  • Check if vertex already exists

    • Use predefined map or dictionary search methods

  • If not, add it by inserting new key-value pair

    • Keep value of the new inserted vertex as empty list

Here is a generalized pseudocode:

Graph is represented as:

adjacencyList (map/dictionary):
  key: vertex 
  value: list of adjacent vertices

Function addVertex(vertex)

  if vertex does not exist in adjacencyList
  
    add new key-value pair:
      key: vertex
      value: empty list     
    end if
    
end Function

Let's now see the actual implementation of the add_vertex() method.

Python3
Python3
. . . .

2. add_edge(vertex1, vertex2)

Pseudocode

Function add_edge(vertex1, vertex2):

  if vertex1 is not present in adjacencyList:
      initialize adjacencyList[vertex1] as an empty list
  add vertex2 to adjacencyList[vertex1]

  if vertex2 is not present in adjacencyList:
      initialize adjacencyList[vertex2] as an empty list
  add vertex1 to adjacencyList[vertex2]
  
End Function

Explanation

To implement the add_edge() function, we need to add an undirected edge between vertex1 and vertex2 in the graph's adjacency list representation.

  1. For vertex1:

    • Check if vertex1 is already present in the adjacency list.
    • If not, initialize its entry as an empty list (or vector in C++).
    • Append vertex2 to vertex1's adjacency list, indicating an edge.

  2. For vertex2:

    • Similarly, check if vertex2 exists in the adjacency list.
    • If not, initialize its entry as an empty list (or vector in C++).
    • Append vertex1 to vertex2's adjacency list, ensuring the graph is undirected.
Python3
Python3
. . . .

A complete executable example

Python3
Python3
. . . .
Mark as Completed

Table of Contents

Implementing the ADT operations

  1. add_vertex(vertex)
  1. add_edge(vertex1, vertex2)

A complete executable example