Data Structures
Graph

Graph

Graph (Data Structure)

Graph is a non-linear data structure that consists of a finite set of vertices (nodes) and edges (links).

Graphs are used to represent networks, social networks, maps, and many more real-world applications.

Graphs are used to model relationships between entities. A graph is a collection of nodes (vertices) and edges that connect pairs of nodes.

Types of Graphs

  1. Undirected Graph: A graph in which edges have no direction.
  2. Directed Graph: A graph in which edges have a direction.
  3. Weighted Graph: A graph in which edges have weights.
  4. Acyclic Graph: A graph that has no cycles.

Tree is undirected graph with no cycles, where each node has exactly one parent.

Representing Graph

Graphs can be represented using different data structures:

  • Adjacency Matrix: A 2D array of size V x V where V is the number of vertices.
  • Adjacency List: An array of linked lists where the size of the array is equal to the number of vertices.
#         0
#        / 
#       1 --- 2
#        \   /
#          3
 
# Adjacency Matrix representation
graph = [[0, 1, 0, 0],
         [1, 0, 1, 1],
         [0, 1, 0, 1],
         [0, 1, 1, 0]]
 
# Adjacency List representation
graph = {0: [1],
         1: [0, 2, 3],
         2: [1, 3],
         3: [1, 2]}

Operations

  1. Add Vertex: Add a new vertex to the graph.
  2. Add Edge: Add an edge between two vertices.
  3. Remove Vertex: Remove a vertex from the graph.
  4. Remove Edge: Remove an edge between two vertices.
  5. Traverse: Visit all vertices in a specific order.

Example

class Graph:
    def __init__(self):
        self.graph = {}
 
    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = [v]
        else:
            self.graph[u].append(v)
 
    def print_graph(self):
        for node in self.graph:
            print(node, "->", " -> ".join(map(str, self.graph[node])))
 
# Create a graph
g = Graph()
 
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 0)
 
g.print_graph()

Traversing a Graph

There are two common ways to traverse a graph:

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

Depth First Search (DFS) is a recursive traversal strategy in which we start from a node and then traverse the graph as far as possible along each branch before backtracking. At each step, we visit an adjacent node that we have not visited before.

Breadth First Search (BFS) is a traversal strategy that explores all neighbor nodes at the present depth level before moving on to the nodes at the next depth level. We achieve this by maintaining a queue of the edges connected to the node that we are visiting. We then pickup the next vertex to visit from the queue.

class Graph:
    def __init__(self):
        self.graph = {}
 
    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = [v]
        else:
            self.graph[u].append(v)
 
    def dfs(self, node, visited):
        visited.add(node)
        print(node, end=" ")
 
        if node not in self.graph:
            return
 
        for neighbor in self.graph[node]:
            if neighbor not in visited:
                self.dfs(neighbor, visited)
 
    def bfs(self, start):
        visited = set()
        queue = [start]
        visited.add(start)
 
        while queue:
            node = queue.pop(0)
            print(node, end=" ")
 
            if node not in self.graph:
                continue
 
            for neighbor in self.graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
                    visited.add(neighbor)
 
 
# Create a graph
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(3, 5)
g.add_edge(4, 5)
 
print("Breadth-First Search starting from node 0:")
g.bfs(0)
 
print("Depth-First Search starting from node 0:")
g.dfs(0, set())
Binary TreeIndexes