AuK/Durchläufe durch Graphen SS12
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
== Test: Tiefensuche ==
<code id="4f68b0ac368e7" hidden>(import debugging) (define amb-fail '*) (define initialize-amb-fail (lambda () (set! amb-fail (lambda () (error "amb" "It fails")))))
(initialize-amb-fail) (define-syntax amb (syntax-rules () ((amb alt ...) (let ((+prev-amb-fail amb-fail)) (call/cc (lambda (+sk) (call/cc
(lambda (+fk) (set! amb-fail (lambda () (set! amb-fail +prev-amb-fail) (+fk 'fail))) (+sk alt))) ... (+prev-amb-fail))))))) (define-syntax
bag-of (syntax-rules () ((bag-of e) (let ((+prev-amb-fail amb-fail) (+results '())) (if (call/cc (lambda (+k) (set! amb-fail (lambda () (+k
#f))) (let ((+v e)) (set! +results (cons +v +results)) (+k #t)))) (amb-fail)) (set! amb-fail +prev-amb-fail) (reverse! +results))))) (define
choice (lambda (ls) (eval (cons 'amb (map (lambda (x) (list 'quote x)) ls))))) (define multichoice (lambda (ls n) (if (= n 0) '() (let ((item
(choice ls))) (cons item (multichoice (delete item ls) (- n 1))))))) (define delete (lambda (item ls) (cond ((null? ls) '()) ((eqv? (car ls)
item) (cdr ls)) (else (cons (car ls) (delete item (cdr ls))))))) (define randomchoice (lambda (n) (letrec ((enumerate (lambda (i) (if (= i 0)
'() (cons i (enumerate (- i 1))))))) (let ((numberlist (enumerate n))) (choice numberlist)))))</code>
<code id="4f68afe40f6c1">
(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!!!
</code>
<run id="4f68afe40f72f">(tiefensuche '(1 2 3) '())</run>
== Test 1.1 Tiefensuche durch Baumstruktur ==
<code id="4f6f07043611d">
;(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)
</code>
<run id="4f6f0704361c9">
(tiefe '(1 (2 (4) (5)) (3 (6) (7))))
</run>
== Test 1.2 Breitensuche mit Baumstruktur ==
<code id="4f6f7d3ad381b">
(define node? (lambda (tree)
(and
(list? tree)
(= (length tree) 3))))
(define leaf? (lambda (tree)
(and
(list? tree)
(= (length tree) 1))))
</code>
<run id="4f6f7d3ad38f0">(breite '(1 (2 (4) (5)) (3 (6) (7))))</run>
== Test 2.1: Tiefensuche mit Adjazenzliste ==
<code id="4f6f7fc5b7345">
(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)))))
</code>
<run id="4f6f7fc5b73f1">
(dfs graph2 1 7)
</run>
== Test 2.2 Breitensuche mit Adjazenzliste ==
<code id="4f72f3f017a18">
(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)))))
</code>
<run id="4f72f3f017adb">(bft graph2 1 7)</run>
== Test 2.3: Tiefensuche mit Java (direkte Eingabe aller Kanten) ==
<code id="4f8d763f337a2">
// 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
////////////////////////////////////////////////////////////////
</code>
<code id="4f8d773e4ffc7">
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
}
}
</code>
<run id="4f8d773e500a7">DFSApp</run>
== Test 3: Breitensuche ==
<code id="4f68d5a9c9378">
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; 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 '()))))
</code>
<run id="4f68cd9f6c839">(breitensuche graph2 1 7)</run>