How to implement a graph in Python
A graph is a data structure that consists of vertices that are connected via edges. It can be implemented with an:
1. Adjacency list
For every vertex, its adjacent vertices are stored. In the case of a weighted graph, the edge weights are stored along with the vertices.
2. Adjacency matrix
The row and column indices represent the vertices: means that there is an edge from vertices to , and denotes that there is no edge between and . For a weighted graph,the edge weight is usually written in place of .
Implementation
1. Using an adjacency list
The following code implements a graph using an adjacency list: add_vertex(v) adds new vertex v to the graph, and add_edge(v1, v2, e) adds an edge with weight e between vertices v1 and v2.
# Add a vertex to the dictionarydef add_vertex(v):global graphglobal vertices_noif v in graph:print("Vertex ", v, " already exists.")else:vertices_no = vertices_no + 1graph[v] = []# Add an edge between vertex v1 and v2 with edge weight edef add_edge(v1, v2, e):global graph# Check if vertex v1 is a valid vertexif v1 not in graph:print("Vertex ", v1, " does not exist.")# Check if vertex v2 is a valid vertexelif v2 not in graph:print("Vertex ", v2, " does not exist.")else:# Since this code is not restricted to a directed or# an undirected graph, an edge between v1 v2 does not# imply that an edge exists between v2 and v1temp = [v2, e]graph[v1].append(temp)# Print the graphdef print_graph():global graphfor vertex in graph:for edges in graph[vertex]:print(vertex, " -> ", edges[0], " edge weight: ", edges[1])# driver codegraph = {}# stores the number of vertices in the graphvertices_no = 0add_vertex(1)add_vertex(2)add_vertex(3)add_vertex(4)# Add the edges between the vertices by specifying# the from and to vertex along with the edge weights.add_edge(1, 2, 1)add_edge(1, 3, 1)add_edge(2, 3, 3)add_edge(3, 4, 4)add_edge(4, 1, 5)print_graph()# Reminder: the second element of each list inside the dictionary# denotes the edge weight.print ("Internal representation: ", graph)
2. Using an adjacency matrix
The following code implements a graph using an adjacency matrix: add_vertex(v) adds new vertex v to the graph, and add_edge(v1, v2, e) adds an edge with weight e between vertices v1 and v2.
# Add a vertex to the set of vertices and the graphdef add_vertex(v):global graphglobal vertices_noglobal verticesif v in vertices:print("Vertex ", v, " already exists")else:vertices_no = vertices_no + 1vertices.append(v)if vertices_no > 1:for vertex in graph:vertex.append(0)temp = []for i in range(vertices_no):temp.append(0)graph.append(temp)# Add an edge between vertex v1 and v2 with edge weight edef add_edge(v1, v2, e):global graphglobal vertices_noglobal vertices# Check if vertex v1 is a valid vertexif v1 not in vertices:print("Vertex ", v1, " does not exist.")# Check if vertex v1 is a valid vertexelif v2 not in vertices:print("Vertex ", v2, " does not exist.")# Since this code is not restricted to a directed or# an undirected graph, an edge between v1 v2 does not# imply that an edge exists between v2 and v1else:index1 = vertices.index(v1)index2 = vertices.index(v2)graph[index1][index2] = e# Print the graphdef print_graph():global graphglobal vertices_nofor i in range(vertices_no):for j in range(vertices_no):if graph[i][j] != 0:print(vertices[i], " -> ", vertices[j], \" edge weight: ", graph[i][j])# Driver code# stores the vertices in the graphvertices = []# stores the number of vertices in the graphvertices_no = 0graph = []# Add vertices to the graphadd_vertex(1)add_vertex(2)add_vertex(3)add_vertex(4)# Add the edges between the vertices by specifying# the from and to vertex along with the edge weights.add_edge(1, 2, 1)add_edge(1, 3, 1)add_edge(2, 3, 3)add_edge(3, 4, 4)add_edge(4, 1, 5)print_graph()print("Internal representation: ", graph)
RELATED TAGS
