Anzeige

Verstendnisproblem Adjazenzliste

DerEisige

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

2017-02-09_135935.jpg rd.
 

zerix

Hausmeister
Moderator
#2
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

Erfahrenes Mitglied
#3
Ok also in die Richtung.

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

Java:
public class Main {

    public static void main(String[] args) {
        AdListe test = new AdListe();
       
        test.addNode('s');
        test.addNode('s');
        test.addNode('s');
    }
}
Java:
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;
    }
}
Java:
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

Hausmeister
Moderator
#4
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

Erfahrenes Mitglied
#5
also
Java:
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

Hausmeister
Moderator
#6
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

Erfahrenes Mitglied
#7
Jetzt bin ich ganz raus.
Habe ich nicht genau das abgebildet.
2017-02-09_175146.jpg

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
Java:
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
Java:
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
Java:
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);
    }
}
 
Zuletzt bearbeitet:

zerix

Hausmeister
Moderator
#8
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.

Code:
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
 
Anzeige
Anzeige