Erste Schritte Referenz zum Knoten davor, in einer Liste

[ioannis_m]

Tach zusammen,

ich hab einen Graph in der Adjazenzliste Repräsentation und möchte die

public void remove(Edge e)

Methode dazu schreiben. Ich iteriere über alle Elemente in der Liste mit Hilfe des Iterators

    public AdjList getAdjList(int v) {
        return new AdjLinkedList(v);
    }
        private class AdjLinkedList implements AdjList{
            private int v; private Node t;
            AdjLinkedList(int v) {
                this.v = v; t = null;
            }
            public int beg(){
                t = adj[v];
                return t == null ? -1 : t.x;
            }
            public int next(){
                if (t != null) t = t.next;
                return t == null ? -1 : t.x;
            }
            public boolean end(){
                return t == null;
            }
    }

Ich brauche eine Referenz zum Knoten davor, damit ich seinem next den Knoten danach zuweisen kann.

Ich dachte an so was

    public void remove(Edge e) {
        int v = e.v; int w = e.w;
        AdjList adjList = getAdjList(v);
       
        for (adjList.beg();!adjList.end();adjList.next()){
            int from = adjList.next();
            if (from == w)

aber somit springt die interne private Variable t auch nach vorne. Gibt es eine Möglichkeit die Referenz an die richtige Stelle zu bekommen, oder muss ich dazu auch den Iterator anfassen?

Danke & Gruß
ioannis

 

[stg]

Du klatsch uns hier totalen Ramsch-Code hin, der sich nicht einmal kompilieren lässt.
Niemand hier kennt die Struktur deiner Liste, daher wird dir auch niemand eine Antwort darauf geben können, wie man an den Knoten "davor" kommt. Zumal du auch gar nicht sagst, vor was du eigentlich meinst.
Nach dem, was ich hier bisher gesehen habe, denke ich aber, dass du deine Listen-Klasse noch einmal komplett überdenken und neu schreiben solltest.

 

[ioannis_m]

Ich hab die ganze top-level Klasse SparseGraph als unnötig bzw. Schrott eingestuft, dem scheint nicht so zu sein. Die remove() Methode ist nicht zu Ende geschrieben. Die Listen im adj[] Array, bestehen nur aus einem int und einer Referenz zum nächsten Knoten. Auf der Suche also nach dem Knoten der gelöscht werden soll, brauche ich eine Referenz zum Knoten davor, damit ich die Referenz des letzteren dem Knoten danach zuweisen kann.

public class SparseGraph implements Graph {
   



    private int numberV, numberE;
    private boolean digraph;
    private class Node{
        int x; Node next;
        Node(int x, Node n){
            this.x = x; this.next = n;
        }
    }
    private Node adj[];
   
    public SparseGraph(int v, boolean flag) {
        this.numberV = v; digraph = flag;
        adj = new Node[v];
    }
    @Override
    public int getV() {
        return numberV;
    }

    @Override
    public int getE() {
        return numberE;
    }

    @Override
    public boolean directed() {
        return digraph;
    }

    @Override
    public void insert(Edge e) {
        int v = e.v; int w = e.w;
        adj[v] = new Node(w, adj[v]);
        if (!directed())adj[w] = new Node(v, adj[w]);
        numberE++;
    }

    @Override
    public void remove(Edge e) {
        int v = e.v; int w = e.w;
        AdjList adjList = getAdjList(v);
       
        for (adjList.beg();!adjList.end();adjList.next()){
            int from = adjList.next();
            if (from == w)
        }
    }

    @Override
    public boolean edge() {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public AdjList getAdjList(int v) {
        return new AdjLinkedList(v);
    }
        private class AdjLinkedList implements AdjList{
            private int v; private Node t;
            AdjLinkedList(int v) {
                this.v = v; t = null;
            }
            public int beg(){
                t = adj[v];
                return t == null ? -1 : t.x;
            }
            public int next(){
                if (t != null) t = t.next;
                return t == null ? -1 : t.x;
            }
            public boolean end(){
                return t == null;
            }
    }
}

 

[Flown]

Das wirkt irgendwie alles so nach Hausaufgabe. Kannst du bitte mal alle Klassen/Interfaces und die Problemstellung hier posten?

 

[ioannis_m]

Meine letzte Hausaufgabe liegt Jahrzehnte zurück...

Ich gehe das Buch Algorithms in Java "Part 5 Graph Algorithms" von Robert Sedgewick durch. Alle Algorithmen basieren auf einem einfachen Interface, im Falle eines dünnbesetzten Graphen sieht die Klasse so aus (sie ist nicht fertig geschrieben weil remove() nicht in konstanter Zeit implementiert werden kann).

Die einzige Klasse die vielleicht noch fehlt wäre die

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