This week's book giveaway is in the Kotlin forum.We're giving away four copies of Kotlin in Action and have Dmitry Jemerov & Svetlana Isakova on-line!See this thread for details.
Win a copy of Kotlin in Action this week in the Kotlin forum!
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# How to implement topological search on a graph of quest nodes?

Tom Daly
Greenhorn
Posts: 1
Hello, I am trying to implement topological sort for a quest prerequisite method i am try to write from the algorithm below and am having trouble implementing the last parts of the algorithm. I'm not sure how to implement it and the language in the pseudo code language is confusing me as to what i need to write. I will include the pseudocode and what i have so far, if any one can help me figure out how to finish the method that would be great as I am stuck on how to finish the method. Thanks!

pseudocode:

my code:

Knute Snortum
Sheriff
Posts: 4073
112
Welcome to the Ranch!  Here are a few things I see with this code:

Your pseudo code is ambiguous because there are no END WHILEs or END FORs in it.  Is the FOR loop inside the WHILE loop or not?

Don't write if (condition == true), just write if (condition) {

The variable names are poorly chosen.  Avoid signle-letter names except for temporary variables that are used within about three lines.  Choose names that mean something.

For the pseudo code:
while H is non - empty do remove a quest n from H
I would use an enhanced for loop:

That's a start.

Piet Souris
Rancher
Posts: 1979
67
hi Tom,

welcome to the ranch!

A slight problem is that I do not know the classes that you have in your code. So, suppose we have the vertices 0, 1, ..., N-1 and we have an adjacency matrix adj[N][N].

The algorithm is then:

for every vertex I, if column I of the adjacency matrix contains only zero's, put I into H.

If H is empty, then we have an invalid graph.

Next:

The whole of the adjacency matrix should now contain only zero's.

You will have to translate this simple scheme to the classes that you have.