# 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:

For every vertex, its adjacent vertices are stored. In the case of a weighted graph, the edge weights are stored along with the vertices. ​

The row and column indices represent the vertices: $matrix[i][j] = 1$ means that there is an edge from vertices $i$ to $j$, and $matrix[i][j] = 0$ denotes that there is no edge between $i$ and $j$. For a weighted graph,the edge weight is usually written in place of $1$.

A graph and its representations in Python

### 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
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
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, " edge weight: ", edges)

# driver code
graph = {}
# stores the number of vertices in the graph
vertices_no = 0
# Add the edges between the vertices by specifying
# the from and to vertex along with the edge weights.
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
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
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
print("Internal representation: ", graph)