Verstendnisproblem Adjazenzliste

[DerEisige]

Hallo Leute,
ich sitze gerade an einer Aufgabe bei der ich nicht verstehe was gefordert wird.
soll ich nun selber eine Arraylist Programmieren?

rd.

 

[zerix]

Hallo,

nein, du sollst keine ArrayList schreiben, denn das wäre ja eine Liste. Du sollst eine Klasse Graph erstellen, die einen Graphen repräsentiert. Diese soll zwei Methoden haben, addEdge und addNode. Knoten sind die Kreise, die die Nummern beinhalten und Kanten sind die Pfeile, die Knoten verbinden können. Wie du da intern implementierst, ist deine Sache.


Viele Grüße
Sascha

 

[DerEisige]

Ok also in die Richtung.

Ein Graph existiert nur einmal, kann aber unendlich fiele kanten haben, jede kante aber nur ein mal.

public class Main {

    public static void main(String[] args) {
        AdListe test = new AdListe();
       
        test.addNode('s');
        test.addNode('s');
        test.addNode('s');
    }
}

public class AdListe {
    ArrayList<Graph> liste = new ArrayList<>();
   
    public AdListe(){
    }
   
    public void addNode(char c){
        if(!this.exGraph(c)){
            Graph neu = new Graph(c);
            this.liste.add(neu);
            System.out.println("Graph " + c + " neu angelegt");
           
        }else{
            System.out.println("Graph " + c + " existiert bereit");
        }
       
    }
   
    private boolean exGraph(char c){
        for(Graph element:this.liste){
            if( element.graph == c){
                return true;
            }
        }
        return false;
    }
}

public class Graph {
    char graph;
    ArrayList<Character> kanten = new ArrayList<Character>();
   
    public Graph(char c){
        this.graph = c;
    }
   
    public void addKante(char c){
        this.kanten.add(c);
       
    }
    public void remKante(char c){
        this.kanten.remove(c);
    }
    public boolean surKante(char c){
        for(Character k:this.kanten){
            if( k == c){
                return true;
            }
        }
        return false;
    }
}

 

[zerix]

Das ist nicht ganz richtig. Bei dir besteht der Graph nur aus Kanten. Ein Graph besteht aus Kanten (Edges) und Knoten(Nodes) und Kanten verbinden Knoten. Ein Knoten soll eine Beschriftung erhalten, die aus einem char besteht, nicht der Graph. Die Klasse Graph hat die Methoden addNode und addEdge.

Viele Grüße
Sascha

 

[DerEisige]

also

public class Graph {
    char knoten;
    ArrayList<Character> kanten = new ArrayList<Character>();
...

der Graph
mit dem Knoten a
und den kanten a,b,c,d,e

a {a,b,c,d,e}

 

[zerix]

Das geht schon mehr in die richtige Richtung. Nur, dass dein Graph momentan nur einen Knoten beinhalten kann.
Du könntest beispielsweise eine HashMap nehmen. Da ist der Schlüssel der Name des Knotens und der Wert eine Liste die jeweils den Namen des Knoten enthält, auf den die Kante zeigen soll. Statt einer HashMap kannst du auch einfach eine ArrayList nehmen und den Buchstaben zum Index umrechnen. Dazu müsstest du aber festlegen, was Knotennamen sein könnten, wie beispielsweise nur Kleinbuchstaben oder nur Großbuchstaben.


Hier kannst du auch nochmal was zur Adjazenz-Liste lesen:
https://de.wikipedia.org/wiki/Adjazenzliste

Viele Grüße
Sascha

 

[DerEisige]

Jetzt bin ich ganz raus.
Habe ich nicht genau das abgebildet.


Vielleicht habe ich die Klassen falsch bannt, aber genau das habe ich doch abgebildet.

char knoten; <-- das ist der knoten
ArrayList<Character> kanten = new ArrayList<Character>(); <-- sind die kanten vom knoten

Also zum Beispiel
a [b,c,d]
b [b,c]
c [d]
d [e]
e [a]



Mani

public class Main {

    public static void main(String[] args) {
        AdListe graph = new AdListe();
     
        graph.addNode('a');
        graph.addNode('b');
        graph.addNode('c');
        graph.addNode('d');
        graph.addNode('e');
     
        graph.addEdge('a', 'b');
        graph.addEdge('a', 'c');
        graph.addEdge('a', 'd');
        graph.addEdge('b', 'b');
        graph.addEdge('b', 'c');
        graph.addEdge('c', 'd');
        graph.addEdge('d', 'e');
        graph.addEdge('e', 'a');
     
        graph.allGraph();
    }
}

AdListe

public class AdListe {
    ArrayList<Daten> liste = new ArrayList<>();
   
    public AdListe(){
    }
   
    public void addNode(char c){
        if(!this.exGraph(c)){
            Daten neu = new Daten(c);
            this.liste.add(neu);
            System.out.println("Graph " + c + " neu angelegt");
           
        }else{
            System.out.println("Graph " + c + " existiert bereit");
        }
       
    }
    public void addEdge(char a, char b){
        if( this.exGraph(a) && this.exGraph(b)){
           
            for(Daten element:this.liste){
                if( element.knoten == a){
                    element.addKante(b);
                    break;
                }
            }
        }else{
            System.out.println( a + " -> " + b + " Einer der Graphen Existiert nicht.");
        }
    }
   
    private boolean exGraph(char c){
        for(Daten element:this.liste){
            if( element.knoten == c){
                return true;
            }
        }
        return false;
    }
    public void allGraph(){
        for(Daten element:this.liste){
            System.out.println(element.toString());
        }
    }
}

Daten

public class Daten {
    char knoten;
    ArrayList<Character> kanten = new ArrayList<Character>();
 
    public Daten(char c){
        this.knoten = c;
    }
 
    public void addKante(char c){
        if(!this.kanten.contains(c)){
            this.kanten.add(c);
        }else {
            System.out.println("Kannte existirt bereiz im Graphen");
        }
    }
    @Override
    public String toString() {
        return "Graph knoten=" + knoten + ", => " + kanten + "";
    }

    public void remKante(char c){
        this.kanten.remove(c);
    }
}

 

[zerix]

Ja mehr oder weniger hast du es, aber die Bezeichnung stimmen immer noch nicht. Meiner Meinung nach passt es auch nicht, weil du die Kanten dem Knoten (bei dir Graph) hinzufügst und die sollten eigentlich zum Graphen (bei dir AdListe) gehören. Es geht aber viel einfacher. Hier mal Pseudocode.

class Graph{

   Map nodes = null;

  public Graph(){

        nodes = new HashMap();
   }

   public void addNode(char k){

        if(k not in nodes)
             nodes[k] = new ArrayList();
   }

   public void addEdge(char k, char j){
      if(k in nodes  and j in nodes){
           if(j not in nodes[k])
              nodes[k].append(j);
            
      }
   }


}

Wie gesagt, das ist Pseudocode, sollte aber in richtigem Java die Aufgabe erfüllen.

Viele Grüße
Sascha