diff options
Diffstat (limited to 'graph')
| -rw-r--r-- | graph/graph.tex | 3 | ||||
| -rw-r--r-- | graph/kruskal.cpp | 18 |
2 files changed, 21 insertions, 0 deletions
diff --git a/graph/graph.tex b/graph/graph.tex index 7a85337..f23db82 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -13,6 +13,9 @@ 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 new file mode 100644 index 0000000..4703c45 --- /dev/null +++ b/graph/kruskal.cpp @@ -0,0 +1,18 @@ +typedef pair<int,int> ii; +typedef vector<pair<int,ii>> graph; + +//Takes a Graph g (EdgeList!!!) with N nodes and computes the MST and Cost of it. Runtime: O(|E|*log(|E|)) +//Requires UnionFind-Datastructure!!! +pair<graph,int> buildMST(int N, graph& g) { + UnionFind uf(N); + graph mst; int mst_cost = 0; int M = g.size(); + sort(g.begin(),g.end()); + for(int i = 0; i < M; i++) { + int u = g[i].second.first, v = g[i].second.second; + if(uf.findSet(u) != uf.findSet(v)) { + mst.push_back(g[i]); mst_cost += g[i].first; + uf.unionSets(u,v); + } + } + return make_pair(mst,mst_cost); +}
\ No newline at end of file |