How to implement a graph in Python
Educative Answers TeamA 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 dictionary
def add_vertex(v):
global graph
global vertices_no
if v in graph:
print("Vertex ", v, " already exists.")
else:
vertices_no = vertices_no + 1
graph[v] = []
# Add an edge between vertex v1 and v2 with edge weight e
def add_edge(v1, v2, e):
global graph
# Check if vertex v1 is a valid vertex
if v1 not in graph:
print("Vertex ", v1, " does not exist.")
# Check if vertex v2 is a valid vertex
elif 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 v1
temp = [v2, e]
graph[v1].append(temp)
# Print the graph
def print_graph():
global graph
for vertex in graph:
for edges in graph[vertex]:
print(vertex, " -> ", edges[0], " edge weight: ", edges[1])
# driver code
graph = {}
# stores the number of vertices in the graph
vertices_no = 0
add_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 graph
def add_vertex(v):
global graph
global vertices_no
global vertices
if v in vertices:
print("Vertex ", v, " already exists")
else:
vertices_no = vertices_no + 1
vertices.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 e
def add_edge(v1, v2, e):
global graph
global vertices_no
global vertices
# Check if vertex v1 is a valid vertex
if v1 not in vertices:
print("Vertex ", v1, " does not exist.")
# Check if vertex v1 is a valid vertex
elif 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 v1
else:
index1 = vertices.index(v1)
index2 = vertices.index(v2)
graph[index1][index2] = e
# Print the graph
def print_graph():
global graph
global vertices_no
for 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 graph
vertices = []
# stores the number of vertices in the graph
vertices_no = 0
graph = []
# Add vertices to the graph
add_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
View all Courses
