//圖的相關(guān)運(yùn)算的實(shí)現(xiàn)graph0.cpp
#include"graph0.h"
//構(gòu)造函數(shù),初始化圖的鄰接矩陣
AdjMatrix::AdjMatrix(int n,int k2)
{int i,j;
 if(k2==0){//初始化無(wú)(有)向無(wú)權(quán)圖
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    GA[i][j]=0;}
 else {//初始化無(wú)(有)向有權(quán)圖
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    if(i==j) GA[i][j]=0;
    else GA[i][j]=MaxValue;}
 size=numE=0;
}
//建立圖的鄰接矩陣
void AdjMatrix::CreateMatrix(int n,int k1,int k2,RCW r[])
//k1為0則無(wú)向否則為有向,k2為0則無(wú)權(quán)否則為有權(quán)
{int i,j,k,e,w;
 cout<<"輸入圖的總邊數(shù):";
   cin>>e;
 if(k1==0 && k2==0) { //建立無(wú)向無(wú)權(quán)圖
  cout<<"輸入"<<e<<"條無(wú)向無(wú)權(quán)邊的起點(diǎn)和終點(diǎn)序號(hào)!"<<endl;
  for(k=1; k<=e; k++) {
   cin>>i>>j;
   Check(n,i,j);
   GA[i][j]=GA[j][i]=1;}
  }
 else if(k1==0 && k2!=0) { //建立無(wú)向有權(quán)圖
   cout<<"輸入"<<e<<"條無(wú)向帶權(quán)邊的起點(diǎn)和終點(diǎn)序號(hào)及權(quán)值!"<<endl;
   for(k=0; k<e; k++) {
    i=r[k].row;j=r[k].col;w=r[k].weight;
    //cin>>i>>j>>w;
    Check(n,i,j);
    GA[i][j]=GA[j][i]=w;}
  }
  else if(k1!=0 && k2==0) { //建立有向無(wú)權(quán)圖
    cout<<"輸入"<<e<<"條有向無(wú)權(quán)邊的起點(diǎn)和終點(diǎn)序號(hào)!"<<endl;
    for(k=1; k<=e; k++) {
     cin>>i>>j;
     Check(n,i,j);
     GA[i][j]=1;}
  }
  else if(k1!=0 && k2!=0) { //建立有向有權(quán)圖
    cout<<"輸入"<<e<<"條有向有權(quán)邊的起點(diǎn)和終點(diǎn)序號(hào)及權(quán)值!"<<endl;
    for(k=0; k<e; k++) {
     i=r[k].row;j=r[k].col;w=r[k].weight;
     //cin>>i>>j>>w;
     Check(n,i,j);
     GA[i][j]=w;}}
  cout<<"創(chuàng)建后的鄰接矩陣:\n";   
  for(i=0;i<n;i++)
  {for(j=0;j<n;j++)
    cout<<setw(4)<<GA[i][j];
   cout<<endl;}
}
//從初始點(diǎn)vi出發(fā)深度優(yōu)先搜索由鄰接矩陣表示的圖
void AdjMatrix::dfsMatrix(bool*& visited,int i,int n,int k2)
{cout<<g[i]<<':'<<i<<"  ";
 visited[i]=true;        //標(biāo)記vi已被訪問過
 for(int j=0; j<n; j++)  //依次搜索vi的每個(gè)鄰接點(diǎn)
  if(k2==0)
   {if(i!=j&&GA[i][j]!=0&&!visited[j])
     dfsMatrix(visited,j,n,k2);}
  else
   if(i!=j&&GA[i][j]!=MaxValue&&!visited[j])
     dfsMatrix(visited,j,n,k2);
}
//從初始點(diǎn)vi出發(fā)廣度優(yōu)先搜索由鄰接矩陣表示的圖
void AdjMatrix::bfsMatrix(bool*& visited,int i,int n,int k2)
{const int MaxLength=30;
 //定義一個(gè)隊(duì)列q,其元素類型應(yīng)為整型
 int q[MaxLength]={0};
 //定義隊(duì)首和隊(duì)尾指針
 int front=0,rear=0;
 //訪問初始點(diǎn)vi
 cout<<g[i]<<':'<<i<<"  ";
 //標(biāo)記初始點(diǎn)vi已訪問過
 visited[i]=true;
  //將已訪問過的初始點(diǎn)序號(hào)i入隊(duì)
 q[++rear]=i;
  //當(dāng)隊(duì)列非空時(shí)進(jìn)行循環(huán)處理
 while(front!=rear) {
  //刪除隊(duì)首元素,第一次執(zhí)行時(shí)k的值為i
  front=(front+1)%MaxLength;
  int k=q[front];
  //依次搜索vk的每一個(gè)可能的鄰接點(diǎn)
  for(int j=0;j<n;j++)
   if(k2==0)
    {if(k!=j&&GA[k][j]!=0&&!visited[j])
     {//訪問一個(gè)未被訪問過的鄰接點(diǎn)vj
      cout<<g[j]<<':'<<j<<"  ";
      visited[j]=true;     //標(biāo)記vj已訪問過
      rear=(rear+1)%MaxLength;//頂點(diǎn)序號(hào)j入隊(duì)
      q[rear]=j;
     }
    }
   else
    if(k!=j&&GA[k][j]!=MaxValue&&!visited[j])
     {//訪問一個(gè)未被訪問過的鄰接點(diǎn)vj
      cout<<g[j]<<':'<<j<<"  ";
      visited[j]=true;   //標(biāo)記vj已訪問過
      rear=(rear+1)%MaxLength;//頂點(diǎn)序號(hào)j入隊(duì)
      q[rear]=j;
     }
}}
//檢查輸入的邊序號(hào)是否越界,若越界則重輸
void AdjMatrix::Check(int n,int& i,int& j)
{while(1) {
  if(i<0||i>=n||j<0||j>=n)
    cout<<"輸入有誤,請(qǐng)重輸!";
  else return;
  cin>>i>>j;
 }
}
//由圖的鄰接矩陣得到圖的鄰接表
void AdjMatrix::graphChange(adjlist &GL,int n,int k2)
{int i,j;
 if(k2==0)
 {for(i=0;i<n;i++){
  for(j=0;j<n;j++)
    if(GA[i][j]!=0) {
     edgenode* p=new edgenode;
     p->adjvex=j;
     p->next=GL[i];GL[i]=p;
     cout<<'('<<i<<','<<p->adjvex<<") ";}
  cout<<endl;}}
 else {
  for(i=0;i<n;i++){
   for(j=0;j<n;j++)
    if(GA[i][j]!=0 && GA[i][j]!=MaxValue) {
     edgenode* p=new edgenode;
     p->adjvex=j;p->weight=GA[i][j];
     p->next=GL[i];GL[i]=p;
     cout<<'('<<i<<','<<p->adjvex<<','<<p->weight<<") ";}
   cout<<endl;}
}}
//創(chuàng)建圖
void AdjMatrix::Creatgraph(int n,int e,RCW r[])
{int i,k;
 for(i=0;i<n;i++) InsertV('A'+i,i);
 for(k=0;k<e;k++)
   InsertEdge(r[k].row,r[k].col,r[k].weight);
}
//取頂點(diǎn)i的值
char AdjMatrix::GetValue(const int i)
{if(i<0||i>size)
  {cerr<<"參數(shù)i越界!\n";exit(1);}
 return g[i];
}
//取弧<v1,v2>的權(quán)
int AdjMatrix::GetWeight(const int v1,const int v2)
{if(v1<0||v1>size||v2<0||v2>size)
  {cerr<<"參數(shù)v1或v2越界!\n";exit(1);}
 return GA[v1][v2]; 
}
//在位置pos處插入頂點(diǎn)V
void AdjMatrix::InsertV(const char &V,int pos)
{int i;
 if(size==MaxV)
  {cerr<<"表已滿,無(wú)法插入!\n";exit(1);}
 if(pos<0||pos>size)
  {cerr<<"參數(shù)pos越界!\n";exit(1);}
 for(i=size;i>pos;i--) g[i]=g[i-1];
 g[pos]=V;
 size++; 
}
//插入弧<v1,v2>,權(quán)為weight
void AdjMatrix::InsertEdge(const int v1,const int v2,int weight)
{if(v1<0||v1>size||v2<0||v2>size)
  {cerr<<"參數(shù)v1或v2越界!\n";exit(1);}
 GA[v1][v2]=weight;
 numE++; 
}
//刪除頂點(diǎn)v與頂點(diǎn)v相關(guān)的所有邊
char AdjMatrix::DeleteVE(const int v)
{for(int i=0;i<size;i++)
  for(int j=0;j<size;j++)
   if((i==v||j==v)&&GA[i][j]>0&&GA[i][j]<MaxValue)
    {GA[i][j]=MaxValue;
     numE--;}
 if(size==0)
  {cerr<<"表已空,無(wú)元素可刪!\n";exit(1);}
 if(v<0||v>size-1)
  {cerr<<"參數(shù)v越界!\n";exit(1);}
 char temp=g[v];
 for(int i=v;i<size-1;i++) g[i]=g[i+1];
 size--;
 g[size]='\0';
 return temp;
}
//刪除弧<v1,v2>
void AdjMatrix::DeleteEdge(const int v1,const int v2)
{if(v1<0||v1>size||v2<0||v2>size||v1==v2)
  {cerr<<"參數(shù)v1或v2出錯(cuò)!\n";exit(1);}
 GA[v1][v2]=MaxValue;
 numE--;
}
//對(duì)非連通圖進(jìn)行深度優(yōu)先搜索
void AdjMatrix::dfsMatrix(int n,int k2)
{bool *vis=new bool[NumV()];
 for(int i=0;i<NumV();i++) vis[i]=false;
 for(int i=0;i<NumV();i++)
  if(!vis[i]) dfsMatrix(vis,i,n,k2);
 delete []vis;
}
//對(duì)非連通圖進(jìn)行廣度優(yōu)先搜索
void AdjMatrix::bfsMatrix(int n,int k2)
{bool *vis=new bool[NumV()];
 for(int i=0;i<NumV();i++) vis[i]=false;
 for(int i=0;i<NumV();i++)
  if(!vis[i]) bfsMatrix(vis,i,n,k2);
 delete []vis;
}