diff options
| -rw-r--r-- | graph/graph.tex | 3 | ||||
| -rw-r--r-- | graph/kruskal.cpp | 9 |
2 files changed, 0 insertions, 12 deletions
diff --git a/graph/graph.tex b/graph/graph.tex index 596c0d6..5d8e5eb 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -11,9 +11,6 @@ Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so Für jeden Kreis $K$ im Graphen gilt: Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums. -\subsubsection{Kruskal} -\lstinputlisting{graph/kruskal.cpp} - \subsection{Kürzeste Wege} \subsubsection{Algorithmus von \textsc{Dijkstra}} diff --git a/graph/kruskal.cpp b/graph/kruskal.cpp deleted file mode 100644 index 0bd2e22..0000000 --- a/graph/kruskal.cpp +++ /dev/null @@ -1,9 +0,0 @@ -// Union-Find Implementierung von oben. Laufzeit: O(|E|*log(|E|)) -sort(edges.begin(), edges.end()); -vector<ii> mst; int cost = 0; -for (auto &e : edges) { - if (findSet(e.from) != findSet(e.to)) { - unionSets(e.from, e.to); - mst.push_back(ii(e.from, e.to)); - cost += e.cost; -}} |