Graph Data Structure Implementation (Python)

How to store a graph?

1
2
3
4
5
6
# Example Graph:
#   0---1---2
#   |       |
#   3---4---5
#   |   |
#   6---7---8---9

Adjacency List

1
2
3
4
5
6
7
8
9
10
11
12
graph1 = {
    0: [1, 3],
    1: [0, 2, 4],
    2: [1, 5],
    3: [0, 4, 6],
    4: [1, 3, 5, 7],
    5: [2, 4],
    6: [3, 7],
    7: [4, 6, 8],
    8: [7, 9],
    9: [8]
}

Adjacency Matrix

1
2
3
4
5
6
7
8
9
10
11
12
graph2 = [
    [0, 1, 0, 1, 0, 0, 0, 0, 0, 0], # 0
    [1, 0, 1, 0, 1, 0, 0, 0, 0, 0], # 1
    [0, 1, 0, 0, 0, 1, 0, 0, 0, 0], # 2
    [1, 0, 0, 0, 1, 0, 1, 0, 0, 0], # 3
    [0, 1, 0, 1, 0, 1, 0, 1, 0, 0], # 4
    [0, 0, 1, 0, 1, 0, 0, 0, 0, 0], # 5
    [0, 0, 0, 1, 0, 0, 0, 1, 0, 0], # 6
    [0, 0, 0, 0, 1, 0, 1, 0, 1, 0], # 7
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 1], # 8
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]  # 9
]

Edge List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
graph3 = [
    [0, 1], # 0
    [0, 3], # 1
    [1, 2], # 2
    [1, 4], # 3
    [2, 5], # 4
    [3, 4], # 5
    [3, 6], # 6
    [4, 5], # 7
    [4, 7], # 8
    [5, 8], # 9
    [6, 7], # 10
    [7, 8], # 11
    [7, 9], # 12
    [8, 9]  # 13
]

Cross linked list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

    def add_edge(self, src, dest):
        node = Node(dest)
        node.next = self.graph[src]
        self.graph[src] = node

        node = Node(src)
        node.next = self.graph[dest]
        self.graph[dest] = node

    def print_graph(self):
        for i in range(self.vertices):
            print("Adjacency list of vertex {}\n head".format(i), end="")
            temp = self.graph[i]
            while temp:
                print(" -> {}".format(temp.data), end="")
                temp = temp.next
            print(" \n")

graph4 = Graph(10)
graph4.add_edge(0, 1)
graph4.add_edge(0, 3)
graph4.add_edge(1, 2)
graph4.add_edge(1, 4)
graph4.add_edge(2, 5)
graph4.add_edge(3, 4)
graph4.add_edge(3, 6)
graph4.add_edge(4, 5)
graph4.add_edge(4, 7)
graph4.add_edge(5, 8)
graph4.add_edge(6, 7)
graph4.add_edge(7, 8)
graph4.add_edge(7, 9)
graph4.add_edge(8, 9)
# graph4.print_graph()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Example
v = 4

# Adjacency List
for neighbor in graph1[v]:
    print(neighbor)

# Adjacency Matrix
for neighbor in range(len(graph2[v])):
    if graph2[v][neighbor] == 1:
        print(neighbor)

# Edge List
for edge in graph3:
    if edge[0] == v:
        print(edge[1])
    elif edge[1] == v:
        print(edge[0])

# Cross linked list
temp = graph4.graph[v]
while temp:
    print(temp.data)
    temp = temp.next