a shot of dev knowledge

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

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)

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 COURSES

View all Courses

Related Courses

Related Courses

View all Courses

Keep Exploring

Related Courses