Question

Please provide Python 3.7 implementation of Graph ADT using in-built structure List only (not using dict).

Basic structure of graph will be:

Node = []

Edges = [ [ ] , [ ] ]

Also provide method to print the graph along with all path

Answer 1

Please note that we ave implemented ge graph in the form o adjacency lst

#graph class

class Graph:

nodes = [] #holds nodes

edges = [] #holds edges

#utility to add vertex to the nodes list

def addVertex(self, v):

self.nodes.append(v)

self.edges.append([])

#utility to add an edge into the Graph#that actually mean inserting (u,v) mean inserting v in neighbour list of u

def addEdge(self, u, v):

#fin the index o the node u in the nodes

idx = self.nodes.index(u)

#checks the validity of index

if idx in range(len(self.nodes)):

self.edges[idx].append(v)

#utility to print the graph in the adjacency list

def print(self):

for i in range(len(self.nodes)):

print("{}: ".format(self.nodes[i]), end="")

for j in range(len(self.edges[i])):

print("{}->".format(self.edges[i][j]), end="")

print()

def main():

graph = Graph()

graph.addVertex(10)

graph.addVertex(20)

graph.addVertex(30)

graph.addVertex(40)

graph.addEdge(10, 20)

graph.addEdge(10, 30)

graph.addEdge(20, 40)

graph.addEdge(40, 20)

graph.addEdge(20, 30)

graph.addEdge(40, 10)

graph.print()

if __name__ == main():

main()