plz use python to answer it, thanks in advance
class Graph:
def _init_(self):
# dictionary containing keys that map to the corresponding vertex
object
self.vertices = {}
def add_vertex(self, key):
"""Add a vertex with the given key to the graph."""
vertex = Vertex(key)
self.vertices[key] = vertex
def get_vertex(self, key):
"""Return vertex object with the corresponding key."""
return self.vertices[key]
def _contains_(self, key):
return key in self.vertices
def add_edge(self, src_key, dest_key, weight=1):
"""Add edge from src_key to dest_key with given weight."""
self.vertices[src_key].add_neighbour(self.vertices[dest_key],
weight)
def does_edge_exist(self, src_key, dest_key):
"""Return True if there is an edge from src_key to
dest_key."""
return
self.vertices[src_key].does_it_point_to(self.vertices[dest_key])
def _iter_(self):
return iter(self.vertices.values())
class Vertex:
def _init_(self, key):
self.key = key
self.points_to = {}
def get_key(self):
"""Return key corresponding to this vertex object."""
return self.key
def add_neighbour(self, dest, weight):
"""Make this vertex point to dest with given edge weight."""
self.points_to[dest] = weight
def get_neighbours(self):
"""Return all vertices pointed to by this vertex."""
return self.points_to.keys()
def get_weight(self, dest):
"""Get weight of edge from this vertex to dest."""
return self.points_to[dest]
def does_it_point_to(self, dest):
"""Return True if this vertex points to dest."""
return dest in self.points_to
class Stack:
def _init_(self):
self.items = []
def is_empty(self):
return self.items == []
def push(self, data):
self.items.append(data)
def pop(self):
return self.items.pop()
def display_dfs(v):
visited = set()
s = Stack()
s.push(vertex)
while not s.is_empty():
current = s.pop()
if current in visited:
continue
print(current.get_key(), end=' ')
visited.add(current)
for dest in current.get_neighbours():
if dest not in visited:
s.push(dest)
g = Graph()
print('Menu')
print('add vertex <key>')
print('add edge <src> <dest>')
print('dfs <vertex key>')
print('display')
print('quit')
while True:
do = input('What would you like to do? ').split()
operation = do[0]
if operation == 'add':
suboperation = do[1]
if suboperation == 'vertex':
key = int(do[2])
if key not in g:
g.add_vertex(key)
else:
print('Vertex already exists.')
elif suboperation == 'edge':
src = int(do[2])
dest = int(do[3])
if src not in g:
print('Vertex {} does not exist.'.format(src))
elif dest not in g:
print('Vertex {} does not exist.'.format(dest))
else:
if not g.does_edge_exist(src, dest):
g.add_edge(src, dest)
else:
print('Edge already exists.')
elif operation == 'dfs':
key = int(do[1])
print('Depth-first Traversal: ', end='')
vertex = g.get_vertex(key)
display_dfs(vertex)
print()
elif operation == 'display':
print('Vertices: ', end='')
for v in g:
print(v.get_key(), end=' ')
print()
print('Edges: ')
for v in g:
for dest in v.get_neighbours():
w = v.get_weight(dest)
print('(src={}, dest={}, weight={}) '.format(v.get_key(),
dest.get_key(), w))
print()
elif operation == 'quit':
break
plz use python to answer it, thanks in advance 3. Tree and back arcs in a DFS 40 Marks For a given set of digraphs, write a program that performs DFS on each digraph starting at node 0 and prints...
Reverse of a digraph 30 Marks For a given set of digraphs, write a program that prints out the reverse of each digraph. Input format: described below under the heading “Digraph input format”. Note that adjacency lists are sorted. Output format: use the input format to output your result ensuring that the output adjacency lists are sorted. the input format: 4 1. 3 2. 3 0 3 1. 2 1 0 2. Reverse of a digraph 30 Marks For a...
For the following questions, use the graph (starting node: S) below: 14. Show DFS traversal. 15. Show BFS traversal. 16. Show the result of a topological sorting of the graph 17. Dijikstra's single source shortest paths for all nodes 18. Show a tabular form soultion of following 0/1 knapsack problem. Value {5,7, 3, 10, 12, 4, 10} Weight {2,3,1,5, 6, 2,4} Total Weight: 12 19. Show a solution to Fractional knapsack problem with the same weight, value, and total weight...
[Python] Construct Tree Using Inorder and Preorder Given Preorder and Inorder traversal of a binary tree, create the binary tree associated with the traversals.You just need to construct the tree and return the root. Note: Assume binary tree contains only unique elements. Input format : Line 1 : n (Total number of nodes in binary tree) Line 2 : Pre order traversal Line 3 : Inorder Traversal Output Format : Elements are printed level wise, each level in new line...
Please write the complete code in C. Write a C function that prints the minimum spanning tree of a graph. At the end, print the weight of the spanning tree. A suggested report format is shown in the following example. Source Vertex To Vertex Weight A B 2 A C 4 B D 3 D E 1 Total weight of spanning tree: 10 Your main program will read a graph from DataIn file to an adjacency table before calling the...
Write a C++ program called ts.cpp that implements the topological sorting algorithm based on the DFS algorithm. Your program should read an input file name and determine if the input graph is a DAG (= directed acyclic graph) or not. If the graph is not a DAG, your program has to stop without further processing. However, if it’s a DAG, your program should display the starting node(s), popping-off order, and topologically sorted list. In the problem, you can assume that...
You will be implementing a Breadth-First Search (BFS) and a Depth-First Search (DFS) algorithm on a graph stored as an adjacency list. The AdjacencyList class inherits from the Graph class shown below. class Graph { private: vector _distances; vector _previous; public: Graph() { } virtual int vertices() const = 0; virtual int edges() const = 0; virtual int distance(int) const = 0; virtual void bfs(int) const = 0; virtual void dfs(int) const = 0; virtual void display() const = 0;...
Code to be written in C++: Initially, you will be given symbols printed in a preorder traversal of a boolean expression tree. The internal nodes of the tree will contain one of the following operators: & (and), | (or), ^ (exclusive-or), or ! (not). The nodes containing the first three operators will have two children, while the nodes containing the ! operator will contain only a left child. The leaves of the tree will contain an operand - either f...
You are given a set of ABC cubes for kids (like the one shown below) and a word. On each side of each cube a letter is written 7 FI 0 You need to find out, whether it it possible to form a given word by the cubes For example, suppose that you have 5 cubes: B1: MXTUAS B2:OQATGE ВЗ: REwMNA B4: MBDFAC В5: IJKGDE (here for each cube the list of letters written on its sides is given) You...
Introduction In this lab, you are supposed to implement a graph class with the data structure implemented before like linked list and queue. graph The class graph contains three member variables: linkedList *adjacentVertices; //an array of linked list. For a vertice i, adjacentVertices[i] stores the linked list that contains all other vertices connected to vertice i. int numVertices; //The number of vertices in the graph. int maxNumVertices; //The maximum number of vertices the graph can hold. Following public methods are...
Edit a C program based on the surface code(which is after the question's instruction.) that will implement a customer waiting list that might be used by a restaurant. Use the base code to finish the project. When people want to be seated in the restaurant, they give their name and group size to the host/hostess and then wait until those in front of them have been seated. The program must use a linked list to implement the queue-like data structure....