Brauch dringent Hilfe noch heute

E

ezio

Mitglied
Und zwar habe ich mit Hilfe folgende Tifensuche implemtiert aber bei der Ausgebe stimmt etwas nicht jeder Knoten wird doppelt gezählt,

kann sich jemand das anschauen ? wehre unendlich dankbar

Java: 
package test88;

public class Edge {
    int v;
    int w;

    Edge(int v, int w) {
        this.v = v;
        this.w = w;
    }
}


Java: 
package test88;

import java.util.LinkedList;

public class Graph {
    private int vertex;
    private int edges;
    private boolean directed;
    private LinkedList<Integer>[] adjlists;

    public Graph(int v, boolean d) {
        vertex = v;
        directed = d;
        edges = 0;
        adjlists = new LinkedList[v];
        for (int i = 0; i < v; i++)
            adjlists[i] = new LinkedList<Integer>();
    }

    int numOfV() {
        return vertex;
    }

    int numOfE() {
        return edges;
    }

    boolean directed() {
        return directed;
    }

    void insert(Edge e) {
        adjlists[e.v].add(new Integer(e.w));
        edges++;
        if (!directed) {
            adjlists[e.w].add(new Integer(e.v));
            edges++;
        }
    }

    void remove(Edge e) {
        adjlists[e.v].remove(new Integer(e.w));
        edges--;
        if (!directed) {
            adjlists[e.w].remove(new Integer(e.v));
            edges--;
        }
    }

    boolean edge(int v, int w) {
        return adjlists[v].contains(w);
    }

    LinkedList<Integer> getAdjList(int v) {
        return adjlists[v];
    }
}

Java: 
package test88;

import java.util.LinkedList;

class DFS {
    static final char WHITE = 0;    // der Knoten wurde noch nicht bearbeitet
    static final char GRAY = 1;        // der Knoten wird gerade bearbeitet
    static final char BLACK = 2;    // die Bearbeitung des Knotens wurde abgeschlossen 
 
    static char[] color;            // speichert die Farbe (=Bearbeitungszustand) eines Knotens 
    static int[] pi;                // speichert den Vorgänger eines Knotens beim Durchlauf 
    static int[] d;                    // speichert den Zeitpunkt des Bearbeitungsbeginns eines Knotens 
    static int[] f;                    // speichert den Zeitpunkt des Bearbeitungsendes eines Knotens 
 
    static int time;
 
    public static void dfs(Graph g) {     
        color = new char[g.numOfV()];        // Arry Größe auf Anzahl der Knoten festlegen
        pi = new int[g.numOfV()];            // Arry Größe auf Anzahl der Knoten festlegen
        d = new int[g.numOfV()];            // Arry Größe auf Anzahl der Knoten festlegen
        f = new int[g.numOfV()];            // Arry Größe auf Anzahl der Knoten festlegen
     
        for (int u = 0; u < g.numOfV(); u++) {
            color[u] = WHITE;                        // Schleife um alle Knoten Weiß zufäreben
            pi[u] = -1;                                // und Vorgänger auf -1 zusetzen         
        }
        time = 0;
        for (int u = 0; u < g.numOfV(); u++) {
            if (color[u] == WHITE);                    // Schleife zum testen ob Knoten noch unbesucht ist
            dfs_visit(g, u);                        // aktuellen Knoten übergeben
        }
    }

    private static void dfs_visit(Graph g, int u) {
        color[u] = GRAY;                            // aktuellen Knoten grau färben
        time++;
        d[u] = time;                                // Entdeckungszeit speichern     
     
        LinkedList<Integer> AdjList = g.getAdjList(u);            // Adjazenzliste des aktuellen Knoten holen

        for (int i = 0; i < AdjList.size(); i++) {
            int v = AdjList.get(i).intValue();
            if (color[v] == WHITE) {                // wenn Nachbar weiß ist dann...     
                pi[v] = u;                            //...aktuellen Knoten als Vorgänger setzen...
                dfs_visit(g, v);                    //... und rerusiv dfs_visit für den Nachbarn auf rufen
            }
        }
        color[u] = BLACK;                            // wenn es keinen weißen nachbarn gibt, Knoten schwatz färben
        f[u] = ++time;                                // finishing time speichern
        System.out.println("finished with node " + u);
        System.out.println("d = " + d[u] + ", f = " + f[u]);
    }
}

Java: 
package test88;

import java.util.LinkedList;

public class GraphTest {
    @SuppressWarnings("static-access")
    public static void main(String[] args) {
        Graph g = new Graph(10, false);
        DFS tief = new DFS();
        g.insert(new Edge(0, 1));
        g.insert(new Edge(0, 2));
        g.insert(new Edge(1, 8));
        g.insert(new Edge(1, 2));
        g.insert(new Edge(2, 3));
        g.insert(new Edge(3, 5));
        g.insert(new Edge(5, 4));
        g.insert(new Edge(4, 6));
        g.insert(new Edge(8, 9));
        g.insert(new Edge(9, 5));
        g.insert(new Edge(9, 6));
        g.insert(new Edge(6, 7));
        g.insert(new Edge(13, 10));
        g.insert(new Edge(10, 12));
        g.insert(new Edge(12, 7));
        g.insert(new Edge(7, 3));
        g.insert(new Edge(7, 11));
        g.insert(new Edge(11, 10));
        g.insert(new Edge(10, 7));
        g.insert(new Edge(10, 9));
        g.insert(new Edge(9, 7));
        g.insert(new Edge(13, 10));
        g.insert(new Edge(5, 7));
        g.insert(new Edge(5, 6));
        g.insert(new Edge(6, 7));
        g.insert(new Edge(7, 8));
        g.insert(new Edge(6, 8));
        g.insert(new Edge(8, 9));
        tief.dfs(g);
    }
}

Ausgabe ist folgende
finished with node 8
d = 4, f = 5
finished with node 9
d = 6, f = 7
finished with node 10
d = 8, f = 9
finished with node 3
d = 3, f = 10
finished with node 6
d = 12, f = 13
finished with node 7
d = 14, f = 15
finished with node 5
d = 16, f = 17
finished with node 4
d = 11, f = 18
finished with node 1
d = 2, f = 19
finished with node 11
d = 21, f = 22
finished with node 13
d = 23, f = 24
finished with node 14
d = 26, f = 27
finished with node 15
d = 28, f = 29
finished with node 12
d = 25, f = 30
finished with node 2
d = 20, f = 31
finished with node 0
d = 1, f = 32
finished with node 1
d = 33, f = 34
finished with node 2
d = 35, f = 36
finished with node 3
d = 37, f = 38
finished with node 4
d = 39, f = 40
finished with node 5
d = 41, f = 42
finished with node 6
d = 43, f = 44
finished with node 7
d = 45, f = 46
finished with node 8
d = 47, f = 48
finished with node 9
d = 49, f = 50
finished with node 10
d = 51, f = 52
finished with node 11
d = 53, f = 54
finished with node 12
d = 55, f = 56
finished with node 13
d = 57, f = 58
finished with node 14
d = 59, f = 60
finished with node 15
d = 61, f = 62
 
Zuletzt bearbeitet von einem Moderator:
JStein52

JStein52

Top Contributor
Musst du bei der Ausgabe nicht auch abfragen ob der Knoten nicht SCHWARZ ist ? Bei Zyklen kommst du ja an einigen Knoten (je nach Zyklus) mehrmals vorbei und dann machst du doch jedesmal den println() oder ??

Mach doch beim testen erst mal einen Graphen ohne Zyklen, dann einen mit
 
Zuletzt bearbeitet:

Aktuelle Jobs

Neue Themen


Oben