Hallo, wie kann man die Knoten ein Graphen zählen?
Mehr infos?! Irgendeine Graphen-Library?
Ich soll eine methode implementieren :
public static int count(Graph anchor){
}
Jo, und wie sieht Graph aus?
In der Standard-API von Java gibt es kein Graph.
Deshalb ja auch die Fragen nach mehr Informationen. Abhängig davon wie Graph implementiert ist muss eben auch die Funktion Count erstellt werden.
Wenn er auf Papier aufgezeichnet ist, dann kann man laut zählen und bei größeren Graphen jeden bereits gezählten Knoten markieren.
Wenn das elektronisch ablaufen soll (da gehe ich mal von aus, denn du hast ja mittlerweile die Signatur der Zählmethode gepostet), dann hängt der Algorithmus davon ab, was für ein Graph es ist. Wenn der Graph nur ein Baum, dann ist das Zählen relativ einfach. Man kann einfach über dem Graphen traversieren und in einer Zählvariablen hochzählen.
Bei einem allgemeinen Graphen muss man zusätzlich noch abspeichern, welche Knoten man bereits erfasst hat.
Edit: es ist total daneben, die count-Methode statisch zu machen…
Und was soll das Zählen ausgehend von einem Knoten? Damit erhält man i.A. höchstens die Anzahl der Ecken in der Komponente.
Normalerweise ist ein Graph definiert als eine Menge von Ecken und Kanten G = (E, K). Will man wissen, wie viele Ecken er hat, gibt man die Mächtigkeit von E aus.
Um überhaupt etwas in Richtung deiner Aufgabe sagen zu können, müsste man wissen, wie der Graph denn bei dir im Programm vorgehalten wird, da gibt es verschiedene Möglichkeiten, z.B. Adjazenzlisten.
Es sieht so aus und ich glaube es ist so ein Adjazenzlisten.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;
public class GraphKnote {
private int content;
private ArrayList<GraphKnote> links;
public GraphKnote(int content) {
this.content = content;
this.links = new ArrayList<GraphKnote>();
}
public int content() {
return this.content;
}
public void addLink(GraphKnote node) {
links.add(node);
}
public GraphKnote[] links() {
GraphKnote[] links = new GraphKnote[this.links.size()];
return this.links.toArray(links);
}
public static int count(GraphKnote anchor) {
}
Poste mal die Klasse “Graph” :rolleyes:
Das ist der Code. Es gibt gibt keine Klasse Graph.
*** Edit ***
Ich hab es so probiert:
HashArray Hash = new HashArray(); // des wird nicht unterstüzt
Stack Stck = new Stack();
Stck.push(anchor);
int Sum = 0;
while (!Stck.isEmpty()){
GraphNode Node = (GraphNode)Stck.pop();
if (!Hash.Contains(Node)){
Hash.Add(Node,null);
Sum += Node.content();
int N = Node.links.Length; // links wird nicht als array gemerkt
for (int I = 0; I < N; I++)
if (Node.links** != null)
Stck.Push(Node.links**);
}
}return Sum;
Warum schreibst du Methoden und Variablen groß? Und es ist HashMap, nicht HashArray. C#-Flüchtling?
Ja du hast recht ich sollte mit kleine Buchstaben schreiben. Was wird als Zweites Argument bei Hashmap sein?
HashMap< GraphNode, ???> Hash = new HashMap<GraphNode, ???>(); //Stck?
Ach so, ich dachte du meinst ein assoziatives Array (das wäre HashMap). Willst du nur eine Menge, wäre HashSet die richtige Klasse (die hat auch nur einen Typparameter)
int N = Node.links.length; //length ist mit rot unter
for (int i = 0; i < N; i++)
if (Node.links** != null) // Node.links** mit rot unter
Stck.Push(Node.links**); // hier auch
links ist aber ein array, oder??
Dann kann die count-Methode nicht funktionieren, weil die ein Objekt vom Typ Graph erwartet.
Die Datenstruktur GraphKnote (fehlt da hinten nicht noch ein n?) kann „nur“ zusammenhängende Graphen darstellen. Mangels übergeordneter Verwaltungsebene (bspw. einer Klasse Graph) ist es nicht möglich, zwischen getrennten Teilgraphen einen Zusammenhang herzustellen.
Beim Stack sollte man den Typparameter verwenden, dann ist der Typecast aus Zeile 7 überflüssig. Außerdem gibt es mehr Codesicherheit, weil der Compiler bereits weiß, ob der Code so funktionieren kann.
Der Algorithmus kommt mir etwas merkwürdig vor. Abgesehen davon, dass dort noch viele syntaktische Fehler drin stecken, summiert er die Werte, die in den Knoten gespeichert sind auf, statt die Anzahl der Knoten zu zählen.
Mir stellt sich auch noch die Frage, weshalb die Links intern zwar als Liste gespeichert werden, sie aber nach außen als Array gegeben werden.
*** Edit ***
Nein, links ist eine Liste, die aber nicht direkt zugreifbar ist (private). Der Zugriff erfolgt über den getter links() (mit Klammern!). Dort wird dann aus der Liste ein Array gemacht.
hmm, wo ist die Rede von Teilgraphen?
die Sache lieber nicht unnötig komplizierter machen als sie sowieso schon ist,
ein ‚Knote‘ verweist auf x andere, die wieder auf andere, das kann man wahrscheinlich schon alles zählen
der bisher gepostete Code ist ja erfreulich ausführlich, wenn es auch an Syntax und Java-Klassen hapert,
die Grundidee ist aber richtig:
alle Knoten aus den Links holen und nach und nach abarbeiten, merken welche schon besucht,
jene nicht neu zählen und schon gar nicht deren Nachbarn nochmal durchgehen, sonst läuft es ja bis in alle Ewigkeit,
nur jeweils neue Knoten und natürlich auch deren Links betrachten
an Code dafür kann man ruhig eine Weile knobeln, wenn noch nicht völlig aufgegeben dann gerne ‚zur Übung belassen‘ 
die Idee ja schon durchaus eben richtig verfolgt
ideal ist dabei immer ein gut aufgebautes Beispiel und System.out.println()-Log nebenher um nachzuvollziehen, was der Algorithmus macht,
wo vielleicht zu viel gezählt, wo Nachbarn übersehen usw.,
nur am Editor kommt man kaum zur finalen Lösung, besser auch immer den Code laufen lassen, Fehler anschauen usw.
jemand könnte vielleicht auch die Lösung posten,
aber mit jeder weiteren Aufgabe wird dein Fehlen jeglicher Programmierkenntnisse umso erdrückender,
besser selber dran arbeiten, falls du darauf Wert legst
was Methoden sind, wie mit HashSet zu arbeiten usw., das kann man ja alles nebenher nachschlagen,
viel natürlich, aber führt kein Weg dran vorbei
Mal aus dem Handgelenk, ohne Gewähr…
public static int count(GraphKnote anchor) {
Set<GraphKnote> set = new HashSet<GraphKnote>();
List<GraphKnote> toDo = new ArrayList<GraphKnote>();
toDo.add(anchor);
while(! toDo.isEmpty()) {
GraphKnote current = toDo.remove(0);
if (! set.contains(current)) {
set.add(current);
toDo.addAll(current.links);
}
}
//jetzt sind alle erreichbaren Knoten im Set
//mach was damit...
}
Und “GraphKnote” ist ein furchtbarer Name, warum nicht einfach “Node”?
Danke Landei!!