Printable View
I am just two java exercises away to pass the class, but I am stuck and I can't figure it out how to do them.
I would pay someone to help me because I am really desperate. PayPal or any method available that you prefer (I don't plan in scamming anyone).
Please PM me or reply to this thread :)
I will post later the details about the exercise. I have to translate it because its in German:D
I realized that I posted in the wrong section. Maybe a mod will move it to the appropriate section of the forum.
As I promised here are the exercises.
Sorry for my bad English. I tried to do my best with the translation :)
Exercise 1 : Edgelist and Adjacency matrix
Implement an undirected, weighted graph using an edge list. The nodes of the graph are defined by the interface MyVertex and the graph itself is defined by the class Graph.
(**The following classes and interface needs to be used)
public interface MyVertex {
// Delivers a string representation of the nodes
public String toString();
}
public class Graph {
// Generating a new Graph with maximal maxVertices nodes
public Graph(int maxVertices) { … }
// Gives the number of the inserted nodes back
public int getNumberOfVertices() { … }
// Gives the size of Array getNumVertices() with all inserted nodes back
public MyVertex[] getVertices() { … }
// Insert a new node v in the graph and delivers its index in the array node
// Null elements are not allowed (IllegalArgumentException) and IndexOutOfBoundsException are thrown in this case
// Overstepping the allowed maximal nodes, will be ignored
public int insertVertex(MyVertex v)
throws IllegalArgumentException, IndexOutOfBoundsException { … }
// Delivers the weight of the edge between the Indexes v1 and v2, when they are existing
// everything else -1. In case of an unknown node index an IllegalArgumentException will be thrown
public int getEdgeWeight(int v1, int v2) throws IllegalArgumentException { … }
// Insert an undirected edge with a weight between the nodes with indexes v1
// and v2. The method delivers false when the edge already exist, otherwise true.
// In the case of an unknown node index will an IllegalArgumentException thrown
public boolean insertEdge (int v1, int v2, int weight)
throws IllegalArgumentException { … }
//Delivers and NxN Adjancency matrix for this graph, where N = getNumVertices().
// The matrix receives the weight of the edge (>=0).
public int[][] getAdjacencyMatrix() { … }
// Delivers an Array of nodes which are adjacent to the nodes with the index v
// If the node index v is unknown an IllegalArgumentException is thrown
public MyVertex[] getAdjacentVertices(int v)
throws IllegalArgumentException { … }
}
Exercise 2 : DFS
Extend the class graph to a DFS (Depth First Search) algorithm, as well as the following public methods, which use the DFS. It can be verified whether the graph is connected (isConnected), and how many components it consist (getNumerOfComponents) and whether it cycles (isCyclic).
// Delivers true when the Graph is connected, otherwise false.
public boolean isConnected() { … }
// Gives the number of the graph components back
public int getNumberOfComponents() { … }
// Gives the nodes of all components (a line for each component)
public void printComponents() { … }
// Delivers true when the graph is cyclic, otherwise false
public boolean isCyclic() { … }
Do you understand the concepts behind the code? This is not very hard to do if you understand what a "undirected, weighted graph" and a "edge list" is. Read up on these things first and google any questions you have. These are very general topics and there are tons of explainations out there(youtube, google, books)
Tasks like this are often easy to implement with recursion, assuming you know how to use recursion.
IE, the pseudo algorithm for isCyclic method
There might be errors in the codeCode:visitNode(firstNode);
boolean visitNode(firstNode){
if(isVisited){
return true
}
markNodeAsVisited()
foreach(edge){
if(visitNode(edge.node)){
return true
}
}
return false
}