Ü b u n g 12

12.3 Minimale Spannbäume

Prim´s Algorithmus
S = {a}, E´  
Solange S  V :
(1)	minimale kreuzende Kante ist {a,b} mit länge(a,b) = 1 
 S = S  {b} , E´ = E´  {a,b}
(2)	minimale kreuzende Kante ist {b,g} mit länge(b,g) = 1 
 S = S  {g} , E´ = E´  {b,g}
(3)	minimale kreuzende Kante ist {g,e} mit länge(g,e) = 1 
 S = S  {e} , E´ = E´  {g,e}
(4)	minimale kreuzende Kante ist {g,d} mit länge(g,d) = 1 
 S = S  {d} , E´ = E´  {g,d}
(5)	minimale kreuzende Kante ist {a,f} mit länge(a,f) = 1 
 S = S  {f} , E´ = E´  {a,f}
(6)	minimale kreuzende Kante ist {b,c} mit länge(b,c) = 1 
 S = S  {c} , E´ = E´  { b,c}
nun ist S = V

Ergebnis
Kanten	
{a,b}	
{b,g}	
{g,e}	
{g,d}	
{a,f}	
{b,c}	

Kruskal´s Algorithmus
Kanten aufsteigend sortieren
{a,b}, {g,c}, {g,d}, {e,d}, {e,d}, {b,g}, {a,g}, {a,f}, {e,f}, {b,c}, {c,d}
W = (V, E´) mit E´ = 
Solange W kein Spannbaum:
(1)	kürzeste kreuzende Kante {a,b} schließt keinen Kreis  E´ = E´  {a,b}
(2)	kürzeste kreuzende Kante {g,e} schließt keinen Kreis  E´ = E´  {g,e}
(3)	kürzeste kreuzende Kante {g,d} schließt keinen Kreis  E´ = E´  {g,d}
(4)	kürzeste kreuzende Kante {e,d} schließt Kreis  verwerfen
(5)	kürzeste kreuzende Kante {b,g} schließt keinen Kreis  E´ = E´  {b,g}
kürzeste kreuzende Kante {a,g} schließt Kreis  verwerfen
(6)	kürzeste kreuzende Kante {a,f} schließt keinen Kreis  E´ = E´  {a,f}
kürzeste kreuzende Kante {e,f} schließt Kreis  verwerfen
(7)	kürzeste kreuzende Kante {b,c} schließt keinen Kreis  E´ = E´  {b,c}
kürzeste kreuzende Kante {a,c} schließt Kreis  verwerfen

Ergebnis:
Kanten	
{a,b}	
{g,e}	
{g,d}	
{b,g}	
{a,f}	
{b,c}	

12.2 Erkennung von Brücken

a) Veränderung der Tiefensuche

Für den Startknoten brauchen wir eine zusätzliche Routine, da ihm keine minimale Anfangszeit der Nachbarn zugewiesen wird

void Anfang_tsuche(int v)
{
   Knoten *p;
   Anfang[v] = ++Anfang_nr;
   for (p = A_Liste[v]; p != 0; pnext)
      if (!Anfang[pname]) tsuche(pname, Anfang[v])

}

Die Tiefensuche soll für einen Knoten alle Anfangszeiten seiner Nachbarn, d.h. des Vorgängers, aller Nachfolger, sowie der nur über eine Rückwärtskante erreichbaren Nachbarn, sammeln und das Minimum dieser Werte ermitteln.
Hierfür benötigen wir noch eine lokale Variable Min und ein globales Array Min_Anfang_Nachbar[] :

int tsuche(int v, int Min)
{
   Knoten *p;
   Anfang[v] = ++Anfang_nr;
   int temp;
   for (p = A_Liste[v]; p != 0; pnext)
   {
      if (!Anfang[pname]) temp = tsuche(pname, Anfang[v])
      else temp = Anfang[pname];
      Min = (Min > temp) ? temp : Min;
   }
   Min_Anfang_Nachbar[v] = Min;
   return Anfang[v];
}

Zur Korrektheit kann ich nur sagen, daß in der Routine tsuche der aktuell bearbeitete Knoten über den Aufruf in der if-Schleife jedem Nachfahren seine Anfangszeit übergibt und über den return-Befehl auch deren Anfangszeiten zurückbekommt. Von den anderen Nachbarn werden die Anfangszeiten  - da diese bereits besucht worden  sind – über den else-Befehl abgefangen. Schließlich wird das Minimum immer am Ende der for-Schleife aktualisiert.

Zur Laufzeit: innerhalb der for-Schleife sind 2 Befehl hinzugekommen. Da aber Beide in Konstantzeit abgearbeitet werden können erhöht sich die Laufzeit der for-Schleife auf  3 * O(|E|). Außerhalb der for-Schleife sind auch noch 2 zusätzliche Befehle, die aber auch in O(1) abgearbeit werden  insgesamt O(|V| +|E|)

12.2 Erkennung von Brücken

b) Ermittlung aller Brücken

 Aus dem Teilaufgabe 12.2a haben wir das Array mit den "frühesten" Nachbarn für jeden Knoten v erhalten. Nun muß nochmals ein Tiefensuchbaum durchgelaufen werden, in welcher das Minimum aller "frühesten" Nachbarn aller Nachfolger vom Knoten v, also aller Kinder im Teilbaum mit Wurzel v, ermittelt werden

int tsuche(int v)
{
   Knoten *p;
   besucht[v] = 1;
   Min_Nachfolger = Anfang[v];
   int temp;
   for (p = A_Liste[v]; p != 0; pnext)
   {
      if(!besucht[pname]) 
      {
         temp = tsuche(pname);
         if(Min_Nachfolger > temp) Min_Nachfolger = temp;
         else printf("Es liegt eine Brücke zwischen %s und %s vor! \n", v, pname);
	}
   (Min_Nachfolger > Min_Anfang_Nachbar[v]) ? Min_Anfang_Nachbar[v] : Min_Nachfolger;
   return Min_Nachfolger
}

Die Gesamtlaufzeit ist wieder O(|V| +|E|), da insgesamt zweimal Tiefensuche gestartet wird mit jeweils einer Laufzeit von O(|V| +|E|).
Das Algorithmus bestimmt alle Brücken, da ein Knoten, der sich in einem Kreis befindet, mindestens einen Nachfolger besitzt dessen "frühester" Nachbar eine geringere Anfangszeit besitzt als der Ausgangsknoten

12.1 Blocksatz

Tja, dynamisches Programmieren, d.h. man müßte einen Algorithmus finden, der für eine Zeile, also für ein Intervall von Wort wi nach wj den geringsten ugly-Wert bestimmt. Vielleicht sollte der Algorithmus solange Wörter in eine Liste einfügen (Intervall vergrößern durch i-- und j++), solange die Zeilenlänge nicht überschritten wird und sich dabei merken, für welche i und j das Intervall die geringste Häßlichkeit besaß. 
Das noch iterieren über alle n Wörter und mit ein klein wenig Glück hätte man dann ein vernünftiges Endergebnis mit