1. Given a graph represented by an array of linked lists (refer to the ppt discu
ID: 3744384 • Letter: 1
Question
1. Given a graph represented by an array of linked lists (refer to the ppt discussed in class today), write an algorithm (pseudo code) to determine if the graph is connected 2. A century after Euler's discovery, another famous puzzle-this one invented by the renowned Irish mathematician Sir William Hamilton (1805-1865)- was presented to the world under the name of the Icosian Game. The game's board was a circular wooden board on which the following graph was carved. As a first step to finding a Hamiltonian circuit-a path that visits all the graph's vertices exactly once before returning to the starting vertex- for this graph, we must transform the game board into a graph representation Two suggestions were presented in class for the above: (1) each corner represents a vertex, (2) each space contained between the lines represents a vertex. Discuss the merits of each of the two suggestions and select the one that is advantageous in your analysisExplanation / Answer
If you post more than 1 question, as per chegg guidelines I have to sovle only first question.
Ques 1.
// do BFS on the given graph
// G is the list containing the graph
// is the the index of current node
Function BreadthFirstSearch(G , i)
BEGIN
// mark that the I th node is visited
G[i].visited = true
q = create a new queue
while q is not empty
BEGIN
// get the element at the front of queue
curr = q.front()
// remove the element at the front of queue
q.pop()
// point trav to the first element of the
// list of the current node
trav = G[ curr ]
while trav != NULL
BEGIN
G[ trav ].visited = true
q.enqueue( trav )
END
END
END
Function transpose(G)
BEGIN
Trans = create a new graph to store the transpose
For i = 1 to G.length
BEGIN
// add the current node
Trans[ i ].add( i )
END
END
Function isConnected(G)
BEGIN
For i = 1 to G.V
BEGIN
G[i].visited = true
END
BreadthFirstSearch( G , 0 )
For i = 1 to G.V
BEGIN
// if it is not connected
If G[i].visited = false
BEGIN
Return false
END
END
// get the transpose
Trans = transpose(G)
For i = 1 to G.V
BEGIN
G[i].visited = false
END
BreadthFirstSearch(Trans)
For i = 1 to G.V
BEGIN
// if it is not connected
If G[i].visited = false
BEGIN
Return false
END
END
Return true
END
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.