//圖的運算的實現文件graph2.cpp
#include"graph2.h"
//構造函數,初始化圖的鄰接矩陣與邊集數組
adjMList::adjMList(RCW GE[],int n,int e)
{int i,j;
 for(i=0; i<n; i++)
 for(j=0; j<n; j++)
  if(i==j) GA[i][j]=0;
  else GA[i][j]=MaxValue;
 for(i=0;i<e;i++) GE[i].weight=0;
 numE=0;
}
//輸出邊集數組中的每條邊
void adjMList::OutputEdgeSet(RCW ge[],int e)
{int i,k=0;
 cout<<"{";
 for(i=0; i<=e-2; i++)
  if(ge[i].weight>0){k++;
   cout<<'('<<ge[i].row<<','<<ge[i].col;
   cout<<','<<ge[i].weight<<") ";
   if(k%5==0) cout<<endl;}
  if(e>0&&ge[i].weight>0) {
   cout<<'('<<ge[e-1].row<<','<<ge[e-1].col;
   cout<<','<<ge[e-1].weight<<')';}
   cout<<'}'<<endl;
}
//建立無向帶權圖的鄰接矩陣
void adjMList::CreateMatrix(int n,int &e,RCW r[])
{int i,j,k=0,w;
 cout<<"依次輸入無向帶權圖的每條邊的起點和終點"<<endl;
 cout<<"序號及權值!直到輸入權值為0的邊為止!"<<endl;
 do {i=r[k].row;j=r[k].col;w=r[k].weight;
     //cin>>i>>j>>w;
     Check(n,i,j);
     if(k==e-1) break;
     GA[i][j]=GA[j][i]=w;k++;
   }while(1);
 numE=e=k;
 cout<<"鄰接矩陣:\n";
 for(i=0;i<n;i++)
 {for(j=0;j<n;j++)
   cout<<setw(4)<<GA[i][j];
   cout<<endl;}
}
//檢查輸入的邊序號是否越界,若越界則重輸
void adjMList::Check(int n, int& i, int& j)
{while(1) {
   if(i<0 || i>=n ||j<0 || j>=n)
    cout<<"輸入有誤,請重輸!";
   else return;
  cin>>i>>j;}
}
//根據圖的鄰接矩陣生成圖的邊集數組
void adjMList::ChangeEdgeSet(RCW GE[],int n,int e)
{//假定只考慮無向圖的情況
 int i,j,k=0;
 for(i=0; i<n; i++)
 for(j=i+1; j<n; j++)
  if(GA[i][j]!=0 && GA[i][j]!=MaxValue)
   {if(k==e) {cout<<"數組GE下標越界!\n";
     exit(1);}
    GE[k].row=i;
    GE[k].col=j;
    GE[k].weight=GA[i][j];
    k++;
   }
}
//按升序排列圖的邊集數組
void adjMList::SortEdgeSet(RCW GE[],int e)
{int i,j;
 RCW x;
 for(i=1; i<=e-1; i++)
  {x=GE[i];
   for(j=i-1; j>=0; j--)
    if(x.weight<GE[j].weight) GE[j+1]=GE[j];
    else break;
   GE[j+1]=x;
  }
}
//利用普里姆算法從頂點v0出發求出用鄰接矩陣GA表示
//的圖的最小生成樹,最小生成樹的邊集存于數組CT中
void adjMList::Prim(RCW CT[],int n)
{int i,j, k, min, t, m, w;
  //給CT賦初值，對應為v0依次到其余各頂點的邊
 for(i=0; i<n-1; i++)
  {CT[i].row=0;
   CT[i].col=i+1;
   CT[i].weight=GA[0][i+1];}
   //進行n-1次循環，每次求出最小生成樹中的第k條邊
 for(k=1; k<n; k++)
  {//從CT[k-1]~CT[n-2]中查找最短邊CT[m]
   min=MaxValue;
   m=k-1;
   for(j=k-1; j<n-1; j++)
    if(CT[j].weight<min) {
     min=CT[j].weight;
     m=j;}
  //把最短邊對調到第k-1下標位置
  RCW temp=CT[k-1];
  CT[k-1]=CT[m];
  CT[m]=temp;
  //把新并入最小生成樹T中的頂點序號賦給j
  j=CT[k-1].col;
  //修改有關邊，使T中到T外的每一個頂點各保持
  //一條到目前為止最短的邊
  for(i=k; i<n-1; i++) {
   t=CT[i].col;
   w=GA[j][t];
   if(w<CT[i].weight) {
    CT[i].weight=w;
    CT[i].row=j;
}}}}