diff options
Diffstat (limited to 'graph')
| -rw-r--r-- | graph/LCA.cpp | 16 | ||||
| -rw-r--r-- | graph/articulationPoints.cpp | 47 | ||||
| -rw-r--r-- | graph/euler.cpp | 41 | ||||
| -rw-r--r-- | graph/graph.tex | 17 |
4 files changed, 120 insertions, 1 deletions
diff --git a/graph/LCA.cpp b/graph/LCA.cpp new file mode 100644 index 0000000..b4e6bdd --- /dev/null +++ b/graph/LCA.cpp @@ -0,0 +1,16 @@ +//RMQ muss hinzugefuegt werden! +vector<int> visited(2*MAX_N), first(MAX_N, 2*MAX_N), depth(2*MAX_N); +vector<vector<int>> graph(MAX_N); + +void initLCA(int gi, int d, int &c) { + visited[c] = gi, depth[c] = d, first[gi] = min(c, first[gi]), c++; + for(int gn : graph[gi]) { + initLCA(gn, d+1, c); + visited[c] = gi, depth[c] = d, c++; + } +} +//[a, b] +int getLCA(int a, int b) { + return visited[queryRMQ(min(first[a], first[b]), max(first[a], first[b]))]; +} +//=> int c = 0; initLCA(0,0,c); initRMQ(); done! diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp new file mode 100644 index 0000000..b99a286 --- /dev/null +++ b/graph/articulationPoints.cpp @@ -0,0 +1,47 @@ +vector< vector<int> > adjlist; +vector<int> low; +vector<int> d; +vector<bool> isArtPoint; +vector< vector<int> > bridges; //nur fuer Bruecken +int counter = 0; + +void visit(int v, int parent) { + d[v] = low[v] = ++counter; + int numVisits = 0, maxlow = 0; + + for (vector<int>::iterator vit = adjlist[v].begin(); vit != adjlist[v].end(); vit++) { + if (d[*vit] == 0) { + numVisits++; + visit(*vit, v); + if (low[*vit] > maxlow) { + maxlow = low[*vit]; + } + + if (low[*vit] > d[v]) { //nur fuer Bruecken + bridges[v].push_back(*vit); bridges[*vit].push_back(v); + } + + low[v] = min(low[v], low[*vit]); + } else { + if (d[*vit] < low[v]) { + low[v] = d[*vit]; + } + } + } + + if (parent == -1) { + if (numVisits > 1) isArtPoint[v] = true; + } else { + if (maxlow >= d[v]) isArtPoint[v] = true; + } +} + +void findArticulationPoints() { + low.clear(); low.resize(adjlist.size()); + d.clear(); d.assign(adjlist.size(), 0); + isArtPoint.clear(); isArtPoint.assign(adjlist.size(), false); + bridges.clear(); isBridge.resize(adjlist.size()); //nur fuer Bruecken + for (int v = 0; v < (int)adjlist.size(); v++) { + if (d[v] == 0) visit(v, -1); + } +}
\ No newline at end of file diff --git a/graph/euler.cpp b/graph/euler.cpp new file mode 100644 index 0000000..74b3399 --- /dev/null +++ b/graph/euler.cpp @@ -0,0 +1,41 @@ +vector< vector<int> > adjlist; +vector< vector<int> > otherIdx; +vector<int> cycle; +vector<int> validIdx; + +void swapEdges(int n, int a, int b) { // Vertauscht Kanten mit Indizes a und b von Knoten n. + int neighA = adjlist[n][a]; + int neighB = adjlist[n][b]; + int idxNeighA = otherIdx[n][a]; + int idxNeighB = otherIdx[n][b]; + swap(adjlist[n][a], adjlist[n][b]); + swap(otherIdx[n][a], otherIdx[n][b]); + otherIdx[neighA][idxNeighA] = b; + otherIdx[neighB][idxNeighB] = a; +} + +void removeEdge(int n, int i) { // Entfernt Kante i von Knoten n (und die zugehoerige Rueckwaertskante). + int other = adjlist[n][i]; + if (other == n) { //Schlingen + validIdx[n]++; + return; + } + int otherIndex = otherIdx[n][i]; + validIdx[n]++; + if (otherIndex != validIdx[other]) { + swapEdges(other, otherIndex, validIdx[other]); + } + validIdx[other]++; +} + +//findet Eulerzyklus an Knoten n startend +//teste vorher, dass Graph zusammenhaengend ist! (isolierte Punkte sind ok) +//teste vorher, ob Eulerzyklus ueberhaupt existiert! +void euler(int n) { + while (validIdx[n] < (int)adjlist[n].size()) { + int nn = adjlist[n][validIdx[n]]; + removeEdge(n, validIdx[n]); + euler(nn); + } + cycle.push_back(n); //Zyklus am Ende in cycle +}
\ No newline at end of file diff --git a/graph/graph.tex b/graph/graph.tex index 8d01e97..e3fd262 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -1,5 +1,8 @@ \section{Graphen} +\subsection{Lowest Common Ancestor} +\lstinputlisting{graph/LCA.cpp} + \subsection{Kürzeste Wege} \subsubsection{Algorithmus von \textsc{Dijkstra}} @@ -17,5 +20,17 @@ Alle kürzesten Pfade im Graphen. \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} +\lstinputlisting{graph/euler.cpp} + \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} -\lstinputlisting{graph/edmondsKarp.cpp}
\ No newline at end of file +\lstinputlisting{graph/edmondsKarp.cpp} |