[Just another graph-related algorithm] Kruskal`s algorithm

Quote:

Originally Posted by androw3349 Interesting ^^ rewritten c# code maybe useful for some one Code: using System.Collections.Generic; using System; private int N; private int M; private priority_queue< pair<int, pair<int, int>> > q = new priority_queue< pair<int, pair<int, int>> >(); // our queue private List< pair<int, pair<int,int >> > tmp = new List< pair<int, pair<int,int >> >(); // auxiliary container private List< pair<int, pair<int,int >> > ffa = new List< pair<int, pair<int,int >> >(); // minimum spanning tree private bool[] jartam = new bool[1000]; // "jartam" means "visited" in hungarian :) private void getData() { ifstream fin = new ifstream( "kruskal.txt" ); fin >> N; fin >> M; pair<int, pair<int,int>> temp = new pair<int, pair<int,int>>(); int a; // from A to B, with a length of D int b; int d; for ( int i = 0; i < N; ++ i ) { fin >> a; fin >> b; fin >> d; temp.first = -d; temp.second.first = a; temp.second.second = b; // NOTE : we add the distance with a - prefix to ensure that the priority queue orders it in the right way q.push( temp ); } fin.close(); } private void Kruskal() { pair<int, pair<int,int>> temp = new pair<int, pair<int,int>>(); temp = q.top(); q.pop(); ffa.Add( temp ); jartam[ temp.second.first ] = true; jartam[ temp.second.second ] = true; while ( ! q.empty() ) { temp = q.top(); q.pop(); if ( jartam[ temp.second.first ] == true && jartam[ temp.second.second ] == false ) { // add to the m. spanning tree ffa.Add( temp ); // cout << temp.first << ' ' << temp.second.first << ' ' << temp.second.second << endl; jartam[ temp.second.second ] = true; // push tmp`s values while ( tmp.Count > 0 ) { q.push( tmp[ tmp.Count - 1 ] ); tmp.RemoveAt( tmp.Count - 1 ); } } if ( jartam[ temp.second.first ] == false && jartam[ temp.second.second ] == true ) { // add to the minimum spanning tree ffa.Add( temp ); // cout << temp.first << ' ' << temp.second.first << ' ' << temp.second.second << endl; jartam[ temp.second.first ] = true; // pushing tmp`s values while ( tmp.Count > 0 ) { q.push( tmp[ tmp.Count - 1 ] ); tmp.RemoveAt( tmp.Count - 1 ); } } if ( jartam[ temp.second.first ] == true && jartam[ temp.second.second ] == true ) { tmp.Add( temp ); // we put it aside } // else do nothing } } static int Main() { getData(); Kruskal(); Console.Write( "Minimum spanning tree : " ); Console.Write( "\n" ); for ( uint i = 0; i < ffa.Count; ++ i ) { Console.Write( ffa[ i ].second.first ); Console.Write( " -> " ); Console.Write( ffa[ i ].second.second ); Console.Write( " = " ); Console.Write( -ffa[ i ].first ); Console.Write( "\n" ); } Console.Read(); return 0; }