Durchläufe durch Graphen SS12

Aus ProgrammingWiki

Archivierte Version vom 2012-04-17T13:59:27+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Test: Tiefensuche
2 Test 1.1 Tiefensuche durch Baumstruktur
3 Test 1.2 Breitensuche mit Baumstruktur
4 Test 2.1: Tiefensuche mit Adjazenzliste
5 Test 2.2 Breitensuche mit Adjazenzliste
6 Test 2.3: Tiefensuche mit Java (direkte Eingabe aller Kanten)
7 Test 3: Breitensuche

Test: Tiefensuche

(define tiefensuche (lambda (knoten besucht)
              (cond
                [(null? knoten) besucht]
                [else
                 (display (tiefensuche (cdr knoten) (cons (car knoten) besucht)))
		 (newline)
                 (tiefensuche (cdr knoten) besucht)])))

;einführungsbeispiel zur arbeitsweise von dfs
;später andere dfs-impl. zu graph1!!!

(tiefensuche '(1 2 3) '())

Test 1.1 Tiefensuche durch Baumstruktur

;(define tree-1
;'(1 (2 (4) (5)) (3 (6) (7))))
;scheme hasst mich, tree-1 lässt sich nicht definieren, allerdings explizit als parameter eingeben :\

(define node? (lambda (tree)
                (and 
                 (list? tree)
                 (= (length tree) 3))))

(define leaf? (lambda (tree)
                (and 
                 (list? tree)
                 (= (length tree) 1))))


(define tiefe (lambda (tree)
                (cond
                  [(leaf? tree) (list (car tree))]
                  [else 
                   (let( [element (car tree)]
                         [left (cadr tree)]
                         [right (caddr tree)])
                     (cons element
                           (append (tiefe left)
                                   (tiefe right))))])))
;(trace 'tiefe)

(tiefe '(1 (2 (4) (5)) (3 (6) (7))))

Test 1.2 Breitensuche mit Baumstruktur

(define node? (lambda (tree)
                (and 
                 (list? tree)
                 (= (length tree) 3))))

(define leaf? (lambda (tree)
                (and 
                 (list? tree)
                 (= (length tree) 1))))

(breite '(1 (2 (4) (5)) (3 (6) (7))))

Test 2.1: Tiefensuche mit Adjazenzliste

(define graph
  '((1 2 4)
    (2 1 4)
    (3 3 5)
    (4 5)
    (5 3)))

(define graph2
  '((1 2 3)
    (2 1 4 5)
    (3 1 6 7)
    (4 2)
    (5 2)
    (6 3)
    (7 3)))

(define (expanding graph node)
  (let ((c (assoc node graph)))
    (if c (cdr c) '())))



(define dfs (lambda (graph src dst)
              (letrec 
                  ((dfs* (lambda (graph visited border dest)
               (cond 
                 ((null? border) #f)
                 ((eq? (car border) dest) (cons (car border) visited))
                 ((member (car border) visited)(dfs* graph visited (cdr border) dest))
                 (else (dfs* graph
                   (cons (car border) visited)
                   (append (expanding graph (car border)) (cdr border))
                   dest))))))
                (reverse (dfs* graph '() (list src) dst)))))

(dfs graph2 1 7)

Test 2.2 Breitensuche mit Adjazenzliste

(define bft (lambda (graph src dst)
              (letrec 
                  ([bft* (lambda (graph visited border dest)
               (cond 
                 [(null? border) #f]
                 [(eq? (car border) dest) (cons (car border) visited)]
                 [(memq (car border) visited)(bft* graph visited (cdr border) dest)]
                 [else (bft* graph
                   (cons (car border) visited)
                   (append (cdr border) (expand graph (car border)))
                   dest)]))])
                (reverse (bft* graph '() (list src) dst)))))

(bft graph2 1 7)

Test 2.3: Tiefensuche mit Java (direkte Eingabe aller Kanten)

// dfs.java
// demonstrates depth-first search
// to run this program: C>java DFSApp
////////////////////////////////////////////////////////////////
class StackX
   {
   private final int SIZE = 20;
   private int[] st;
   private int top;
// ------------------------------------------------------------
   public StackX()           // constructor
      {
      st = new int[SIZE];    // make array
      top = -1;
      }
// ------------------------------------------------------------
   public void push(int j)   // put item on stack
      { st[++top] = j; }
// ------------------------------------------------------------
   public int pop()          // take item off stack
      { return st[top--]; }
// ------------------------------------------------------------
   public int peek()         // peek at top of stack
      { return st[top]; }
// ------------------------------------------------------------
   public boolean isEmpty()  // true if nothing on stack
      { return (top == -1); }
// ------------------------------------------------------------
   }  // end class StackX



class Vertex
   {
   public char label;        // label (e.g. 'A')
   public boolean wasVisited;
// ------------------------------------------------------------
   public Vertex(char lab)   // constructor
      {
      label = lab;
      wasVisited = false;
      }
// ------------------------------------------------------------
   }  // end class Vertex



class Graph
   {
   private final int MAX_VERTS = 20;
   private Vertex vertexList[]; // list of vertices
   private int adjMat[][];      // adjacency matrix
   private int nVerts;          // current number of vertices
   private StackX theStack;
// ------------------------------------------------------------
   public Graph()               // constructor
      {
      vertexList = new Vertex[MAX_VERTS];
                                          // adjacency matrix
      adjMat = new int[MAX_VERTS][MAX_VERTS];
      nVerts = 0;
      for(int y=0; y<MAX_VERTS; y++)      // set adjacency
         for(int x=0; x<MAX_VERTS; x++)   //    matrix to 0
            adjMat[x][y] = 0;
      theStack = new StackX();
      }  // end constructor
// ------------------------------------------------------------
   public void addVertex(char lab)
      {
      vertexList[nVerts++] = new Vertex(lab);
      }
// ------------------------------------------------------------
   public void addEdge(int start, int end)
      {
      adjMat[start][end] = 1;
      adjMat[end][start] = 1;
      }
// ------------------------------------------------------------
   public void displayVertex(int v)
      {
      System.out.print(vertexList[v].label);
      }
// ------------------------------------------------------------
   public void dfs()  // depth-first search
      {                                 // begin at vertex 0
      vertexList[0].wasVisited = true;  // mark it
      displayVertex(0);                 // display it
      theStack.push(0);                 // push it

      while( !theStack.isEmpty() )      // until stack empty,
         {
         // get an unvisited vertex adjacent to stack top
         int v = getAdjUnvisitedVertex( theStack.peek() );
         if(v == -1)                    // if no such vertex,
            theStack.pop();
         else                           // if it exists,
            {
            vertexList[v].wasVisited = true;  // mark it
            displayVertex(v);                 // display it
            theStack.push(v);                 // push it
            }
         }  // end while

      // stack is empty, so we're done
      for(int j=0; j<nVerts; j++)          // reset flags
         vertexList[j].wasVisited = false;
      }  // end dfs
// ------------------------------------------------------------
   // returns an unvisited vertex adj to v
   public int getAdjUnvisitedVertex(int v)
      {
      for(int j=0; j<nVerts; j++)
         if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)
            return j;
      return -1;
      }  // end getAdjUnvisitedVertex()
// ------------------------------------------------------------
   }  // end class Graph
////////////////////////////////////////////////////////////////

class DFSApp
   {
   public static void main(String[] args)
      {
      Graph theGraph = new Graph();
      theGraph.addVertex('1');    // 0  (start for dfs)
      theGraph.addVertex('2');    // 1
      theGraph.addVertex('3');    // 2
      theGraph.addVertex('4');    // 3
      theGraph.addVertex('5');    // 4

      theGraph.addEdge(0, 1);     // 1-2
      theGraph.addEdge(1, 0); 	  // 2-1
      theGraph.addEdge(1, 3);     // 2-4
      theGraph.addEdge(0, 3); 	  // 1-4
      theGraph.addEdge(3, 4);	  // 4-5
      theGraph.addEdge(4, 2);     // 5-3
      theGraph.addEdge(2, 5); 	  // 3-5
      theGraph.addEdge(2, 2);	  // 3-3

      System.out.print("Visits: ");
      theGraph.dfs();             // depth-first search
      }
   }

DFSApp

Test 3: Breitensuche

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Vordefinitionen ;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;;;;;; 1: QUEUE ;;;;;;;;;;;;;;;;;

(define create-queue '())

(define enqueue (lambda (queue element)
                  (append queue (list element)))) ;;auch rappend genannt

(define front car)
(define dequeue cdr)

;;;;;;;; 2: GRAFEN ;;;;;;;;;;;;;;;;

(define graph1
  '((1 2 4)
    (2 1 4)
    (3 3 5)
    (4 5)
    (5 3)))

(define graph2
  '((1 2 3)
    (2 1 4 5)
    (3 1 6 7)
    (4 2)
    (5 2)
    (6 3)
    (7 3)))

;;nur 1 graphen definieren, queue-impl. ggf verbergen (evtl. selber schreiben lassen?)
;;anregung: in übung/vorlesung beliebigen graphen (orange) als liste übersetzen lassen und bfs/dfs testen

;;;;;;;; 3: FKT ;;;;;;;;;;;;;;;;;;;
(define (strip-duplicates ls)
  (let loop ((rest ls)
             (so-far '()))
    (if (null? rest)
        so-far
        (loop (cdr rest)
              (let ((first (car rest)))
                (if (member first (cdr rest))
                    so-far
                    (cons first so-far)))))))


(define breitensuche (lambda (graph start ziel)
                       (letrec ([bfs (lambda (end queue graph besucht)
                                       (write 'Layer: )
                                       (display queue)
                                       (newline)
                                       (cond
                                         [(equal? end (front (front queue))) (strip-duplicates (append besucht (list end)))]
                                         ;[(equal? end (front (front queue))) (remove-duplicates (append besucht (list end)))]
                                         ;oberes für vollständigen durchlauf und visited-liste, unübersichtliche ausgabe
                                         ;unteres für leichte übersicht durchlaufener kanten
                                         [(list? (assoc end queue)) (write 'Traversed.)]
                                         [else
                                          (bfs end 
                                               (append (dequeue queue)
                                                       (letrec ([new-paths (lambda (path node net)
                                                           (map (lambda (n) (cons n path)) (cdr (assoc node net))))])
                                                       (new-paths (front queue) (front (front queue)) graph)))
                                               graph
                                               (append besucht (list (front (front queue)))))]))])
                          (bfs ziel (list (list start)) graph '()))))

(breitensuche graph2 1 7)

Durchläufe durch Graphen SS12

Inhaltsverzeichnis

Test: Tiefensuche

Test 1.1 Tiefensuche durch Baumstruktur

Test 1.2 Breitensuche mit Baumstruktur

Test 2.1: Tiefensuche mit Adjazenzliste

Test 2.2 Breitensuche mit Adjazenzliste

Test 2.3: Tiefensuche mit Java (direkte Eingabe aller Kanten)

Test 3: Breitensuche

Suche