Girth of a digraph For a digraph G, the length of the shortest cycle is called t
ID: 3754320 • Letter: G
Question
Girth of a digraph For a digraph G, the length of the shortest cycle is called the directed girth of the graph If the digraph has no cycle then the girth is undefined, and we will say it has girth 0. Your task is to determine the directed girth of each input digraph Input Format Input for this problem consists of a sequence of one or more digraphs taken from the keyboard (System.in). Each graph is represented by an adjacency list. The first line is an integer n indicating the order of the graph. This is followed by n white space separated lists of adjacencies for nodes labeled 0 ton - 1. The input will be terminated by a line consisting of one zero (0). This line should not be processed. Two sample input digraphs are listed below. The test cases are digraphs of order at most 30. 4 1 3 2 3 0 3 1 2 0 OutputFormat Output will be just one integer per line sent to the console (e.g. System.out). For the above, input we would output the following two integers denoting the girth of the two graphs, using 0 to indicate the graph has no cycle. 3 0Explanation / Answer
Solution:-
The girth of a graph is the length of the shortest cycle present in the graph.
Graph in python can be represented using dictionary of vertices and edges.
class Graph:
def __init__(self):
self.vertices = {}
def add_vertex(self, key):
vertex = Vertex(key)
self.vertices[key] = vertex
def get_vertex(self, key):
return self.vertices[key]
def __contains__(self, key):
return key in self.vertices
def add_edge(self, src_key, dest_key, weight=1):
self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)
def does_edge_exist(self, src_key, dest_key):
return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])
def __len__(self):
return len(self.vertices)
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 self.key
def add_neighbour(self, dest, weight):
self.points_to[dest] = weight
def get_neighbours(self):
return self.points_to.keys()
def get_weight(self, dest):
return self.points_to[dest]
def does_it_point_to(self, dest):
---------------------------------------End--------------------------------------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.