Graph: countEdges Wie unterscheiden zwischen gerichtetem und ingerichtetem Graphen?

Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Vykyfikation
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 9. Mai 2017 12:44

Graph: countEdges Wie unterscheiden zwischen gerichtetem und ingerichtetem Graphen?

Beitrag von Vykyfikation » 25. Jun 2017 13:08

Hallo, ich kamm grade nicht darauf, wie ich bei der Methode countEdgesRec zwischen gerichtetem und ungerichtetem graphen unterscheiden soll.
ich bekomm für die ungerichteten Graphen immer das doppelte raus.

Code: Alles auswählen

private void countEdgesRec(Node<N, E> node, HashSet<Edge<N, E>> edgeSet, HashSet<Node<N, E>> nodeSet)
{
    if(!nodeSet.contains(node)){
        nodeSet.add(node);
        for(Edge e: node.getFanOut()){
            if(!edgeSet.contains(e)){
                edgeSet.add(e);
                countEdgesRec(e.getTargetNode(),edgeSet,nodeSet);
            }
        }
        for(Edge e: node.getFanIn()){
            if(!edgeSet.contains(e)){
                edgeSet.add(e);
                countEdgesRec(e.getSourceNode(),edgeSet,nodeSet);
            }
        }
    }
}

Kabooom
Erstie
Erstie
Beiträge: 19
Registriert: 17. Jun 2017 15:04

Re: Graph: countEdges Wie unterscheiden zwischen gerichtetem und ingerichtetem Graphen?

Beitrag von Kabooom » 25. Jun 2017 15:13

Du musst nicht überprüfen ob das edgeSet die gerade untersuchte Kante enthält (die kann noch gar nicht im edgeSet sein) sondern ob e.getLinkedEdge() schon enthalten ist, da e und e.getLinkedEdge() in einem ungerichteten Graphen als eine Kante betrachtet werden. Der rekursive Aufruf kann dann unabhängig davon ausgeführt werden, ob die Kante ins edgeSet aufgenommen wurde oder nicht.

LukasPhysiker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

Re: Graph: countEdges Wie unterscheiden zwischen gerichtetem und ingerichtetem Graphen?

Beitrag von LukasPhysiker » 25. Jun 2017 21:17

Um zu überprüfen, ob ein Graph gerichtet oder ungerichtet ist, kannst du folgenden Code verwenden:

Code: Alles auswählen

if(this instanceof UndirectedGraph)

Antworten

Zurück zu „AuD: Programmieraufgaben“