[FRAGE] - DFS/ Adjazenzmatrix
Results 1 to 24 of 24
  1. #1

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts

    DFS/ Adjazenzmatrix

    wie habts ihr das beispiel wo man mit tiefensuche die adjazenzmatrix eines graphen ausgeben soll gemacht? war mir nicht sicher wie ich die ajazenzmatrix ausgeben soll, stimmt der algorithmus?
    PHP Code:
    DFS(s) { 
    initialisiere Stack
    initialisiere Matrix A
    [i,jmit A[i,j]=0 für alle i,(i,j=0,1,...,n)
    markiere s
    Speichere s
    solange (Speicher != NULL) { 
        
    snächstes_Element
        
    falls (es gibt ein k € n(smit k != markiert) { 
           
    speichere k
            
    markiere k
            
    A[s,k]=1;
           } 
        
    sonst  
            entferne s

        } 


  2. #2
    dose's Avatar
    Title
    Dipl.Ing
    Join Date
    Feb 2002
    Location
    Meidllling
    Posts
    1,037
    Thanks
    1
    Thanked 0 Times in 0 Posts
    Kuhl, ich wollts ursprünglich auch so in die Richtung machen (also mim Stack), dann ham mir die anwesenden Tutoren gsagt, ich solls rekursiv machen, weils sonst Punkteabzug gibt...dann hab ich ewig herumgschissn, und am Schluß is ma wieder mal die Zeit ausgangen...also hab ich irgendwas hingschmiert und damit wieder den Pseudocode versaut *speib*
    yast, SuSEconfig, apt-get and rpm - the 4 horsemen of the apocalypse

    Platform of insanity :: www.dose-xp.org

  3. #3
    SinusDiabolicus's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Wien
    Posts
    383
    Thanks
    0
    Thanked 0 Times in 0 Posts
    punkteabzug wenns nicht rekursiv is?
    und wer hat uns das gsagt?

    also wenn das stimmt und wenns bei mir deshalb knapp wird (was durchaus sein kann) können sie sich sicher sein daß ich mich aufreg...

  4. #4

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    ich hab erst jetzt bemerkt das ich keine adjazenzmatrix angegeben hab sondern ne adjazenzliste.... hätt wohl mehr schlafen sollen...oder mir zumindest die angabe durchlesen...

    arg
    laborg

  5. #5
    shabby's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Schrödinger, 1040 Wien
    Posts
    267
    Thanks
    2
    Thanked 9 Times in 8 Posts
    Original geschrieben von laborg
    ich hab erst jetzt bemerkt das ich keine adjazenzmatrix angegeben hab sondern ne adjazenzliste.... hätt wohl mehr schlafen sollen...oder mir zumindest die angabe durchlesen...

    arg
    laborg
    manche = meine Gruppen hatten Adjazenzlisten
    imho war nur die DFS so zu modifizieren:
    Code:
    für jedes w aus der Nachbarschaftsliste von v: push es auf die Ausgabeliste von v
    und am Schluß der DFS:
    Code:
    gib Nachbarschaftsliste von v aus
    da die DFS für jeden knoten genau einmal ausgeführt wird, führt das (trivialerweise?) zur Lösung.

    Wenn keine Ausgabeliste erlaubt sein soll, möchte ich sehen, wie du mit einer Höhensuche rekursiv Adjazenzlisten/matrizen ausgibts ...

  6. #6

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: DFS/ Adjazenzmatrix

    Original geschrieben von Lukas

    DFS(s) {
    initialisiere Stack
    initialisiere Matrix A[i,j] mit A[i,j]=0 für alle i,j (i,j=0,1,...,n)
    markiere s;
    Speichere s;
    solange (Speicher != NULL) {
    s= nächstes_Element;
    falls (es gibt ein k € n(s) mit k != markiert) {
    speichere k;
    markiere k;
    A[s,k]=1;
    }
    sonst
    entferne s;
    }
    }
    hab diesen pseudocode auch so geschrieben.. und im grunde sollts passen.. nur hast du anscheinend auch den selben (kleinen) fehler wie ich gemacht: In einer adjazenzmatrix sind ja für jede kante 2 1er eingetragen. Hätte also zum A[s,k]=1 noch A[k,s]=1 dazukommen sollen?

    ist mir eingefallen, sobald ich ausm hs draußen war.. *grml*

    was hast du als laufzeit davon angegeben? ich hab
    O(|V|^2+|E|)...

    @dose:
    wenns dafür punkteabzüge gibt, dasser nicht rekursiv ist... naja, das wär schon irgendwie ein schöner scheiß...

    mfg, chris
    hi, i'm a signature virus. copy me into your signature to help me spread.

  7. #7

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    Original geschrieben von shabby

    manche = meine Gruppen hatten Adjazenzlisten
    imho war nur die DFS so zu modifizieren:

    Wenn keine Ausgabeliste erlaubt sein soll, möchte ich sehen, wie du mit einer Höhensuche rekursiv Adjazenzlisten/matrizen ausgibts ...
    ich bin mir sicher ich hatte eine adjazenzmatrix zu coden.

    höhensuche? was meinst du damit? wir verwendeten nur die begriffe tiefen- und breitensuche.

    laborg

  8. #8
    Benno's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Posts
    105
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: DFS/ Adjazenzmatrix

    wie habts ihr das beispiel wo man mit tiefensuche die adjazenzmatrix eines graphen ausgeben soll gemacht? war mir nicht sicher wie ich die ajazenzmatrix ausgeben soll, stimmt der algorithmus?
    PHP Code:
    DFS(s) { 
    initialisiere Stack
    initialisiere Matrix A
    [i,jmit A[i,j]=0 für alle i,(i,j=0,1,...,n)
    markiere s
    Speichere s
    solange (Speicher != NULL) { 
        
    snächstes_Element
        
    falls (es gibt ein k € n(smit k != markiert) { 
           
    speichere k
            
    markiere k
            
    A[s,k]=1;
           } 
        
    sonst  
            entferne s

        } 

    habs genauso wie du, nur hab ich den stack und die matrix am anfang nicht initialisiert

  9. #9

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: Re: DFS/ Adjazenzmatrix

    Original geschrieben von Chris

    hab diesen pseudocode auch so geschrieben.. und im grunde sollts passen.. nur hast du anscheinend auch den selben (kleinen) fehler wie ich gemacht: In einer adjazenzmatrix sind ja für jede kante 2 1er eingetragen. Hätte also zum A[s,k]=1 noch A[k,s]=1 dazukommen sollen?

    ist mir eingefallen, sobald ich ausm hs draußen war.. *grml*
    ja stimmt das hätt man wahrscheinlich dazuschreiben sollen. hoffe dafür ziehens nicht viele punkte ab.

    was hast du als laufzeit davon angegeben? ich hab
    O(|V|^2+|E|)...
    ich dab O(n^2) angegeben. hab mir gedacht nachdem es eine (n,n)-matrix ist müssen n^2 felder überprüft werden. wie kommst du auf das +|E|?

  10. #10

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    +|E| ,weil die Zeile "falls (es gibt ein k € n(s) mit k != markiert) {" irgendwie auch von der Anzahl der kanten abhängt, bei mehr Kanten muss er hier auch länger nach einem k suchen
    klingt ein bisserl holprig, ich weiß

    außerdem haben die algorithmen im skriptum auch |V|+|E|, und ich kann mir nicht vorstellen, dass dieselbe tiefensuche, wenn man nur die rekursivität "herausnimmt", (im prinzip nur einen eigenen stack verwendet, anstatt dem prozessorstack) ihr laufzeitverhalten ändert...

    mfg, Chris
    hi, i'm a signature virus. copy me into your signature to help me spread.

  11. #11
    dose's Avatar
    Title
    Dipl.Ing
    Join Date
    Feb 2002
    Location
    Meidllling
    Posts
    1,037
    Thanks
    1
    Thanked 0 Times in 0 Posts
    Die Pseudocode Beispiele sind IMHO sowieso a Schas (sorry für die Wortwahl)...vielleicht gehts auch nur mir so, aber innerhalb von zehn Minuten an Pseudocode zamzupfuschen, den ma kaum testen kann, wenn ma e schon im Streß is (Hint: "Zeitdruck"), liegt mir nicht wirklich...Pseudocode für die Übungen is ja schön und gut, aber bei der Prüfung hat das irgendwie nix verloren...zumindest nicht zum Schreiben, viel gscheiter wärs doch, wenn ma einen Pseudocode vorgegeben hat und z.B. dessen Laufzeit analysiert, oder erklärt, was der Code tut...

    ...vielleicht aber red ich auch nur absoluten Stumpfsinn und bin einfach zu unfähig.
    yast, SuSEconfig, apt-get and rpm - the 4 horsemen of the apocalypse

    Platform of insanity :: www.dose-xp.org

  12. #12
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts
    mir gehts genauso, bei der vorlesungsprüfung kommen 2 glaub ich

  13. #13
    dose's Avatar
    Title
    Dipl.Ing
    Join Date
    Feb 2002
    Location
    Meidllling
    Posts
    1,037
    Thanks
    1
    Thanked 0 Times in 0 Posts
    Jetzt weiß ich wenigstens was ich mit den 90 Minuten mach...
    yast, SuSEconfig, apt-get and rpm - the 4 horsemen of the apocalypse

    Platform of insanity :: www.dose-xp.org

  14. #14

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    78
    Thanks
    0
    Thanked 0 Times in 0 Posts
    stand da nicht man soll die adjazenzmatrix des gegebenen graphen speichern
    (also nich die des DFS Baums, der durch Tiefensuche entsteht?)

    wenn nicht, dann hab ich mir da einigen unnötigen streß gemacht ...
    Last edited by tocvolxa; 22-05-2002 at 21:53.

  15. #15

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @dose: finde auch das das pseudocode schreiben bei der prüfung totaler schwachsinn ist. wenn man nicht zufällig (bzw weil der georg im repetitorium gesagt hat was kommt) den richtigen algorithmus auswendig gelernt hat kann man nie in der zeit einen algorithmus erfinden.

    @tocvolxa: also meiner meinung nach sollte das eigentlich das gleiche sein.

  16. #16

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    78
    Thanks
    0
    Thanked 0 Times in 0 Posts
    naja, angenommen du hast einen rgaphen mit drei knoten, jeder mit jedem verbunden:
    dann verlierst du die kante zwischen dem element dass du als erstes in den stack gibst und dem letzten.

    (oder siehe auch skript S114)

  17. #17
    dose's Avatar
    Title
    Dipl.Ing
    Join Date
    Feb 2002
    Location
    Meidllling
    Posts
    1,037
    Thanks
    1
    Thanked 0 Times in 0 Posts
    Ach ja, was ich mich auch gfragt hab...wofür brauch ich die Tiefensuche, um die Adjazenzmatrix darzustellen ? Ohne die Adjazenzmatrix kann i kaum gscheit mit an Graphen arbeiten, also Angabe = Lösung, Weg = unsinnig ? Oder bin ich heut einfach nur zu angfressen und sollt mir ein paar Beruhigungsmittel reinhauen ? Dabei war ich gestern nach dem Repetitorium noch frohen Mutes...
    yast, SuSEconfig, apt-get and rpm - the 4 horsemen of the apocalypse

    Platform of insanity :: www.dose-xp.org

  18. #18

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    78
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @dose: hast recht, verrückt.

    eine effiziente implementierung wäre also gar keine
    laufzeit O(0) *gg*

  19. #19

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts
    sorry, hab da was verwechselt, adjazenzmatrix von dem dfs-baum und dem graphen is natürlich nicht das gleiche.
    aber bei meinem algorithmus werden durch das if-statement (das wenn mans ausprogrammiert eigentlich eine schleife sein müsste) alle mit dem s benachbarten knoten ausgegeben -> adjazenzmatrix des graphen.

    für die adjazenzmatrix des dfs-baumes müsste man glaub ich einma pro schleifendurchlauf A[s, s_nachfolger]=1 schreiben.

  20. #20

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    78
    Thanks
    0
    Thanked 0 Times in 0 Posts
    tschuldigung, aber da steh ich jetz wohl auf der leitung:
    also nochmal das beispiel mit einem graphen mit 3 knoten V=(1,2,3) und 3 Kanten E=(1-2,1-3,2-3)
    anfangs elemt sei 1
    --> 1 markiert und im stack
    --> irgendein nachbar wird markiert, sagne wir mal es sei 2 (kante 1-2 gesp)
    --> 1 , 2 im stack
    --> nich markierter nachbar von 2 ist 3 (kante 2-3 gesp)
    --> 1, 2, 3 im stack
    --> 3 wird gelösche (alle knoten schon markiert), dann 2 dann 1 gelöscht

    und kante 1-3 imho nicht eingetragen.?

  21. #21

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @tocvolxa: ja, hast recht... die kante wird überlesen.. ist anscheinend doch nicht so toll, unser code...

    und @dose: kann nur zustimmen...
    hi, i'm a signature virus. copy me into your signature to help me spread.

  22. #22

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @tocvolxa: stimmt nicht ganz, aber mir fällt auch grad auf dass bei dem pseudocode einiges nicht stimmt.

    es wird nicht irgendein nachbar markiert und die kannte gespeichert, sondern alle nachbarn.
    also im ersten durchlauf werden die kanten 1-2 und 1-3 gespeichert (und 2-1 und 3-1 nicht weil ich das vergessen hab, aber das haben wir eh vorher schon gehabt). leider wird dabei auch zwei und drei markiert, daher wird dann im nächsten schleifendurchlauf 2-3 nicht gespeichert. fürchte das wird nicht viele punkte bringen

  23. #23

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    Original geschrieben von Lukas
    wenn man nicht zufällig (bzw weil der georg im repetitorium gesagt hat was kommt) den richtigen algorithmus auswendig gelernt hat kann man nie in der zeit einen algorithmus erfinden.
    schreibst des am besten per sides4me...

    aber das man den algo wenn man ihn nicht schon vorher kennt nicht erfinden kann glaube ich nicht... nur dazu wär mehr übung notwendig..und wie oft mussten wir schon pseudocodieren???

    mfg laborg

  24. #24

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    hmm.. also ich würde den dfs-algorithmus ausm skriptum hernehmen und in der schleife, die alle benachbarten knoten von einem bestimmten knoten durchläuft, gleich ganz am anfang (noch bevor auf markierungen geprüft wird) einen entsprechenden eintrag in die adjazenzmatrix machen... sollte passen

    mfg, Chris
    hi, i'm a signature virus. copy me into your signature to help me spread.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •