//圖的相關(guān)數(shù)據(jù)類型的定義graph1.h
//最多頂點(diǎn)數(shù)
const int MaxV=10;
//定義鄰接表中的邊結(jié)點(diǎn)類型
struct edgenode {
 int adjvex;     //鄰接點(diǎn)域
 int weight;     //權(quán)值域
 edgenode* next; //指向下一個(gè)邊結(jié)點(diǎn)的鏈域
 edgenode(){}
 edgenode(int d,int w):adjvex(d),weight(w),next(NULL){}
};
struct Top //頂點(diǎn)數(shù)組的元素類型
{char data;//頂點(diǎn)數(shù)據(jù)
 edgenode *adj;//鄰接表指針
};
struct RCW
{int row;
 int col;
 int weight;
};
//鄰接表的類定義
class AdjAdjoin
{private:
  Top g[MaxV];//頂點(diǎn)數(shù)組
  int size;   //頂點(diǎn)個(gè)數(shù)
  int numE;   //當(dāng)前邊的條數(shù)
 public:
  edgenode **GL;//定義鄰接表
  //構(gòu)造函數(shù)
  AdjAdjoin() {}
  //構(gòu)造函數(shù),初始化圖的鄰接表
  AdjAdjoin(edgenode **gl,int n);
  //判斷圖空否
  bool GraphEmpty() {return size==0;}
  //取當(dāng)前頂點(diǎn)數(shù)
  int NumV() {return size;}
  //取當(dāng)前邊數(shù)
  int NumEdges() {return numE;}
  //取頂點(diǎn)i的值
  char GetValue(const int i);
  //取弧<v1,v2>的權(quán)
  int GetWeight(const int v1,const int v2);
  //在位置pos處插入頂點(diǎn)V
  void InsertV(const char &V);
  //插入弧<v1,v2>,權(quán)為weight
  void InsertEdge(const int v1,const int v2,int weight);
  //刪除頂點(diǎn)i與頂點(diǎn)i相關(guān)的所有邊
  void DeleteVE(const int v);
  //刪除弧<v1,v2>
  void DeleteEdge(const int v1,const int v2);
  //刪除圖的鄰接表
  void DeleteAdjoin(int n);
  //建立圖
  void CreatGraph(char V[],int n,RCW E[],int e);
  //建立圖的鄰接表
  void CreateAdjoin(int n,int k1,int k2,RCW rcw[]);
  //從初始點(diǎn)vi出發(fā)深度優(yōu)先搜索由鄰接表GL表示的圖
  void dfsAdjoin(bool*& visited,int i,int n);
  //從初始點(diǎn)vi出發(fā)廣度優(yōu)先搜索由鄰接表GL表示的圖
  void bfsAdjoin(bool*& visited,int i,int n);
  //檢查輸入的邊序號(hào)是否越界,若越界則重輸
  void Check(int n,int& i,int& j);
   //對(duì)非連通圖進(jìn)行深度優(yōu)先搜索
  void dfsAdjoin(int n);
  //對(duì)非連通圖進(jìn)行廣度優(yōu)先搜索
  void bfsAdjoin(int n);
};
//圖的相關(guān)運(yùn)算的實(shí)現(xiàn)graph1.cpp
#include"graph1.h"
//構(gòu)造函數(shù),初始化圖的鄰接表
AdjAdjoin::AdjAdjoin(edgenode **gL,int n)
{GL=gL;
 for(int i=0;i<n;i++)
  {g[i].adj=GL[i]=NULL;}
 size=numE=0;
}
//建立圖的鄰接表
void AdjAdjoin::CreateAdjoin(int n,int k1,int k2,RCW rcw[])
{int i,j,k,e,w;
 cout<<"輸入圖的總邊數(shù):";
  cin>>e;
 if(k1==0 && k2==0) {  //建立無向無權(quán)圖
   cout<<"輸入"<<e
       <<"條無向無權(quán)邊的起點(diǎn)和終點(diǎn)序號(hào)!"<<endl;
   for(k=1; k<=e; k++) {
    cin>>i>>j;
    Check(n,i,j);
   //向序號(hào)i的單鏈表的表頭插入一個(gè)邊結(jié)點(diǎn)
   edgenode *p=new edgenode;
   p->adjvex=j; p->weight=1;
   p->next=GL[i];
   GL[i]=p;//向序號(hào)j的單鏈表的表頭插入一個(gè)邊結(jié)點(diǎn)
   p=new edgenode;
   p->adjvex=i; p->weight=1;
   cout<<'('<<p->adjvex<<','<<j<<','<<p->weight<<")\n";
   p->next=GL[j];
   GL[j]=p;}
 }
 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=rcw[k].row;j=rcw[k].col;w=rcw[k].weight;
    //cin>>i>>j>>w;
    Check(n,i,j);
   //向序號(hào)i的單鏈表的表頭插入一個(gè)邊結(jié)點(diǎn)
   edgenode *p=new edgenode;
   p->adjvex=j; p->weight=w;
   p->next=GL[i];
   GL[i]=p;
   //向序號(hào)j的單鏈表的表頭插入一個(gè)邊結(jié)點(diǎn)
   p=new edgenode;
   p->adjvex=i;p->weight=w;
   p->next=GL[j];
   GL[j]=p;}
 }
 else if(k1!=0&&k2==0) {  //建立有向無權(quán)圖
   cout<<"輸入"<<e<<"條有向無權(quán)邊的起點(diǎn)和終點(diǎn)序號(hào)!"<<endl;
   for(k=1; k<=e; k++) {
    cin>>i>>j;
    Check(n,i,j);
    //向序號(hào)i的單鏈表的表頭插入一個(gè)邊結(jié)點(diǎn)
    edgenode* p=new edgenode;
    p->adjvex=j; p->weight=1;
    p->next=GL[i];
    GL[i]=p;}
 }
 else if(k1!=0&&k2!=0) {  //建立有向有權(quán)圖
   cout<<"輸入"<<e
       <<"條有向有權(quán)邊的起點(diǎn)和終點(diǎn)序號(hào)及權(quán)值!"<<endl;
   for(k=1; k<=e; k++) {
    cin>>i>>j>>w;
    Check(n,i,j);
    edgenode* p=new edgenode;
    p->adjvex=j; p->weight=w;
    p->next=GL[i];
    GL[i]=p;}}
 numE=e;size=n;   
}
//從初始點(diǎn)vi出發(fā)深度優(yōu)先搜索由鄰接表GL表示的圖
void AdjAdjoin::dfsAdjoin(bool*& visited,int i,int n)
{cout<<g[i].data<<':'<<i<<"  ";
 visited[i]=true;
 //取vi鄰接表的表頭指針
 edgenode *p=GL[i];
 //依次搜索vi的每個(gè)鄰接點(diǎn)
 while (p!=NULL) {
   int j=p->adjvex;//j為vi的一個(gè)鄰接點(diǎn)序號(hào)
   if(!visited[j])
   dfsAdjoin(visited,j,n);
   p=p->next;  //使p指向vi單鏈表的下一個(gè)邊結(jié)點(diǎn)
}}
//從初始點(diǎn)vi出發(fā)廣度優(yōu)先搜索由鄰接表GL表示的圖
void AdjAdjoin::bfsAdjoin(bool*& visited,int i,int n)
{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].data<<':'<<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鄰接表的表頭指針
  edgenode* p=GL[k];
  while(p!=NULL)
    {//依次搜索vk的每一個(gè)鄰接點(diǎn)
     int j=p->adjvex;  //vj為vk的一個(gè)鄰接點(diǎn)
     if(!visited[j]) { //若vj沒有被訪問過則進(jìn)行處理
       cout<<g[j].data<<':'<<j<<"  ";
       visited[j]=true;
       rear=(rear+1)%MaxLength;//頂點(diǎn)序號(hào)j入隊(duì)
       q[rear]=j;}
       p=p->next; //使p指向vk鄰接表的下一個(gè)邊結(jié)點(diǎn)
}}}
//檢查輸入的邊序號(hào)是否越界,若越界則重輸
void AdjAdjoin::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;
 }
}
//取頂點(diǎn)i的值
char AdjAdjoin::GetValue(const int i)
{if(i<0||i>size)
  {cerr<<"參數(shù)i越界!\n";exit(1);}
 return g[i].data;
}
//取弧<v1,v2>的權(quán)
int AdjAdjoin::GetWeight(const int v1,const int v2)
{if(v1<0||v1>size||v2<0||v2>size)
  {cerr<<"參數(shù)v1或v2越界!\n";exit(1);}
 edgenode *p=g[v1].adj;
 while(p!=NULL&&p->adjvex<v2) p=p->next;
 if(v2!=p->adjvex)
  {cerr<<"邊<v1,v2>不存在!\n";exit(1);}
 return p->weight; 
}
//在位置pos處插入頂點(diǎn)V
void AdjAdjoin::InsertV(const char &V)
{g[size].data=V;
 size++; 
}
//插入弧<v1,v2>,權(quán)為weight
void AdjAdjoin::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);}
 edgenode *q=new edgenode(v2,weight);
 //q->adjvex=v2;q->weight=weight;
 if(g[v1].adj==NULL) //第一次插入
  g[v1].adj=q;
 else                //非第一次插入
  {edgenode *curr=g[v1].adj,*pre=NULL;
   while(curr!=NULL&&curr->adjvex<v2)
   {pre=curr;
    curr=curr->next;
   }
   if(pre==NULL)    //在第一個(gè)結(jié)點(diǎn)前插入
    {q->next=g[v1].adj;
     g[v1].adj=q;
    }
   else            //在其他位置插入
    {q->next=pre->next;
     pre->next=q;
    }
  }
 numE++; 
}
//刪除頂點(diǎn)v與頂點(diǎn)v相關(guān)的所有邊
void AdjAdjoin::DeleteVE(const int v)
{edgenode *pre,*curr;
 for(int i=0;i<size;i++)
 {pre=NULL;       //刪除頂點(diǎn)v的入邊
  curr=g[i].adj;
  while(curr!=NULL&curr->adjvex<v)
  {pre=curr;
   curr=curr->next;
  }
  if(pre==NULL&&curr->adjvex==v)
   {g[i].adj=curr->next; //該出邊結(jié)點(diǎn)是鏈表的第一結(jié)點(diǎn)時(shí)
    delete curr;
    numE--;
   }
  else if(curr!=NULL&&curr->adjvex==v)
   {pre->next=curr->next;//該出邊結(jié)點(diǎn)是鏈表的其他結(jié)點(diǎn)時(shí)
    delete curr;
    numE--;
   }
 }
 edgenode *p=g[v].adj,*q;
 for(int i=v;i<size-1;i++)
  g[i]=g[i+1]; //刪除數(shù)組的頂點(diǎn)v元素
 numE--;
 while(p!=NULL)//刪除頂點(diǎn)v的所有出邊
 {q=p->next;
  delete p;    //釋放空間
  p=q;
  numE--;
 }
}
//刪除弧<v1,v2>
void AdjAdjoin::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);}
 edgenode *curr=g[v1].adj,*pre=NULL;
  while(curr!=NULL&curr->adjvex<v2)
  {pre=curr;
   curr=curr->next;
  }
  if(pre==NULL&&curr->adjvex==v2)//要?jiǎng)h除的結(jié)點(diǎn)是鏈表的第一結(jié)點(diǎn)
   {g[v1].adj=curr->next;
    delete curr;
    numE--;
   }
  else if(curr!=NULL&&curr->adjvex==v2)//不是鏈表的第一結(jié)點(diǎn)
   {pre->next=curr->next;
    delete curr;
    numE--;
   }
  else
   {cerr<<"邊<v1,v2>不存在!\n";exit(1);}
}
//刪除圖的鄰接表
void AdjAdjoin::DeleteAdjoin(int n)
{int i;
 edgenode* p;
 for(i=0;i<n;i++)
 {p=GL[i];
  while(p!=NULL)
   {GL[i]=p->next;
    delete p;p=GL[i];
   }
 }
 delete []GL;
}
//對(duì)非連通圖進(jìn)行深度優(yōu)先搜索
void AdjAdjoin::dfsAdjoin(int n)
{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]) dfsAdjoin(vis,i,n);
 delete []vis;
}
//對(duì)非連通圖進(jìn)行廣度優(yōu)先搜索
void AdjAdjoin::bfsAdjoin(int n)
{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]) bfsAdjoin(vis,i,n);
 delete []vis;
}
void AdjAdjoin::CreatGraph(char V[],int n,RCW E[],int e)
{for(int i=0;i<n;i++) InsertV(V[i]);
 for(int k=0;k<e;k++)
  InsertEdge(E[k].row,E[k].col,E[k].weight);
 cout<<"輸出建立的圖:\n";
 for(int i=0;i<n;i++)
  cout<<g[i].data<<"  ";
 cout<<endl;  
}  
//圖的相關(guān)運(yùn)算的測試graph1M.cpp
#include<iostream.h>
#include<iomanip.h>
#include "graph1.cpp"
void main()
{cout<<"graph1M.cpp運(yùn)行結(jié)果:\n";
 char a[]={'A','B','C','D','E','F','G'};
 RCW rcw[]={{0,1,1},{0,2,1},{1,3,1},{1,4,1},{2,5,1},
  {2,6,1},{1,0,1},{2,0,1},{3,1,1},{4,1,1},{5,2,1},{6,2,1}};
 //定義圖的點(diǎn)數(shù)及搜索起始點(diǎn)序號(hào)等
 int n,k,i,j;
 //k1為0則無向否則為有向,k2為0則無權(quán)否則為有權(quán)
 int k1,k2;
 //標(biāo)記已訪問過的點(diǎn)
 bool *vis;
 cout<<"輸入圖的點(diǎn)數(shù)n=";cin>>n;
 vis=new bool[n];
 if(!vis) {cout<<"申請(qǐng)堆內(nèi)存失敗!\n";exit(1);}
 for(i=0;i<n;i++) vis[i]=false;
 cout<<"輸入選擇無向(權(quán))與有向(權(quán))圖的值k1,k2:";
 cin>>k1>>k2;
 edgenode **gl=new edgenode*[n];
 AdjAdjoin B(gl,n);
 B.CreatGraph(a,n,rcw,12);
 cout<<"創(chuàng)建鄰接表:\n";
 B.CreateAdjoin(n,k1,k2,rcw);
 cout<<"出發(fā)點(diǎn)Vk的序號(hào)=";cin>>k;
 cout<<"當(dāng)前的頂點(diǎn)數(shù)為:"<<B.NumV()<<endl;
 cout<<"當(dāng)前的邊數(shù)為:"<<B.NumEdges()<<endl;
 cout<<"表的深度優(yōu)先搜索順序:\n";
 B.dfsAdjoin(vis,k,n);cout<<endl;
 cout<<"表的廣度優(yōu)先搜索順序:\n";
 for(i=0;i<n;i++) vis[i]=false;
 B.bfsAdjoin(vis,k,n);cout<<endl;

 B.DeleteEdge(0,2);
 B.DeleteEdge(2,0);
 cout<<"當(dāng)前的頂點(diǎn)數(shù)為:"<<B.NumV()<<endl;
 cout<<"當(dāng)前的邊數(shù)為:"<<B.NumEdges()<<endl;
 cout<<"表的深度優(yōu)先搜索順序:\n";
 B.dfsAdjoin(n);cout<<endl;
 cout<<"表的廣度優(yōu)先搜索順序:\n";
 for(i=0;i<n;i++) vis[i]=false;
 B.bfsAdjoin(n);cout<<endl;
 B.DeleteAdjoin(n);
 cin.get();cin.get();}
graph1M.cpp運(yùn)行結(jié)果:
輸入圖的點(diǎn)數(shù)n=7
輸入選擇無向(權(quán))與有向(權(quán))圖的值k1,k2:0  1
輸出建立的圖:
A  B  C  D  E  F  G  
創(chuàng)建鄰接表:
輸入圖的總邊數(shù):12
輸入12條無向帶權(quán)邊的起點(diǎn)和終點(diǎn)序號(hào)及權(quán)值!
出發(fā)點(diǎn)Vk的序號(hào)=0
當(dāng)前的頂點(diǎn)數(shù)為:7
當(dāng)前的邊數(shù)為:12
表的深度優(yōu)先搜索順序:
A:0  C:2  G:6  F:5  B:1  E:4  D:3  
表的廣度優(yōu)先搜索順序:
A:0  C:2  B:1  G:6  F:5  E:4  D:3  
當(dāng)前的頂點(diǎn)數(shù)為:7
當(dāng)前的邊數(shù)為:10
表的深度優(yōu)先搜索順序:
A:0  C:2  G:6  F:5  B:1  E:4  D:3  
表的廣度優(yōu)先搜索順序:
A:0  C:2  B:1  G:6  F:5  E:4  D:3