Erste Schritte brauche hilfe zum verstehen einer Klasse(Tiefensuche)

[ezio]

Hallo, ich wollte mich mal mit den verschidenen such Algorithmen auseinander setzen bzw es versuchen
habe nun zum Thema Tiefensuchen folgenden code gefunden

Spoiler: Tiefensuche

,

import java.util.*;


class Graph{
     
      int knotenZahl;
  Knoten[] knotenArray;
     
  Graph(){
        Knoten a = new Knoten("A"), b = new Knoten("B"), c = new Knoten("C"),
               d = new Knoten("D"), e = new Knoten("E"), f = new Knoten("F"),
               g = new Knoten("G"), h = new Knoten("H"), i = new Knoten("I"),
               k = new Knoten("K"), l = new Knoten("L"), m = new Knoten("M"),
               n = new Knoten("N"), o = new Knoten("O"), p = new Knoten("P");
        
         Knoten[] ka = {a,b,c,d,e,f,g,h,i,k,l,m,n,o,p};
         knotenArray = ka;
         knotenZahl  = ka.length;
        
         //Kanten definieren
         b.nachbarn.add(a);
         d.nachbarn.add(e); d.nachbarn.add(c); d.nachbarn.add(b);
         e.nachbarn.add(h);
         f.nachbarn.add(d); f.nachbarn.add(i);
         g.nachbarn.add(h);
         h.nachbarn.add(n); h.nachbarn.add(l); h.nachbarn.add(f);
         k.nachbarn.add(g);
         l.nachbarn.add(n); l.nachbarn.add(i);
         m.nachbarn.add(k);
         n.nachbarn.add(p); n.nachbarn.add(o);
         p.nachbarn.add(m);          
    }
 
  void resetMarken(){for (Knoten k : knotenArray) k.markiert = false;}
 
 
  int index(Knoten k){
        for (int i=0; i < knotenZahl; i++)
          if (k == knotenArray[i]) return i;
      return -1;   
      }   
 
  int index(String s){
        for (int i=0; i < knotenZahl; i++)
          if (s.equals(knotenArray[i].name)) return i;
      return -1;   
      }
     
  Knoten find(String s){
        for (int i=0; i < knotenZahl; i++)
          if (s.equals(knotenArray[i].name)) return knotenArray[i];
      return null;   
      }   
 
  boolean kante(int k1, Knoten k2){
        for (Knoten k : knotenArray[k1].nachbarn)
          if (k == k2) return true;
      return false;   
      }
     
     
  boolean kante(Knoten k1, Knoten k2){
        for (Knoten i1 : knotenArray)
          if (i1 == k1) for (Knoten i2 : k1.nachbarn)
             if (i2 == k2) return true;
      return false;   
      }          

  void nachbarn(){
      for (Knoten k1 : knotenArray)
        for (Knoten k2 : k1.nachbarn)
            System.out.println("Kante von "+k1+" nach "+k2+" vorhanden");
          }      
 

  void tiefenSuche(Knoten k){
      resetMarken();
      rekTiefenSuche(k);
      }
     
  void rekTiefenSuche(Knoten k){
      k.markiert = true;
      System.out.println(k);
      for (Knoten n : k.nachbarn)
            if (!n.markiert) rekTiefenSuche(n);   
     }
    
        
}

Spoiler: Knoten

import java.util.*;

class Knoten{
    String  name;
    boolean markiert;
    ArrayList<Knoten> nachbarn;
    Knoten(String s){ name = s; nachbarn = new ArrayList<Knoten>();}
    public String toString(){ return name;}
}

Was ich nicht verstehe warum es zwei boolean vergleiche gibt und wieso es ein index für den sring gibt sowie ein für den Knoten,der sring gehört doch zum Knoten, oder?

hoffe auf ein paar Tipps

 

[pacao]

Ohne mir jetzt den Code genauer angeschaut zu haben will ich dir den Tipp geben. Versuch es einfach mal selbst zu programmieren. Einfach einen Algorithmus der Tiefensuche, der in natürlicher Sprache geschrieben ist, umzusetzten. Dann verinnerlicht man diese Ansätze und versteht leichter
-> https://de.wikipedia.org/wiki/Tiefensuche

 

[JStein52]

Wo siehst du einen Index für den String ??

 

[AndiE]

So richtig erschließt sich mir das noch nicht. Unter Tiefensuche verstehe ich die Suche in einem Baum: Jedes Datenobjekt hat genau ein Eltern- und mehrere Kindobjekte. Außer dem Wurzelobjekt, das hat ein Elternobjekt. In einem Graf dagegen hat jedes Objekt mehrere Eltern und mehrere Kindobjekte. Es können dabei ja Schleifen auftreten, wo die Suche stecken bleibt, weil sie immer im Kreis läuft. kann mir das jemand erklären? Mir persönlich ist immer noch unklar, wie der Code das bewerkstelligt. Ich bin aber auch der Meinung, dass der Code so wie er dasteht nicht akzeptabel ist, weil z.B. im Knoten keine Kapselung der Daten erfolgt stattfindet. java ist nun mal OOP. Auch im Graf selbst wird die allgemeine Deklaration der Datenstruktur Graph mit dem konkreten Sachverhalt vermischt. Ich finde, dass das den Code schwer verständlich macht. mir fehlt auch die Main()-Funktion als Programmbeginn.

 

[JStein52]

Der Code den du oben stehen ist ist ja wohl nur beispielhaft und ein Knoten enthält als Nutzinformation hier halt einen String. Was soll daran nicht akzeptabel sein ? Und die Tiefensuche sucht ja auch nicht wirklich sondern geht den Baum/Graphen durch und gibt jeden gefundenen Knoten aus. Durch die Markierung wird verhindert dass welche doppelt ausgegeben werden (Zyklen im Graphen). sämtliche übrigen Methode die da stehen sind ja an und für sich erstmal ok und könnten ganz nützlich sein und sind zunächst mal ganz wertfrei. Und wenn dir die main-Methode fehlt mach dir doch mal eine und schau was passiert.

 

[JStein52]

Nimm z.B. mal diese main-Methode:

    public static void main(String[] args) {
        //
        Graph myGraph = new Graph();
        myGraph.nachbarn();
      
        myGraph.tiefenSuche(myGraph.find("H"));
    }

Schau was passiert und danach hast du evtl. konkrete Fragen
Zeichne dir z.B. mal an Hand der Ausgaben den Graphen auf und du wirst sehen dass da durchaus Zyklen drin sind. Er gerät aber trotzdem nicht in eine Endlos-Rekursion. Grund ist die Markierung der besuchten Elemente !

 

[AndiE]

Tatsächlich habe ich noch konkrete Fragen:
1. Tiefensuche in einem Baum ist für mich die Suche nach einem Knoten. In einem Graph wäre das also die Suche nach einem Knoten K2 von einem Ursprungsknoten K1 aus. Eine Tiefensuche hat dann entweder einen Pfad als Ergebnis oder "kein Pfad gefunden".
2. Es wurde zwar der Beweis erbracht, dass sich die Aufgabenstellung prozedural lösen lässt, aber was ist mit OOP? Ich denke, dass ich dann drei Klassen brauche: Anwendung, Graph und Knoten und die Main() in Anwendung prinzipiell so aussehen müsste:

main(){
GraphErstellen();
Knotenerstellen();
KantenErstellen();
Tiefensuchen("K",A");
}

Dabei gibt dann die Tiefensuche den Pfad von K nach A aus. Wie würden da die Klassen aussehen, das ist die Frage. Klar ist das mehr Aufwand, aber ich finde es wichtig, Java auch objektorientiert zu nutzen, also auch mit Kapselung. Wir mussten uns ja auch umstellen, als wir von Basic, C usw. zu Java gewechselt sind. Indirekte Obkeltorientierung ist eben keine "richtige Objektorientierung".

 

[JStein52]

Aber das hast du ja fast alles schon. Du hast eine Klasse Graph, eine Klasse Knoten ! Was du mit Anwendung meinst weiss ich gerade nicht aber klar Wird man eine Anwendung haben die das Ganze verwendet. Im Moment ist dies halt die main-Methode. Und die 4 Methoden die du oben aufführst hast du ja auch schon. Das GraphErstellen(); KnotenErstellen(); und KantenErstellen(); wird halt im Moment alles im Konstruktor von Graph erledigt, und zwar fest kodiert. Natürlich würde man das ausserhalb in der Anwendung machen.
Was du in dem Zusammenhang damit meinst es wurde prozedural gelöst verstehe ich nicht ?

 

[AndiE]

Jetzt staune ich auch. Wir kennen ja verschiedene Arten, ein Programm zu schreiben. Als die Programmiersprachen noch keine Objektorientierung kannten, wurde auf eine Art programmiert, die als "strukturierte Pogrammierung" bekannt war. Dabei war ein wesentlicher Aspekt, das Programm in Unterprogramme aufzuteilen, auch Prozeduren genannt. Daher nenne ich die Form die "prozedurale Programmierung". Früher standen diese in Bibliotheken bereit, heute kann man das selbe Prinzip mit Hilfe von Methoden verwenden, die Klassen bereitstellen- "Indirekt objektorientierte Programmierung". Objektorientierung besteht ja prinzipiell aus Datenobjekten die miteinander kommunizieren. Bei der Erstellung geht man schulmäßig davon aus, dass eine Klassendefinition eine Blaupause ist, was dann bedeutet, dass diese recht allgemein ist. Um die durch Anwendung der Blaupausen geschaffenen Objekt der Klassen Graph und Knoten zu indiviualisieren, ist nach meiner Erfahrung genau eine dritte Klasse notwendig, die ich "Anwendung genannt habe." Für mich ist das wichtig, weil es doch vielen Leuten große Schwierigkeiten macht, in diesem OO-Ansatz zu denken.

 

[JStein52]

Aha. Also fehlt dir schlicht und einfach die Anwendung zu dem ganzen ?? Der TE hatte damit begonnen dass er sich mit dem Algorithmus zur Tiefensuche beschäftigen wollte. Und das ist genau das was hier vorliegt. Es ging nicht darum den jetzt zum Beispiel in einer Anwendung die einen Wegeplan für eine Spedition errechnet einzubauen !
Und warum du meinst dass das ganze jetzt prozedural gelöst sei erschliesst sich mir nicht. Gib doch mal ein Beispile was du oo anders machen würdest ??

 

[AndiE]

package mauer;

public class Wand {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        steine s= new steine();
        stein c= new stein();
      
      
        c.inhalt("a","a");
        s.NeuerKnoten(c);
        //Knoten 2
        c.inhalt("b","b");
        s.NeuerKnoten(c);
        s.beziehung("a","b");
        //Knoten 3
        c.inhalt("c", "c");
        s.NeuerKnoten(c);
        s.beziehung("a", "b");
    }
}

package mauer;

import java.util.ArrayList;

public class steine {
  
    private ArrayList<stein> steinliste;

    public steine()
    {
        steinliste=new ArrayList<stein>();
  
    }
  
    public void NeuerKnoten(stein s)
    {
        stein neu= new stein();
        neu.Kopiere(s);
        steinliste.add(neu);
    }
  
    public void beziehung( String indexa, String indexb)
    {
        stein s1= new stein();
        stein s2= new stein();
        for( stein sl : steinliste)
        {
            if(sl.getIndex()==indexa)
            {
                s1=sl;
            }
        }
        for( stein sl : steinliste)
        {
            System.out.println(sl.getIndex()+ "-");
            if(sl.getIndex()==indexb)
            {
                s2=sl;
            }
        }
        s1.beziehung(s2);
        s2.beziehung(s1);
    }
}

package mauer;

import java.util.ArrayList;


public class stein {

  
    private    String Index;
    private String Content;
    private ArrayList<stein> boden;
    private stein nachbar;
      
    public stein()
    {
        boden= new ArrayList<stein>();
    }
      
  
    public String getIndex() {
        return Index;
    }


    public void setIndex(String index) {
        Index = index;
    }


    public String getContent() {
        return Content;
    }


    public void setContent(String content) {
        Content = content;
    }


    public void inhalt(String index,String name)
    {
        this.Index=index;
        this.Content=name;
    }  
  
    public void Kopiere(stein s)
    {
        this.Index=s.Index;
        this.Content=s.Content;
    }
  
    void beziehung(stein s)
    {
        nachbar=new stein();
        nachbar.Kopiere(s);;
        boden.add(nachbar);
    }
}

 

[AndiE]

Dieser Code macht zwar nur einen Bruchteil dessen, was der Code des TE macht. Trotzdem sieht man hier schon den Unterschied. Getter, Setter und Kopierfunktionen sind typische Elemente, die die eine von der anderen Programmierweise unterscheiden. Übrigens geht es hier nicht um eine Spedition. Es geht darum, eine Mauer zu beschreiben, indem der Nutzer angibt, welche Steine aufeinander liegen. Ich finde das Problem, in einem Netzwerk zu suchen, so interessant, weil es ja auch als NoSQL-Datenbank betrachtet werden kann.

 

[JStein52]

Da hast du dir ja ganz schön Mühe gegeben aber was hilft das ? Es ging um deine Kritik an den Klassen Graph und Knoten. Sag doch mal konkret was du da anders machen würdest ? Warum ist das prozedural gelöst ? Was ist daran "indirekt objektorientiert"

 

[thecain]

Du willst den TE kritisieren und zeigst dann solchen Code?

Strings mit == verglichen
Gross-Kleinschreibung nach gut Glück...

Dann ein Beispiel gewählt wo ich den Zusammenhang mit einem Graph nicht mehr sehen kann. Oder willst du in deiner Mauer den kürzesten Weg suchen?

 

[AndiE]

Ja, genau das ist das Ziel: Wie ist die Verbindung zwischen zwei Steinen? Ja, das mit der groß und Kleinschreibung ist mir hinterher auch eingefallen. Aber auch das ist nur ein Beispiel. Ihr würdet das ja alles viel besser machen, keine Frage. Zu der anderen Frage. Wie würdet Ihr es denn nennen, wenn ein einer Programmierumgebung, die Klassen bereitstellt, ohne getter und setter, Konstruktoren usw. programmiert wird? Letztendlich geht es doch darum sauberen java-Code zu entwickeln. Und für mich gehören zum modernen java-Programmieren auch getter und setter.

 

[JStein52]

Dann schreib doch endlich mal was du bei Graph und Knoten getten und setten willst ? Wir haben einen konkreten Code (Graph und Knoten) des TE. Schreibe ihn doch bitte so um dass er nicht mehr indirekt objektorientiert ist und sag was du da getten und setten willst ?! Es geht nicht um eine Mauer oder eine Spedition sondern einfach nur um den Alorithmus zur Tiefensuche !

 

[AndiE]

Mir geht es darum, dass dieser Algorithmus in einer Form umgesetzt wird, die Java-konform ist, also OOP beinhaltet. Sonst hätte der TE das auch bei "Mathematik" posten können.

 

[thecain]

getter und setter haben weniger mit moderner Java Entwicklung zu tun, als mit dem JavaBean Standard. Meiner Meinung nach ist es eine Unart sich keine Gedanken zu machen warum man etwas tut, sondern einfach Blind mit gettern/settern zu Arbeiten. Andere objektorientierte Sprachen können das auch.

Zudem geht es weniger um sauberen Java-Code als um die Implementierung einer Tiefensuche, welche der TE meiner Meinung nach nicht schlecht umgesetzt hat.

Er hat den Algorithmus in Java geschrieben und ist somit Java-Konform, was du mit deinem OOP hier willst, weiss ich nicht. Wenn er diesen Graph anwenden will, kann er das ja dann tun.

Quasi à la

   Graph myTSP = new Graph(myNodeArray);

dazu muss er nur noch seinen Testkonstruktor durch einen ersetzen, der direkt Nodes übergibt und alles ist i.o.

Was an deinem Beispiel mit der Mauer mehr OOP sein soll als seins, sehe ich nicht.

Hier noch ein interessanter Artikel zum Thema Getter/Setter