The CSU Fullerton Computer Science Undergraduate Handbook includes a graph showi
ID: 3832785 • Letter: T
Question
The CSU Fullerton Computer Science Undergraduate Handbook includes a graph showing the prerequisite relationship between courses on Page 14 (http://www.fullerton.edu/ecs/cs/_resources/pdf/CPSC_undergraduate_handbook.pdf).
List the vertexes in the order of a Depth First Search starting from “Start”
List the vertexes in the order of a Breadth First Search starting from “Start”
Which traversal, DFS or BFS, more closely matches taking the courses in order of their prerequisites?
Make the following changes before your traversal
-Treat every edge as undirected
-Ignore dashed lines with arrows
-Ignore vertexes shown as dotted circles (Math 125)
Explanation / Answer
Since you have asked to ignore the direction of the edges, now there will be loops in the graph. Hence I would just print the unidirectional DFS and BFS paths and ignore the circular loops.
List of the vertices in the order of DFS (depth first search) starting from "Start" are:
1. Start; 150A; 150B; 33B; 481
2. Start; 120; 121; 131; 223
3. Start; 120; 121; 131; 254; 351; 471
4. Start; 120; 121; 131; 301; 323
5. Start; 120; 121; 131; 301; 335; 481
List of the vertices in the order of BFS (Breadth first search) starting from "Start" are:
1. Start; 150A; 120; 270A; G.E A2; 150B; 121; 270B; 33B; 131; 223; 254; 301; 240; 311; 481; 351; 323; 335; 440; 315; 362; 471
Since the dependency of the subjects shown in the book is in the manner of
A->B->C->D; B->D
DFS is more relavant to show the sequence of the subjects to be taken as per the guidelines mentioned.
In fact to approach such type of problems, the solution is to use topological sort to create a sequence of subjects to make sure that all the subjects which are a pre-requisite to take a certain subject 's' are taken before s is opted for.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.