I need help solving this problem. Any help doing this is greatly appreciated. I

Question

I need help solving this problem. Any help doing this is greatly appreciated. I will rate as soon as possible. Thanks.

Consider the following adjacency matrix for an unweighted directed graph G (blank entries mean no edge): A breadth-first .search starting from vertex 6 will visit vertices in G in some sequence. In fact, several distinct sequences are possible in this case. Show four of them: (In this problem keys are characters, with alphabetic ordering; priorities are integers, with larger integers representing higher priority.)

Explanation / Answer

for x in xrange(0, numGraphs): numVerts = input() numEdges = input() adjMat = [[0 for x in xrange(numVerts)] for x in xrange(numVerts)] for x in xrange(0, numEdges): edges = raw_input() i, padding, j = edges.rpartition(" ") i = int(i) j = int(j) i -= 1 j -= 1 adjMat[i][j] = 1 numPaths = [0 for x in xrange(numVerts)] numPaths[0] = 1 currentPath = [0 for x in xrange(numVerts)] maxPath = 1 minPath = numVerts -1 for i in xrange(0, numVerts): for j in xrange(1, numVerts): if adjMat[i][j] == 1: numPaths[j] += numPaths[i] currentPath[j-i] += 1 if (currentPath[j-i] is not 0): minPath = currentPath[j-i] maxPath = max(currentPath) print "shortest: %d, longest: %d, total %d" % (minPath, maxPath, numPaths[numVerts-1]

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.