Praktische Informatik 1

10.2 Graphalgorithmen

• 
  Wdh.: Definition Graph
  
  • 
    Darstellung einer binären Relationen über einer endlichen Grundmenge
    
  • 
    Tupel (V,E), V endliche Menge von Knoten, E Menge von Kanten, zu jeder Kante genau ein Anfangs- und ein Endknoten
    
• 
  Repräsentationsmöglichkeiten
  
  • 
    als Relation (Menge von Paaren)
    
  • 
    Knotendarstellung, Verweise als Kanten
    
  • 
    Adjazenzmatrix
    

Knoten-Kanten-Darstellung

Syntaktisch lassen sich Graphen auch genauso wie endlich verzweigte Bäume darstellen:

class Graph{

char node;

int numberOfEdges;

Graph [] edge;

Graph (char c, int n) {

node=c;

numberOfEdges=n;

edge=new Graph [n];

}

}
Semantisch können Graphen Zyklen enthalten:

BeispielGraph() {

Graph nodeA=new Graph('A',1);

Graph nodeB=new Graph('B',2);

Graph nodeC=new Graph('C',3);

Graph nodeD=new Graph('D',0);

nodeA.edge[0]=nodeB;

nodeB.edge[0]=nodeD; nodeB.edge[1]=nodeC;

nodeC.edge[0]=nodeA; nodeC.edge[1]=nodeB; nodeC.edge[2]=nodeD;

}
Anwendung von Graphen

• 
  Beispiel: Verbindungsnetz der Bahn
  
• 
  Suche Verbindung zwischen zwei Knoten
  
• 
  Problem: Zyklen führen evtl. zu nicht terminierender Rekursion
  
• 
  Lösung: Markieren bereits untersuchter Knoten (z.B. Eintragen in einer Menge)
  

Erreichbarkeit - fehlerhaft

boolean search (char c) {

return suche(c, this); }

private boolean suche (char c, Graph g) {

// Achtung fehlerhaft!!

if (g==null) return false;

if (g.node==c) return true;

for (int i=0; i
if (suche(c, g.edge[i])) return true;

return false;

}

// funktioniert nur falls Graph zyklenfrei

// d.h. wenn Graph n-fach verzweigter Baum ist
Erreichbarkeit – korrigiert
import java.util.*;

Set s;

boolean search (char c) {

s = new HashSet();

return suche(c, this); }

private boolean suche (char c, Graph g) {

if (g==null) return false;

if (s.contains(g)) return false;

if (g.node==c) return true;

s.add(g);

for (int i=0; i
if (suche(c, g.edge[i])) return true;

return false;

}
Darstellung von Graphen als Adjazenzmatrix

• 
  Angenommen, die Knoten seien k₁…k_n
  
• 
  boolesche Matrix m der Größe n´n
  
  • 
    m[i][j] gibt an, ob eine Verbindung
    von k_i-1 zu k_j-1 existiert oder nicht
    
• 
  Vorbesetzung z.B. zu einem bestimmten Prozentsatz zufällig mit true:
  

public class Adjazenzmatrix {

static int n = 5;

boolean[][] matrix = new boolean [n][n];

void fillMatrixRandom (float f) {

for (int i = 0; i<n; i++)

for (int j = 0; j<n; j++)

matrix[i][j]=(Math.random()

void printMatrix () {

for (int i = 0; i<n; i++) {

for (int j = 0; j<n; j++)

System.out.print(matrix[i][j]?" t":" f");

System.out.println();}

System.out.println();

}

}
transitive Hülle

Def. transitive Hülle:

xR^*y « xRy Ú $z (xR^*z Ù zR^*y)

• 
  Algorithmus von Warshall:
  
  • 
    starte mit R^*=R
    
  • 
    für jeden möglichen Zwischenknoten z:
    
    • 
      Berechne für alle x und y, ob xR^*y Ú (xR^*z Ù zR^*y)
      
  • 
    Reihenfolge der Schleifen ist wichtig!
    
• 
  Algorithmus von Floyd (kürzeste Wege)
  
  • 
    Entfernungsmatrix, min statt Ú, + statt Ù
    

void warshall() {

for (int z=0; z<n; z++)

for (int x = 0; x<n; x++)

for (int y = 0; y<n; y++)

matrix[x][y]=matrix[x][y]||matrix[x][z]&&matrix[z][y];

}
Anwendung z.B. wie folgt:

public class AdjazenzmatrixTest {

public static void main(String[] args) {

Adjazenzmatrix A=new Adjazenzmatrix();

A.fillMatrixRandom(0.2f);

A.printMatrix();

A.warshall();

A.printMatrix();

}

}

10.3 Suchen und Sortieren

• 
  Gegeben eine (irgendwie strukturierte) Sammlung von Daten
  
  • 
    Spezielles Suchproblem: entscheide ob ein gegebenes Element in der Sammlung enthalten ist
    
  • 
    Allgemeines Suchproblem: finde ein (oder alle) Elemente mit einer bestimmten Eigenschaft
    
• 
  Algorithmen hängen stark von der Struktur der Datensammlung ab!
  
  • 
    im Folgenden: als Reihung (Array) organisiert
    

lineare Suche

• 
  Wenn über den Inhalt der Reihung nichts weiter bekannt ist, muss sie von vorne bis hinten durchsucht werden
  

public class EinfacheSuche {

public static final int n = 10;

static int[]r=new int[n];

static void printReihung() {

for (int i = 0; i<n; i++)

System.out.print(r[i] + " ");

System.out.println("");

}

static void fillReihungRandom() {

for (int i = 0; i<n; i++)

r[i]=(int) (Math.random()*10);

}

static int sucheLinear(int suchinhalt) {

for (int i=0;i<n;i++) {

if (r[i]==suchinhalt) return(i);

}

return (-1);//oder exception

}

public static void main(String[] args) {

fillReihungRandom();

printReihung();

System.out.println(sucheLinear(3));

}

}

• 
  Komplexität: mindestens 1, höchstens n Schleifendurchläufe è O(n)
  

binäre Suche

• 
  Wenn der Inhalt der Reihung aufsteigend sortiert ist, können wir es besser machen:
  

public class BinaerSuche {

public static final int n = 10;

static int[]r=new int[n];

static void printReihung() {...}

static void fillReihungSorted() {

final int inc = 3;

r[0]=(int) (Math.random()*inc);

for (int i = 1; i<n; i++)

r[i]= r[i-1] + (int) (Math.random()*inc);

}

static int sucheBZ(int si, int lo, int hi) {

if (lo > hi) return -1;

int mitte = (hi + lo) / 2;

if (si == r[mitte]) return mitte;

else if (si < r[mitte])

return sucheBZ(si, lo, mitte - 1);

else /* (si > r[mitte])*/

return sucheBZ(si, mitte + 1, hi);

}

static int sucheBinaer(int suchinhalt) {

return sucheBZ(suchinhalt, 0, n-1);

}

public static void main(String[] args) {

fillReihungSorted();

printReihung();

System.out.println(sucheBinaer(7));

}

}

Hashtabellen

• 
  Wenn über den Inhalt der Reihung mehr bekannt ist, können wir es noch besser machen
  
  • 
    Annahme: 10*i £ r[i] £ 10*i + 9,
    z.B. r[7] liegt zwischen 70 und 79,
    d.h. jedes Datenelement hat höchstens einen möglichen Platz
    

public class HashSuche {

public static final int n = 10;

static int[]r=new int[n];

static void printReihung() {...}

static void fillReihungHashable() {

for (int i = 0; i<n; i++)

r[i]= 10*i + (int) (Math.random()*10);

}

static int sucheHash(int suchinhalt) {

int idx = suchinhalt / 10;

return (r[idx]==suchinhalt)?idx:-1;

}

public static void main(String[] args) {

fillReihungHashable();

printReihung();

System.out.println(sucheHash(77));

}

}
Sortieren

• 
  Oft lohnt es sich, Daten zu sortieren
  
  • 
    einmalige Aktion, Abfragen häufig
    
  • 
    oft gleich beim Eintrag möglich
    
• 
  Wie sortiert man eine unsortierte Reihung?
  
  • 
    selection sort: größtes Element an letzte Stelle, zweitgrößtes an zweitletzte Stelle, usw.
    
    • 
      einfach aber ineffizient!
      
  • 
    insertion sort: In absteigender Reihenfolge: das i-te Element in den sortierten Bereich [i+1, …, n] einsortieren
    
    • 
      noch ineffizienter!
      
• 
  Beispiele
  

Bubblesort

• 
  Ineffizienz vorher: „weites“ Vertauschen mit Informationsverlust
  
• 
  Idee: Tauschen von Nachbarn
  
  • 
    Falls zwei Nachbarn in verkehrter Reihenfolge, vertausche sie
    
  • 
    nach dem i-ten Durchlauf sind die obersten i Elemente sortiert
    

public class BubbleSort {

public static final int n = 5;

static int[]r=new int[n];

static void printReihung() {...}

static void fillReihungRandom() {

final int range = 100;

for (int i = 0; i<n; i++)

r[i]=(int) (Math.random()*range);

}

static void swap (int i, int j) {

int h = r[i]; r[i] = r[j]; r[j] = h; }

static void bubbleSort () {

for (int k=n-1; k>0; k--)

for(int i=0; i
if (r[i]>r[i+1]) {

swap(i,i+1);

printReihung();

}

}

public static void main(String[] args) {

fillReihungRandom();

printReihung();

bubbleSort();

printReihung();

}

}

Quicksort

• 
  berühmter, schneller Sortieralgorithmus
  
• 
  wähle ein „mittelgroßes“ Element w=a[k], alle kleineren nach links, alle größeren nach rechts
  
• 
  rekursiv linke und rechte Teile sortieren
  

public class Quicksort {

...

private static int partition(int lo, int hi) {

swap((lo+hi)/2, hi);

int w = r[hi], k=lo;

for (int i=k; i
if (r[i]swap(i,k); k++;}

swap(k,hi);

return k;

}

public static void qSort(int lo, int hi) {

if (lo
int pivIndex = partition(lo,hi);

qSort(lo,pivIndex-1);

qSort(pivIndex+1, hi);

}

}

public static void quickSort() {

qSort(0,n-1);

}

public static void main(String[] args) {...}

}
Partitionierung (Methode partition(int[]a, int lo, int hi))

• 
  Idee: Pivotelement w irgendwo aus der Mitte wählen (eigentlich egal), am rechten Rand (hi) ablegen
  
• 
  Dann 3 Bereiche bilden
  
  • 
    lo..k-1 : Elemente kleiner als w
    
  • 
    k..i-1: Elemente größer gleich w
    
  • 
    i..hi-1: unsortierte Elemente