\documentclass{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{fullpage}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}
\usepackage {ngerman}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand {\mathset} [1] {\ensuremath {\mathbb {#1}}}
\newcommand {\R} {\mathset {R}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator{\emst}{emst}
\DeclareMathOperator{\conv}{CH}
\DeclareMathOperator{\argmin}{argmin}
\DeclareMathOperator{\DT}{DT}
\DeclareMathOperator{\UC}{UC}
\DeclareMathOperator{\LC}{LC}
\newcommand{\DKL}{D_\textup{KL}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{problem}[theorem]{Problem}
\newtheorem{obs}[theorem]{Beobachtung}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{definition}[theorem]{Definition}


\title{Graphen}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

\section{Operationen}
Der ADT Graph bietet folgende Operationen: 

\setlength{\itemsep}{-20pt}
\begin{itemize}
 \item  \texttt{vertices}$()$: liefere einen Iterator f\"ur die Knoten;
 \item \texttt{edges}$()$: liefere einen Iterator f\"ur die Kanten;
 \item \texttt{createVertex}$()$: erzeuge einen Knoten;
 \item \texttt{deleteVertex}$(v)$: l\"osche Knoten $v$;
 \item \texttt{createEdge}$(u,v)$: erzeuge Kante zwischen 
   $u$ und $v$ (unterschiedliche Semantik f\"ur 
   gerichtete und ungerichtete Graphen);
 \item \texttt{deleteEdge}$(e)$:  l\"osche Kante $e$.
\end{itemize}

Operationen f\"ur einen Knoten $v$:
\begin{itemize}
  \item $v\texttt{.incidentEdges}()$:  liefere einen Iterator f\"ur 
    die inzidenten Kanten. In gerichteten Graphen gibt es zwei
      Operationen: \texttt{outgoingEdges}$()$ und 
      \texttt{incomingEdges}$()$.
  \item $v\texttt{.setInfo}(o)$: speichere das Objekt $o$ am Knoten $v$;
  \item $v\texttt{.getInfo}()$: liefere das Objekt am Knoten $v$.
\end{itemize}

Operationen f\"ur eine Kante $e$:
\begin{itemize}
  \item $e\texttt{.endVertices}()$: liefere die beiden Endknoten von $e$;
  \item $e\texttt{.opposite}(v)$: liefere den Endknoten von $e$, der nicht $v$
     ist:
  \item $e\texttt{.setInfo}(o)$: speichere das Objekt $o$ an der Kante $e$;
  \item $e\texttt{.getInfo}()$: liefere das Objekt an der Kante $e$.
\end{itemize}

\section{Tiefensuche rekursiv}

Jeder Knoten $v$ hat ein \texttt{boolean}-Attribut
$v$\texttt{.found}, das anzeigt, ob $v$ von der
DFS schon entdeckt wurde. Zu Beginn ist
$v\texttt{.found} = \texttt{false}$ f\"ur alle Knoten $v \neq s$,
und $s\texttt{.found} = \texttt{true}$. Dabei ist $s$ der Startknoten.
Der Aufruf erfolgt durch $\texttt{dfs}(s)$.

\begin{verbatim}
dfs(v)
  //process v
  // Besuche rekursiv alle Nachbarn, die noch
  // nicht entdeckt wurden
  for e in v.outgoingEdges() do
    w <- e.opposite(v)
    if not w.found then
      w.found <- true
      dfs(w)
\end{verbatim}

\section{Tiefensuche iterativ}

F\"ur die iterative Version benutzen wir
einen expliziten Stack, der diejenigen Knoten
enth\"alt, die wir schon entdeckt haben, aber
f\"ur die wir noch nicht alle ausgehenden Kanten
inspiziert haben. Der Stack speichert zu jedem
solchen Knoten noch einen Iterator f\"ur die
Menge der jeweils inzidenten Kanten.
Zu Beginn ist das $v\texttt{.found}$ Attribut f\"ur alle
Knoten \texttt{false}.

\begin{verbatim}
// Initialisiere S
S <- new Stack
// process s
s.found <- true
S.push((s, s.outgoingEdges()))
while not S.isEmpty() do
  (v, e) <- S.top()
  // finde einen unentdeckten Nachbarn
  // des aktuellen Knoten
  do 
    if e.hasNext() then
      w <- e.next().opposite(v)
    else
      w <- NULL
  while w != NULL and w.found
  // falls v keinen unentdeckten Nachbarn mehr hat, 
  // nimm ihn vom Stack
  if w = NULL then
    S.pop()
  // ansonsten betrachte diesen Nachbarn als naechstes
  else  
    // process w
    w.found <- true
    S.push((w, w.outgoingEdges()))
\end{verbatim}

Der Stack entspricht dem ``Ariadnefaden'': die Knoten in \texttt{S} stellen
einen Pfad von $v$ zur\"uck zu $s$ dar. 

\section{Breitensuche}

Zu Beginn ist $v\texttt{.found} = \texttt{false}$ f\"ur alle Knoten $v$.

\begin{verbatim}
Q <- new Queue
s.found <- true
Q.enqueue(s)
while not Q.isEmpty() do
  v <- Q.dequeue()
  //process v
  for e in v.outgoingEdges() do
    w <- e.opposite(v)
    if not w.found then
      w.found <- true
      Q.enqueue(w)
\end{verbatim}

\section{BFS mit k\"urzesten Wegen}

Breitensuche l\"asst sich leicht modifizieren,
um k\"urzeste Wege in ungewichteten Graphen zu 
berechnen.
Jetzt speichert jeder Knoten zus\"atzlich noch
einen Wert $v.d$, der den Abstand zwischen $v$ und $s$ angibt, und
einen Zeiger $v\texttt{.pred}$, der zu dem Vorg\"angerknoten auf
einem k\"urzesten Weg von $v$ zu $s$ zeigt.

\begin{verbatim}
Q <- new Queue
s.found <- true
s.d <- 0       // Neu
s.pred <- NULL // Neu
Q.enqueue(s)
while not Q.isEmpty() do
  v <- Q.dequeue()
  //process v
  for e in v.outgoingEdges() do
    w <- e.opposite(v)
    if not w.found then
      w.found <- true
      w.d <- v.d + 1  // Neu
      w.pred <- v     // Neu
      Q.enqueue(w)
\end{verbatim}

\section{Dijkstra}

Der Algorithmus von Dijkstra verallgemeinert
den obigen BFS-Algorithmus auf gewichtete Kanten,
wobei alle L\"angen nichtnegativ sein m\"ussen.
Jede Kante hat jetzt eine L\"ange $e\texttt{.length} \geq 0$.

Es gibt folgende Unterschiede:
\begin{enumerate}
  \item Wir verwenden eine Priorit\"atswarteschlange
     statt einer einfachen Schlange.
  \item Die Interpretation f\"ur $v.d$ und $v.\texttt{pred}$
     ist ein bisschen anders. 
     F\"ur alle Knoten, f\"ur die $v\texttt{.found} = \texttt{true}$ ist 
     und die nicht mehr in \texttt{Q} sind, ist $v.d$ der 
     Abstand von $s$ zu $v$ und $v.\texttt{pred}$ der 
     Vorg\"anger auf einem k\"urzesten Weg.
     F\"ur alle Knoten, bei denen $v\texttt{.found} = \texttt{true}$
     ist und die noch in \texttt{Q} enthalten sind,
     ist $v.d$ die k\"urzeste L\"ange eines Weges von
     $s$ nach $v$, der nur Knoten $w$ benutzt, f\"ur die
     $(w\texttt{.found} = \texttt{true} \wedge w \not\in \texttt{Q})$
     gilt. $v\texttt{.pred}$ ist der Vorg\"anger von $v$ auf
     einem solchen Weg.
     Diese Information muss man aktualisieren,
     wenn man einen Knoten aus \texttt{Q} entnimmt.
\end{enumerate}

\begin{verbatim}
Q <- new PrioQueue
s.found <- true
s.d <- 0
s.pred <- NULL
Q.insert(s, 0)
while not Q.isEmpty() do
  v <- Q.extractMin()
  for e in v.outgoingEdges() do
    w <- e.opposite(v)
    if not w.found then
      w.found <- true
      w.d <- v.d + e.length
      w.pred <- v
      Q.insert(w, w.d)
    else if w is in Q then
      // Neu: hier muessen wir
      // ueberpruefen, ob der Weg
      // ueber v nach w kuerzer ist,
      // als der alte Weg.
      if v.d + e.length < w.d then
        w.d <- v.d + e.length
        w.pred <- v
        Q.decreaseKey(w, w.d)
\end{verbatim}

Man kann den Algorithmus vereinfachen,
indem man $v\texttt{.found} = \texttt{false}$ durch
$v.d = \infty$ darstellt. Dann kann man sich das 
$v\texttt{.found}$ Attribut sparen und braucht eine
\texttt{if}-Abfrage weniger.

\begin{verbatim}
Q <- new PrioQueue
// Fuege alle Knoten in Q ein
// und gibt ihnen Abstand INFTY 
for v in vertices() do
  v.d <- INFTY
  v.pred <- NULL
  Q.insert(v, INFTY)
// nur s hat Abstand 0
s.d <- 0
Q.decreaseKey(s, 0)
while not Q.isEmpty() do
  v <- Q.extractMin()
  for e in v.outgoingEdges() do
    w <- e.opposite(v)
    if v.d + e.length < w.d then
      w.d <- v.d + e.length
      w.pred <- v
      Q.decreaseKey(w, w.d)
\end{verbatim}

\end{document}