//---------------------------------------------------------------------------
/*
    例10-9 Kruskal構造算法的范例程序
    關鍵：算法10.10 Kruskal算法構造最小生成樹
    首先，建立簡易的graph_miniTree類
    然后，編寫Kruskal構造算法的范例程序模塊
*/
#include <algorithm>
#include "Graph_Trav.h"
using namespace std;

//---------------------------------------------------------------------------
// 重載邊結點的<運算符
template <class T,class T1>
bool operator<(const EdgeNode<T,T1> &x, const EdgeNode<T,T1> &y)
{  return x.cost < y.cost;  }    // 由小到大排列, 在類外定義

// 建立簡易的graph_miniTree類
template <class T,class T1>
class graph_miniTree: public graph_traver<T>
{
    private:
       // 邊結點的向量容器
       vector<EdgeNode<T,T1> > Edges_data; // 存放初始化數據的向量
    public:
       // 構造器：創建基于鄰接鏈表的帶權值圖的Kruskal算法初始化對象
       graph_miniTree(weightedgraphInfo<T,T1> ginfo)
           : graph_traver<T>(ginfo.graph)
       {
           // 保存Kruskal算法的邊結點數據
           Edges_data.resize(GetnumEdges());
           for(int i=0; i<GetnumEdges(); i++) {
              Edges_data[i].v1 = ginfo.graph.edges[i].v1;
              Edges_data[i].v2 = ginfo.graph.edges[i].v2;
              Edges_data[i].cost = ginfo.edgesCost[i];
           }
       }
       vector<EdgeNode<T,T1> > Kruskal();
       void print_tree(vector<EdgeNode<T,T1> > tree)
       {
          T1 total=0;
          cout << "起點\t終點\t長度\n";
          for (size_t j=0; j<tree.size(); j++) {
              cout << " " << tree[j].v1 << "\t " << tree[j].v2 << "\t "
                   << tree[j].cost << endl;
          total += tree[j].cost;
          }
          cout << "  網絡最小生成樹的權值總和為" << total << endl;
       }
};
//---------------------------------------------------------------------------
// 實現
template <class T, class T1>
vector<EdgeNode<T, T1> > graph_miniTree<T, T1>::Kruskal()
{
   int n = GetnumVertices();
   T u, w;
   EdgeNode<T, T1> e;
   vector<EdgeNode<T, T1> > tree;			// 儲存最小生成樹的向量
   list<T> L;
   list<T>::const_iterator itr;
   // 構造過程初始化
   for(int i=0;  i<GetnumVertices();  i++)
      AdjLists[i].clear();
   // 向量Edges_data排序
   sort(Edges_data.begin(), Edges_data.end());
   i = 0;
   int k = 0;
   bool b;
   while (k<n-1)
   {
      // tree中含有邊數 n-1
      // E中選取最短邊e = (u, w)
      e = Edges_data[i]; 
      u = e.v1;  w = e.v2;
      b = false;
      // 深度搜索遍歷產生路徑
      L = dfs(u);							
      // 檢查(u,w)并入tree后是否產生回路：若b=true，則產生回路
      if(L.size()>1)
      {
         // 路徑長度至少為2才可能產生回路
         itr=L.begin();  itr++;  itr++;
         // 從第2條邊的末端頂點開始依次檢測其鄰接鏈表是否含有頂點w
         while(itr!=L.end())
         {
             list<T> adjL = AdjLists[GetVertexPos(*itr)];
             b = findVertex(adjL, w);
             if(b)  break;
             itr++;
         }
      }
      if( !b )
      {
         // b為false表示(u, w)并入tree后未產生回路，因此將(u, w)并入tree中
         tree.push_back(e);
         // 更新不帶權鄰接鏈表
         AdjLists[GetVertexPos(u)].push_front(e.v2);
         if(!gType)
             AdjLists[GetVertexPos(w)].push_front(e.v1);
         ++k;
      }
      ++i;
   }
   return tree;
}
//---------------------------------------------------------------------------
   // 測試最小生成樹Kruskal算法的輸入類常量
   const weightedgraphInfo<int,int> Kruskal_inf =
   {
      // 是否是有向圖
      false,
      // 頂點數、邊數
      6, 10,
      // 頂點信息
      {1,2,3,4,5,6},
      // 邊信息
      { {1,2},{1,3},{1,4},{2,3},{2,5},
        {3,4},{3,5},{3,6},{4,6},{5,6} },
      // 權值
      {  6,    1,    5,    5,    3,
         5,    6,    4,    2,    6    }
   };
void main()
{
   // 創建網絡對象并用輸入數據初始化
   graph_miniTree<int,int> G(Kruskal_inf);
   // 調用對象的Kruskal方法，返回向量后調用print_tree函數輸出
   G.print_tree(G.Kruskal());
}