\documentclass[12pt,a4paper,leqno]{article}
\usepackage[utf8]{inputenc}
\usepackage{polski}
\usepackage{pgf}
\usepackage{tikz}
\usetikzlibrary{arrows,automata}
\usepackage{subfigure}
\usepackage{xcolor}
\usepackage{float}
\usepackage{geometry}
 \geometry{
 a4paper,
 total={170mm,257mm},
 left=20mm,
 top=20mm,
 }
\tikzset{
    ultra thick/.style={line width=10pt}
}
\usetikzlibrary{patterns}

\begin{document}
\section*{Algorytm Borůvki}

Jest to algorytm wyznaczający minimalne drzewo rozpinające dla grafu ważonego pod warunkiem, że jest on spójny. Jest on algorytmem zachłannym.

Algorytm na początku rozważa każdy z wierzchołków jako oddzielne drzewo, natomiast potem w pętli szuka dla każdego drzewa najlżejszą krawędź łączącą ją do kolejnego drzewa, dodaje ją do MST i łączy wierzchołki jako jedno drzewo do momentu, aż nie zostanie tylko jedno.

\subsection*{Lista kroków}

\begin{enumerate}
\item Rozważ wszystkie wierzchołki jako oddzielne drzewa.
\item Zadeklaruj MST jako puste.
\item Dopóki jest więcej niż jedno drzewo rób po kolei dla każdego drzewa .
   \begin{itemize}
     \item  Znajdź krawędź o najmniejszym koszcie który łączy drzewo do kolejnego drzewa.
     \item  Dodaj je do MST jeśli nie jest jeszcze dodane.
    \end{itemize}
\item Zwróć MST.
\end{enumerate}

\begin{figure}[ht]
\centering
\subfigure[Drzewo na początku, każdy wierzchołek tworzy oddzielne drzewo]{%
\begin{tikzpicture}[node distance=2.3cm,thick]

  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm, fill=gray!20] (b) {b};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (a) [below left of=b] {a};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (c) [right of=b] {c};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (d) [right of=c] {d};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (e) [below right of=d] {e};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (f) [below left of=e] {f};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (g) [left of=f] {g};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (h) [left of=g] {h};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (i) [below of=c, node distance=1.6cm] {i};


  \path[every node/.style={font=\sffamily\large}]
    (a) edge node [above left] {1} (b)
    (b) edge node [above] {2} (c)
    (c) edge node [above] {4} (d)
    (d) edge node [above right] {5} (e)
    (f) edge node [above] {2} (g)
    (e) edge node [below right] {7} (f)
    (g) edge node [above] {3} (h)
    (a) edge node [below left] {4} (h)
    (b) edge node [above right] {5} (i)
    (i) edge node [right] {1} (g)
    (i) edge node [above left] {2} (h)
    (c) edge node [above right] {2} (f);


\end{tikzpicture}}

\subfigure[Drzewo po przejściu przez każdy wierzchołek]{%
\begin{tikzpicture}[node distance=2cm,thick]

  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm, fill=gray!20] (b) {b};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (a) [below left of=b] {a};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (c) [right of=b] {c};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (d) [right of=c] {d};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (e) [below right of=d] {e};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (f) [below left of=e] {f};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (g) [left of=f] {g};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (h) [left of=g] {h};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (i) [below of=c, node distance=1.4cm] {i};

	\draw[-, ultra thick, gray!70] (a) -- (b);
	\draw[-, ultra thick, gray!70] (c) -- (f);
	\draw[-, ultra thick, gray!70] (d) -- (c);
	\draw[-, ultra thick, gray!70] (d) -- (e);
	\draw[-, ultra thick, gray!70] (i) -- (g);
	\draw[-, ultra thick, gray!70] (i) -- (h);

  \path[every node/.style={font=\sffamily\large}]
    (a) edge node [above left] {1} (b)
    (b) edge node [above] {2} (c)
    (c) edge node [above] {4} (d)
    (d) edge node [above right] {5} (e)
    (f) edge node [above] {2} (g)
    (e) edge node [below right] {7} (f)
    (g) edge node [above] {3} (h)
    (a) edge node [below left] {4} (h)
    (b) edge node [above right] {5} (i)
    (i) edge node [right] {1} (g)
    (i) edge node [above left] {2} (h)
    (c) edge node [above right] {2} (f);


\end{tikzpicture}}
\centering
\subfigure[Drzewo po zakończeniu]{%
\begin{tikzpicture}[node distance=2cm,thick]

  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm, fill=gray!20] (b) {b};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (a) [below left of=b] {a};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (c) [right of=b] {c};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (d) [right of=c] {d};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (e) [below right of=d] {e};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (f) [below left of=e] {f};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (g) [left of=f] {g};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (h) [left of=g] {h};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (i) [below of=c, node distance=1.4cm] {i};

	\draw[-, ultra thick, gray!70] (a) -- (b);
	\draw[-, ultra thick, gray!70] (c) -- (f);
	\draw[-, ultra thick, gray!70] (d) -- (c);
	\draw[-, ultra thick, gray!70] (d) -- (e);
	\draw[-, ultra thick, gray!70] (i) -- (g);
	\draw[-, ultra thick, gray!70] (i) -- (h);
	\draw[-, ultra thick, gray!70] (c) -- (b);
	\draw[-, ultra thick, gray!70] (g) -- (f);

  \path[every node/.style={font=\sffamily\large}]
    (a) edge node [above left] {1} (b)
    (b) edge node [above] {2} (c)
    (c) edge node [above] {4} (d)
    (d) edge node [above right] {5} (e)
    (f) edge node [above] {2} (g)
    (e) edge node [below right] {7} (f)
    (g) edge node [above] {3} (h)
    (a) edge node [below left] {4} (h)
    (b) edge node [above right] {5} (i)
    (i) edge node [right] {1} (g)
    (i) edge node [above left] {2} (h)
    (c) edge node [above right] {2} (f);
\end{tikzpicture}}
\caption{Wizualizacja działania algorytmu. }
\end{figure}
\newpage
W powyższej wizualizacji algorytm w pierwszym kroku znajduje najtańsze krawędzie :

\begin{figure}[H]
\centering
\begin{tabular}{|c|c|}
	\hline
	Drzewo& Krawędź \\
	\hline
	\{a\}& (a,b) \\
	\hline
	\{b\}& (a,b) \\
	\hline
	\{c\}& (c,d) \\
	\hline
	\{d\}& (c,d) \\
	\hline
	\{e\}& (d,e) \\
	\hline
	\{f\}& (c,f) \\
	\hline
	\{g\}& (g,i) \\
	\hline
	\{h\}& (h,i) \\
	\hline
	\{i\}& (g,i) \\
	\hline
\end{tabular}
\end{figure}

potem w drugim :

\begin{figure}[H]
\centering
\begin{tabular}{|c|c|}
	\hline
	Drzewo& Krawędź \\
	\hline
	\{a,b\}& (b,c) \\
	\hline
	\{c,d,e,f\}& (f,g) \\
	\hline
	\{g,h,i\}& (f,g) \\
	\hline
\end{tabular}
\end{figure}


\subsection*{Złożoność}
Mimo tego, że przez powyższą wizualizację można odnieść wrażenie, iż algorytm ten ma logaritmiczną złożność obliczeniową to jednak w implementacji jest ona równa $O(E\log{V})$, gdzie E to liczba  krawędzi a V liczba wierzchołków.

\subsection*{Źródła}

\begin{enumerate}
 \item https://www.geeksforgeeks.org/boruvkas-algorithm-greedy-algo-9/

 \item https://en.wikipedia.org/wiki/Borůvka\%27s\_algorithm
\end{enumerate}

\end{document}





















\begin{tikzpicture}[node distance=2cm,thick]

  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm, fill=gray!50] (b) {b};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!50] (a) [below left of=b] {a};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!50] (c) [right of=b] {c};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!50] (d) [right of=c] {d};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!50] (e) [below right of=d] {e};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!50] (f) [below left of=e] {f};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!50] (g) [left of=f] {g};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!50] (h) [left of=g] {h};
  \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!50] (i) [below of=c, node distance=1.4cm] {i};


  \path[every node/.style={font=\sffamily\large}]
    (a) edge node [above left] {3} (b)
    (b) edge node [above] {2} (c)
    (c) edge node [above] {4} (d)
    (d) edge node [above right] {5} (e)
    (f) edge node [above] {2} (g)
    (e) edge node [below right] {7} (f)
    (g) edge node [above] {3} (h)
    (a) edge node [below left] {4} (h)
    (b) edge node [above right] {5} (i)
    (i) edge node [right] {1} (g)
    (i) edge node [above left] {2} (h)
    (c) edge node [above right] {2} (f);


\end{tikzpicture}

\draw[-, ultra thick, gray!70] (a) -- (b);