Sunday, October 10, 2021

New Minimum Spanning Tree

 \textbf{Step 1:} Take the input graph $G$ such that $v$ number of vertices and $e$ number of edges.

\newline \newline

\textbf{Step 2:} Take the input graph $F$ that is a subgraph of $G$.

\newline \newline

\textbf{Step 3:} Initialize an array $result$ to store the minimum spanning tree $(mst)$.

\newline \newline

\textbf{Step 4:} We then iterate through all the edges of the graph $G$ [$for$ $e \in G$], check if the current edge is in the subgraph $F$ (if $e \in F$)

\newline \newline

\textbf{Step 5:} If the condition is true, then add the edge into the $result$ array and delete the edge from $G$.

\newline \newline

\textbf{Step 6: }Repeat steps 4 and 5 until all the edges of $G$ are visited.

\newline \newline

\textbf{Step 7:} We then run Kruskal's algorithm on $G$.

\newline \newline

\textbf{Step 8:} We then sort remaining edges in $G$ in ascending order based on the weight of the edge.

\newline \newline

\textbf{Step 9: }Pick the smallest edge from $G$ and check whether it forms a cycle with already existing edges in the $result$ array. If the cycle is not formed, then add it to the $result$ array. Otherwise, delete it.

\newline \newline

\textbf{Step 10: }Repeat step 9 until there are $(v-1)$ edges in the minimum spanning tree.

\newline \newline

\textbf{Correctness of the algorithm - }We want to include all the edges of the subgraph $F$ in the resulting minimum spanning tree. So, based on above steps we first, we first add all the edges of the subgraph $F$ and then apply Kruskal's algorithm on the remaining edges of graph $G$ to find the minimum spanning tree.

\newline \newline

\textbf{Time Complexity - } 

Step 4 - Time complexity for iteration of all edges of graph $G$ is $\mathcal{O}(e)$ \newline

Step 7 - Time complexity of Kruskal's algorithm is $\mathcal{O}(|E| \log |V|)$, \newline

Step 8 - Time complexity of Sorting remaining edges is $\mathcal{O}(|E| \log |E|)$ \newline

Step 9 - Time complexity for picking smallest edge and repeating step is $\mathcal{O}(|E| \log |V|)$ \newline

\newline \newline

\textbf{Total Time Complexity} is $\mathcal{O}(e)$ + $\mathcal{O}(|E| \log |V|)$ + 

$\mathcal{O}(|E| \log |E|)$ + $\mathcal{O}(|E| \log |V|)$ = \textbf{$\mathcal{O}(|E| \log |E|)$}

No comments:

Post a Comment