Graphs Data Structure in Python

1. Use the Adjacency List to Implement Graphs in Python
2. Use the Adjacency Matrix to Implement Graphs in Python

In Programming, the graph data structure represents a set of interlinked objects. Every object is called the vertex, and the link is termed as edge.

In the above figure, {A, B, C, D, E} are the vertices, and the set is represented using the V symbol. The set of edges is represented using E and in the above example it is {ad,ac,ab,cd,bd,be,de}.

We can categorize graphs based on different criteria. First, we have graphs based on direction.

These are the undirected and directed graphs. In an undirected graph, edges have no direction.

This means the edge ab is the same as ba. The opposite is true for directed graphs where every edge has direction or orientation.

Based on weights, we have weighted and non-weighted graphs. Weighted graphs have some value associated with the edges.

There are also special graphs like trees, directed acyclic graphs, and more. Due to their non-linear nature, graphs have a lot of real-world applications.

Google maps use graphs for their transportation systems, and even Facebook uses graphs to visualize a user and its friend list.

In this tutorial, we will discuss representing a simple graph in Python.

Use the Adjacency List to Implement Graphs in Python

An adjacency list stores every vertex and its adjacent vertices to visualize a graph. This can be represented using a dictionary.

Every vertex will be the dictionary’s key, and the corresponding value of the keys will contain the adjacent vertices in a list.

adjacency_lst = {}
mylst = []


def graph_node(node):
    if node not in mylst:
        mylst.append(node)
    else:
        print("The given node exists")


def graph_edge(node1, node2):
    temp = []
    if node1 in mylst and node2 in mylst:
        if node1 not in adjacency_lst:
            temp.append(node2)
            adjacency_lst[node1] = temp

        elif node1 in adjacency_lst:
            temp.extend(adjacency_lst[node1])
            temp.append(node2)
            adjacency_lst[node1] = temp

    else:
        print("The given node does not exist")


def disp_graph():
    for node in adjacency_lst:
        print(node, " -> ", [i for i in adjacency_lst[node]])


graph_node("a")
graph_node("b")
graph_node("c")
graph_node("d")
graph_edge("a", "b")
graph_edge("b", "c")
graph_edge("c", "d")
graph_edge("d", "a")
disp_graph()
print(adjacency_lst)

Output:

a  ->  ['b']
b  ->  ['c']
c  ->  ['d']
d  ->  ['a']
{'a': ['b'], 'b': ['c'], 'c': ['d'], 'd': ['a']}

We implement a simple graph using the adjacency list in the above example. At the start, the adjacency_lst dictionary is defined to store the nodes and edges.

The graph_node() function adds a vertex to this dictionary and checks if a node already exists. We add edges using the graph_edge() function.

The disp_graph() function displays this graph by displaying the nodes’ edges.

Use the Adjacency Matrix to Implement Graphs in Python

We can use a matrix to represent a graph. A matrix is a 2-Dimensional array.

In an adjacency matrix, the value at a particular row and column indicates whether an edge exists or not.

If A[i][j] is 0, then no edge between i and j. A value of 1 indicates that the edge exists.

def graph_node(v):
    global graph
    global nodes_no
    global nodes
    if v in nodes:
        print("Node already exists")
    else:
        nodes_no = nodes_no + 1
    nodes.append(v)
    if nodes_no > 1:
        for vertex in graph:
            vertex.append(0)
    temp = []
    for i in range(nodes_no):
        temp.append(0)
    graph.append(temp)


def graph_edge(v1, v2, e):
    global graph
    global nodes_no
    global nodes
    if v1 not in nodes:
        print("Node ", v1, " does not exist.")
    elif v2 not in nodes:
        print("Node ", v2, " does not exist.")
    else:
        index1 = nodes.index(v1)
        index2 = nodes.index(v2)
        graph[index1][index2] = e


def disp_graph():
    global graph
    global nodes_no
    for i in range(nodes_no):
        for j in range(nodes_no):
            if graph[i][j] != 0:
                print(nodes[i], " -> ", nodes[j], "Weight for the edge: ", graph[i][j])


nodes = []
nodes_no = 0
graph = []
graph_node(1)
graph_node(2)
graph_node(3)
graph_node(4)
graph_edge(1, 2, 1)
graph_edge(1, 3, 1)
graph_edge(2, 3, 0)
graph_edge(3, 1, 2)
disp_graph()
print("Matrix Representation: ", graph)

Output:

1  ->  2 Weight for the edge:  1
1  ->  3 Weight for the edge:  1
3  ->  1 Weight for the edge:  2
Matrix Representation:  [[0, 1, 1, 0], [0, 0, 0, 0], [2, 0, 0, 0], [0, 0, 0, 0]]

In the above example, we implement a graph using the adjacency matrix. We maintain the graph is a list of lists called graph.

The graph_node() function adds a vertex to the graph, and the edges between vertices are added.

Using the graph_edge() function. The disp_graph() displays the representation of nodes and edges from the matrix.