Hej! Jag har fått en uppgift som jag måste lösa och känner mig helt vilse då det är första gången jag jobbar med grafer! Programmet ska göra en implementation
av en oriktad graf och implementera en funktion som, med hjälp av Prims
algoritm, returnerar ett minimalt spännande träd.
Jag har börjat och behöver fylla i nedanstående metoder:
public class Graph <Generell extends Comparable<? super Generell>> implements GraphInterface {
public void addNode(Node n) {
Method for adding a node to the graph.
@param n The node to add to the graph.
}
public void connectNodes(Node n1, Node n2, int weight) {
Method for creating an undirected arc between two nodes.
@param n1 The first node to create an arc to
@param n2 The second node to create an arc to
@param weight The weight for traversing the arc
}
public boolean contains(Node n) {
return false;
Method for searching the graph for a certain node.
If the node is present in the graph, the method returns
true, otherwise, it returns false.
@return boolean telling if the node is present or not.
}
public void disconnectNodes(Node fromNode, Node toNode) {
Method for removing the arc between two nodes.
@param n1 The first node that identifies the arc.
@param n2 The second node that identifies the arc.
}
public Graph generateMinimumSpanningTree() {
return null;
Method for calculating a minimum spanning tree for the graph.
The method is supposed to returning a String representing the
minimum spanning tree. The method is not allowed to modify the graph during the calculation, ie. the graph after the method has returned must be identical to how the graph looked before the invocation of the method.
@return Graph A new instance of the Graph class, representing a
minimal spanning tree.
}
public void removeNode(Node n) {
Method for removing a node from the graph.
Before the node is removed, all arcs associated with the node
must be removed.
}
public int size() {
return 0;
Method for finding the number of nodes in the graph.
@returns int The number of nodes in the graph.
}
}
Evigt tacksam för all hjälp jag kan få, som sagt känner mig helt vilse!