My homework problem presents some courses and how many depend on each other. For an instance, the first test (courses,depedent on): (1,3) (2,3) (4,1) (4,2) and we identify that there are 5 courses and 4 dependent on each other (Thats why 5 is not on the list, its just 0)
I know from a topological search, that the following is a valid solution: 1 3 2 4 0
I then need to print the number of semesters it takes to take these courses and I know it is 3 semester, due to the relations between them. We first have to take course 1 and 2 to take 3 and since we already have 1 2, we can take course 4.
So I need help figuring some code out that does this. That's where I need you guys help
I've tried to simply count the courses that are connected, but failed. I've tried to think of something that I can do but literally nothing pops up as a solution.
The graph class:
public class Graph {
int V;
LinkedList<Integer> adjList[];
public Graph(int vertex) {
this.V = vertex;
//We then define the num of vertexes in the adjlist
adjList = new LinkedList[vertex];
//Then create a new list for each vertex so we can create a link between the vertexes
for (int i = 0; i < vertex; i++) {
adjList[i] = new LinkedList<>();
}
}
//Directed graph
public void addEdge(int source, int destination) {
//Add the edge from the source node to the destination node
adjList[source].add(destination);
adjList[destination].add(source);
}
//Method to print the graph if necessary
public void printGraph(Graph graph) {
for (int i = 0; i < graph.V; i++) {
System.out.println("Adjacency list over vertex: " + i);
System.out.print("head");
for (Integer treeCrawler : graph.adjList[i]) {
System.out.print("-> " + treeCrawler);
}
System.out.println("\n");
}
}
public LinkedList<Integer>[] getAdjList() {
return adjList;
}
}
and the topological sort class, the algorithm we are using for the problem
public class TopologicalSort {
int vertex;
//This function helps the topological function recursively by marking the vertices and pushing them onto the stack
public void topologicalHelper(int vertex, boolean marked[], Stack nodes, Graph graph) {
List<Integer>[] list = graph.getAdjList();
marked[vertex] = true;
Iterator<Integer> iterator = list[vertex].iterator();
while (iterator.hasNext()) {
int temp = iterator.next();
if (!marked[temp] && list[temp].size() != 0) {
topologicalHelper(temp, marked, nodes, graph);
}
}
nodes.add(vertex);
}
public TopologicalSort(Graph graph, int vertecies) {
vertex = vertecies;
Stack nodes = new Stack();
boolean[] marked = new boolean[vertex];
for (int i = 0; i < vertex; i++) {
if (marked[i] == false) {
topologicalHelper(i, marked, nodes, graph);
}
}
while(!nodes.empty()) {
System.out.print(nodes.pop() + " ");
}
}
}
The result should be 3, but I haven't produced that number in all my solution ideas, I need some help or hints.
Oh and the following is the console output
Adjacency list over vertex: 0
head
Adjacency list over vertex: 1
head-> 3-> 4
Adjacency list over vertex: 2
head-> 3-> 4
Adjacency list over vertex: 3
head-> 1-> 2
Adjacency list over vertex: 4
head-> 1-> 2
1 3 2 4 0
Dependency is a directed property so you should be using a directed graph. After populating the graph u will end up with a disconnected graph which has one or more trees in it. Find out which nodes are roots of each tree and use DFS to get the max depth of each tree. Assuming there is no limit on no of courses for each semester the max depth of all trees is the solution.
public class Graph {
int V;
ArrayList<Integer> adjList[];
boolean[] notRoot;
public Graph(int vertex) {
this.V = vertex;
adjList = new ArrayList[vertex];
notRoot = new boolean[vertex];
for (int i = 0; i < vertex; i++) {
adjList[i] = new ArrayList<Integer>();
}
}
public void addEdge(int a, int b) {
//asuming b is dependent on a
adjList[b].add(a);
notRoot[a]=true;
}
int maxDepthDfs(int root){
int depth=1;
for(int i=0;i<adjList[root].size();i++){
int child=adjList[root].get(i);
depth=Math.max(maxDepthDfs(child)+1,depth);
}
return depth;
}
public int getSolution(){
int ans=0;
for(int i=0;i<V;i++){
if(!notRoot[i])
ans=Math.max(ans,maxDepthDfs(i));
}
return ans;
}
}
A topological sort is simply DFS with adding nodes into a stack,(all children of a node are added first and then root is added). In Kahn's algorithm first the root elements(nodes without parent) are found and the method is called only or those nodes.
int maxDepthDfs(int root){
//since we are only calling this function for root nodes we need not check if nodes were previously visited
int depth=1;
for(int i=0;i<adjList[root].size();i++){
int child=adjList[root].get(i);
depth=Math.max(maxDepthDfs(child)+1,depth);
}
s.push(root);
return depth;
}
public int getSolution(){
s=new Stack<Integer>();
int ans=0;
for(int i=0;i<V;i++){
if(!notRoot[i])
ans=Math.max(ans,maxDepthDfs(i));
}
//stack s contains result of topological sort;
return ans;
}