الگوریتم ادمون

این الگوریتم یک توصیف شهودی بازگشتی دارد. تابعی مانند ${\displaystyle f}$ را در نظر می‌گیریم. این تابع به عنوان ورودی، گراف وزن دار و جهت دار ${\displaystyle D}$، با یک راس ${\displaystyle r}$ به عنوان ریشه را می‌گیرد و به عنوان خروجی، یک درخت فراگیر ریشه دار، با کمترین هزینه، می‌دهد.
توصیف دقیق الگوریتم در ادامه آمده‌است. با گرفتن یک گراف وزن دار و جهت دار ${\displaystyle D}$ با ریشهٔ ${\displaystyle r}$، در ابتدا به این صورت عمل می‌کنیم که مجموعه‌ای از یال‌های موازی (یال‌های بین دو راس یکسان که دارای یک جهت هستند)را با یک یال که وزن آن برابر با مینیمم مقدار وزن آن یال‌های موازی است، جایگزین می‌کنیم.
حالا برای هر راس ${\displaystyle v}$ به جز ریشه، یال ورودی به آن راس که دارای کمترین هزینه‌است را علامت(به‌طور قراردادی) می‌زنیم. راسی که در سر دیگر این یال قرار دارد را با ${\displaystyle \pi (v)}$ مشخص می‌کنیم. اگر یال‌های علامت زده شده، تشکیل یک SRT(درخت فراگیر ریشه دار) را می‌دادند، یعنی تابع ${\displaystyle f(D)}$ این SRT را مشخص کرده‌است. در غیر این صورت، مجموعه یال‌های علامت زده شده، تشکیل حداقل یک دور را می‌دهند. یکی از دورها را (به صورت دلخواه) ${\displaystyle C}$ بنامید. حالا ما یک گراف وزن دار و جهت دار ${\displaystyle D^{\prime }}$ که دارای ریشه ${\displaystyle r^{\prime }}$ است را تعریف می‌کنیم. به این صورت که، راس‌های ${\displaystyle D^{\prime }}$ مانند راس‌های ${\displaystyle D}$ هستند نه ${\displaystyle C}$، به اضافه یک راس جدید که با ${\displaystyle v_{C}}$ مشخص می‌شود.
اگر ${\displaystyle (u,v)}$ یالی در ${\displaystyle D}$ باشد، با این شرط که ${\displaystyle u\notin C}$، یال ${\displaystyle e}$ را به صورت شرح داده شده در زیر به ${\displaystyle D^{\prime }}$ اضافه می‌کنیم.
اگر ${\displaystyle v\in C}$، ${\displaystyle e=(u,v_{C})}$ و ${\displaystyle w(e)=w(u,v)-w(\pi (v),v)}$
در غیر این صورت، اگر ${\displaystyle v\notin C}$، ${\displaystyle e=(u,v)}$ و and ${\displaystyle w(e)=w(u,v)}$.
ما هیچ یال دیگری را به ${\displaystyle D^{\prime }}$ اضافه نمی‌کنیم.
ریشهٔ ${\displaystyle r^{\prime }}$ در ${\displaystyle D^{\prime }}$، همان ریشهٔ ${\displaystyle r}$ در ${\displaystyle D}$. است.
با صدا کردن تابع ${\displaystyle f(D^{\prime })}$، یک SRT در ${\displaystyle D^{\prime }}$ می‌یابیم. در نظر داشته باشید که در این SRT، یال ورودی (یکتا) به ${\displaystyle v_{C}}$، یال ${\displaystyle (u,v_{C})}$ است. این یال می‌تواند از زوج مرتب‌هایی مانند ${\displaystyle (u,v)}$ با شرط ${\displaystyle u\notin C}$ و ${\displaystyle v\in C}$ باشد. علامت ${\displaystyle (\pi (v),v)}$ را بردارید و ${\displaystyle (u,v)}$ را علامت بزنید. حالا مجموعه یال‌های علامت زده شده، یک SRT می‌سازند که ما می‌توانیم آن را مقدار تابع ${\displaystyle f(D)}$ در نظر بگیریم.
دقت کنید که تابع ${\displaystyle f(D)}$ به وسیله تابع ${\displaystyle f(D^{\prime })}$ تعریف شده‌است. و تابع ${\displaystyle D^{\prime }}$ که یک گراف وزن دار، جهت دار و ریشه دار است، نسبت به گراف ${\displaystyle D}$ به شدت تعداد راس‌هایش کمتر است و استفاده از ${\displaystyle f(D)}$ برای یک گراف تک راس، کاری بیهوده‌است.

BV را یک مجموعه‌ای برای رئوس و BE را مجموعه‌ای برای یال‌ها در نظر بگیرید. اگر V را یک راس در نظر بگیرید و e هم یالی با بیشترین وزن مثبت و متصل به V باشد، C_i یک دور خواهد بود. G_۰ = (V_۰,E_۰) گراف اصلی است و u_i یک راس جانشین برای C_i است.

${\displaystyle BV\leftarrow BE\leftarrow \varnothing }$
i=0


A:
if ${\displaystyle BV=V_{i}}$ then goto B
for some vertex ${\displaystyle v\notin BV}$ and ${\displaystyle v\in V_{i}}$ {
   ${\displaystyle BV\leftarrow BV\cup \lbrace v\rbrace }$
   find an edge ${\displaystyle e=(x,v)}$ such that w(e) = max{ w(y,v)|(y,v) ${\displaystyle \in }$ Ei}
   if w(e) ≤ 0 then goto A
}
if ${\displaystyle BE\cup \lbrace e\rbrace }$ contains a circuit {
   i=i+1
   construct ${\displaystyle G_{i}}$ by shrinking ${\displaystyle C_{i}}$ to ${\displaystyle u_{i}}$
   modify BE, BV and some edge weights
}
${\displaystyle BE\leftarrow BE\cup {e}}$
goto A


B:
while i ≠ 0 {
   reconstruct ${\displaystyle G_{i-1}}$ and rename some edges in BE
   if ${\displaystyle u_{i}}$ was a root of an out-tree in BE {
       ${\displaystyle BE\leftarrow BE\cup \lbrace e|e\in C_{i}}$ and ${\displaystyle e\neq e_{0}^{i}\rbrace }$
   }else{
       ${\displaystyle BE\leftarrow BE\cup \lbrace e|e\in C_{i}}$ and ${\displaystyle e\neq {\tilde {e}}_{i}\rbrace }$
   }
   i=i-1
}
Maximum branching weight = ${\displaystyle \sum _{e\in BE}w(e)}$