☰
×

Graphs in Python

Chapters
Graphs Python Feature

A Graph is a non-linear data structure comprising nodes and edges. The nodes of a graph are also called vertices and the lines or arcs connecting two vertices are called edges.

Graphs are used to solve many real-life problems and can be used to maintain networks. The networks may include paths in a city or telephone network or circuit network. Social networks such as LinkedIn and Facebook use Graphs to implement their networks.

Image 253

Types of Graphs

There are several types of graphs data structure in Python. For the implementation of functions and algorithms, we will discuss 5 basic types of graphs. We will discuss other types of graphs in further applications when the need arises.

Directed Graph

A directed graph is a graph with a set of nodes that are connected together, where all the edges are directed from one vertex to another. A directed graph is sometimes called a digraph. Ordered pair (V1, V2) means an edge between V1 and V2 with an arrow directed from V1 to V2.

Undirected Graph

An undirected graph is a graph having a set of nodes and a set of links between the nodes. Each node is called a vertex, each link is called an edge, and each edge connects two vertices. The order of the two connected nodes is unimportant.

Cyclic Graph

The cyclic graph is a graph that contains at least one graph cycle. This means that some number of vertices in the graph will be connected in a closed chain.  A graph with a single cycle is known as a unicyclic graph.

Acyclic Graph

An acyclic graph is a graph having no graph cycles. A connected acyclic graph is known as a tree, and a disconnected acyclic graph is known as a forest.

Weighted Graph

A weighted graph is a graph in which each edge is given a numerical weight. A weighted graph is therefore a special type of labeled graph in which the labels are positive numbers.

Creation of Graph

To implement the Graph data structure, we first initialize the “Graph” class. Then, we overwrite the __init__ function and create another function to add edges between the newly added nodes.

#Initializing the Graph Class
class Graph:
    def __init__(self, gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict
    
    def addEdge(self, vertex, edge):
        self.gdict[vertex].append(edge)

Types of Graph Traversals

In Python, graph traversal refers to the process of visiting each vertex of a graph. If each vertex in a graph is to be traversed, then the algorithm must be called at least once for each connected component of the graph.

This is implemented by iterating through all the vertices of the graph, performing the algorithm on each vertex that is still unvisited when checked. Graph Traversals are classified on the basis of the order in which the nodes are visited.

There are two types of graph traversal techniques:

  • Breadth First Search (BFS) Traversal
  • Depth First Search (DFS) Traversal

Breadth First Search (BFS) Traversal

The Breadth-First Search(BFS) technique starts at some arbitrary node of a graph and checks adjacent nodes at the current level. This way, all the unvisited nodes of the same level are traversed before moving on to the next level of the graph.

Image 247

Implementation of BFS Traversal

The BFS Traversal algorithm is based on the following steps:

  • Insert any of the graph’s vertices at the back of a queue.
  • Retrieve the first item of the queue and mark it as visited.
  • Created a list of the nodes adjacent to the current node. Traverse the unvisited nodes and insert them to the back of queue.
  • Repeat the steps continuously until the queue is empty.
#Function to implement Breadth First Search Traversal 
def bfs(self, vertex):
    visited = [vertex]
    queue = [vertex]
    while queue:
        deVertex = queue.pop(0)
        print(deVertex)
        for adjacentVertex in self.gdict[deVertex]:
            if adjacentVertex not in visited:
                visited.append(adjacentVertex)
                queue.append(adjacentVertex)

customDict = { "a" : ["b","c"],
            "b" : ["a", "d", "e"],
            "c" : ["a", "e"],
            "d" : ["b", "e", "f"],
            "e" : ["d", "f", "c"],
            "f" : ["d", "e"]
               }

g = Graph(customDict)
g.bfs("a")

Output

1 20

Time and Space Complexity

The time complexity of Breadth-First Search is O(V+E) where “V” and “E” denote the number of vertices and edges respectively. The space complexity is O(V+E) as well since we need to enqueue and dequeue all the elements of the graph in our queue.

Depth First Search (DFS) Traversal

The Depth-First Search(DFS) technique starts at some arbitrary node of a graph and checks as far as possible along each edge before backtracking.

Image 248

Implementation of DFS Traversal

The DFS Traversal algorithm is based on the following steps:

  • Insert any of the graph’s vertices at the top of a stack.
  • Retrieve the top item of the stack and mark it as visited.
  • Created a list of the nodes adjacent to the current node. Traverse the unvisited nodes and insert them to the top of stack.
  • Repeat the steps continuously until the stack is empty.
#Function to implement Depth First Search Traversal 
def dfs(self, vertex):
    visited = [vertex]
    stack = [vertex]
    while stack:
        popVertex = stack.pop()
        print(popVertex)
        for adjacentVertex in self.gdict[popVertex]:
            if adjacentVertex not in visited:
                visited.append(adjacentVertex)
                stack.append(adjacentVertex)
    
customDict = { "a" : ["b","c"],
            "b" : ["a", "d", "e"],
            "c" : ["a", "e"],
            "d" : ["b", "e", "f"],
            "e" : ["d", "f", "c"],
            "f" : ["d", "e"]
               }

g = Graph(customDict)
g.dfs("a")

Output

1 21

Time and Space Complexity

The time complexity of Depth-First Search is O(V+E) where “V” and “E” denote the number of vertices and edges respectively. The space complexity is O(V+E) as well since we need to enqueue and dequeue all the elements of the graph in our queue.