2. Graph representation using Adjacency List

Graph Representation using Adjacency List¶

Graph¶

Graph

0---1
|  /
| /
|/
2---3

Expected Adjacency List

=> [0, 1, 2, 3, 4]

        |
        |
        V


0[] -> [1 | ] -> [2 | ]
1[] -> [0 | ] -> [2 | ]
2[] -> [0 | ] -> [1 | ] -> [3 | ]
3[] -> [2 | ]

In [1]:

from utils.nodes import SinglyLinkedListNode as Node

from utils.nodes import SinglyLinkedListNode as Node

In [2]:

class Graph:
    def __init__(self, vertices) -> None:
        self.vertices = vertices
        self.list = [None] * self.vertices

    def add_node(self, idx, data):
        node = Node(data)
        if self.list[idx] is None:
            self.list[idx] = node
        else:
            ptr = self.list[idx]
            while ptr.next is not None:
                ptr = ptr.next

            ptr.next = node

    def traverse(self):

        for i in range(len(self.list)):
            done = False
            ptr = self.list[i]
            while ptr is not None:
                if not done:
                    print(f"[{i}] -> ", end="")
                    done = True
                print(f"[{ptr.data} | ] ", end="")
                if ptr.next is not None:
                    print("->", end="")

                ptr = ptr.next
            print()

class Graph: def __init__(self, vertices) -> None: self.vertices = vertices self.list = [None] * self.vertices def add_node(self, idx, data): node = Node(data) if self.list[idx] is None: self.list[idx] = node else: ptr = self.list[idx] while ptr.next is not None: ptr = ptr.next ptr.next = node def traverse(self): for i in range(len(self.list)): done = False ptr = self.list[i] while ptr is not None: if not done: print(f"[{i}] -> ", end="") done = True print(f"[{ptr.data} | ] ", end="") if ptr.next is not None: print("->", end="") ptr = ptr.next print()

In [3]:

graph = Graph(5)
graph.add_node(0, 1)
graph.add_node(0, 2)
graph.add_node(1, 0)
graph.add_node(1, 2)
graph.add_node(2, 0)
graph.add_node(2, 1)
graph.add_node(2, 3)
graph.add_node(3, 2)

graph = Graph(5) graph.add_node(0, 1) graph.add_node(0, 2) graph.add_node(1, 0) graph.add_node(1, 2) graph.add_node(2, 0) graph.add_node(2, 1) graph.add_node(2, 3) graph.add_node(3, 2)

In [4]:

graph.traverse()

graph.traverse()

[0] -> [1 | ] ->[2 | ] 
[1] -> [0 | ] ->[2 | ] 
[2] -> [0 | ] ->[1 | ] ->[3 | ] 
[3] -> [2 | ] 

In [ ]: