blob: bf23c5bcac65efa4a5339dd3a9fb53ceada23f53 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
\section{Graphen}
\subsection{Lowest Common Ancestor}
\lstinputlisting{graph/LCA.cpp}
\subsection{Kürzeste Wege}
\subsubsection{Algorithmus von \textsc{Dijkstra}}
Kürzeste Pfade in Graphen ohne negative Kanten.
\lstinputlisting{graph/dijkstra.cpp}
\subsubsection{\textsc{Bellmann-Ford}-Algorithmus}
Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen.
\lstinputlisting{graph/bellmannFord.cpp}
\subsubsection{\textsc{Floyd-Warshall}-Algorithmus}
Alle kürzesten Pfade im Graphen.
\lstinputlisting{graph/floydWarshall.cpp}
\subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)}
\lstinputlisting{graph/scc.cpp}
\subsection{Artikulationspunkte und Brücken}
\lstinputlisting{graph/articulationPoints.cpp}
\subsection{Eulertouren}
\begin{itemize}
\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet), bzw. bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
\item Pfad existiert, wenn alle bis auf (maximal) zwei Knoten geraden Grad haben (ungerichtet), bzw. bei allen Knoten bis auf zwei Ein- und Ausgangsgrad übereinstimmen, wobei einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
\item \textbf{Je nach Aufgabenstellung überprüfen, wie isolierte Punkte interpretiert werden sollen.}
\item Der Code unten läuft in Linearzeit. Wenn das nicht notwenidg ist (oder bestimmte Sortierungen verlangt werden), gehts mit einem \lstinline{set} einfacher.
\end{itemize}
\begin{figure}[h]
\begin{lstlisting}
VISIT(v):
forall e=(v,w) in E
delete e from E
VISIT(w)
print e
\end{lstlisting}
\caption{Idee für Eulerzyklen}
\end{figure}
\lstinputlisting{graph/euler.cpp}
\subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)}
\lstinputlisting{graph/edmondsKarp.cpp}
|
