//圖的相關數據類型的定義graph.h
//最多頂點數
const int MaxV=10;
//最大權值
const int MaxValue=99;
//定義鄰接表中的邊結點類型
struct edgenode {
 int adjvex;   //鄰接點域
 int weight;   //權值域
 edgenode* next;//指向下一個邊結點的鏈域
};
//定義鄰接表類型
typedef edgenode** adjlist;
//鄰接矩陣類定義
class AdjMatrix
{private:
  char g[MaxV];//頂點信息數組
  int size;//當前頂點數
  int GA[MaxV][MaxV];//定義鄰接矩陣GA
  int numE;//當前邊數
 public:
  //構造函數,初始化圖的鄰接矩陣
  AdjMatrix(int n,int k2);
  //判斷圖空否
  bool GraphEmpty() {return size==0;}
  //取當前頂點數
  int NumV() {return size;}
  //取當前邊數
  int NumEdges() {return numE;}
  //取頂點i的值
  char GetValue(const int i);
  //取弧<v1,v2>的權
  int GetWeight(const int v1,const int v2);
  //在位置pos處插入頂點V
  void InsertV(const char &V,int pos);
  //插入弧<v1,v2>,權為weight
  void InsertEdge(const int v1,const int v2,int weight);
  //刪除頂點i與頂點i相關的所有邊
  char DeleteVE(const int i);
  //刪除弧<v1,v2>
  void DeleteEdge(const int v1,const int v2);
  //建立圖的鄰接矩陣
  void CreateMatrix(int n, int k1,int k2);
  //k1為0則無向否則為有向,k2為0則無權否則為有權
  //從初始點vi出發深度優先搜索由鄰接矩陣表示的圖
  void dfsMatrix(bool*& visited,int i,int n,int k2);
  //從初始點vi出發廣度優先搜索由鄰接矩陣表示的圖
  void bfsMatrix(bool*& visited,int i,int n,int k2);
  //由圖的鄰接矩陣得到圖的鄰接表
  void graphChange(adjlist &GL,int n,int k2);
  //檢查輸入的邊序號是否越界,若越界則重輸
  void Check(int n,int& i,int& j);
  //由圖的鄰接矩陣建立圖
  void Creatgraph(int n,int k2);
  //對非連通圖進行深度優先搜索
  void dfsMatrix(int n,int k2);
  //對非連通圖進行廣度優先搜索
  void bfsMatrix(int n,int k2);
};
//圖的相關運算的實現graph.cpp
#include"graph.h"
//構造函數,初始化圖的鄰接矩陣
AdjMatrix::AdjMatrix(int n,int k2)
{int i,j;
 if(k2==0){//初始化無(有)向無權圖
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    GA[i][j]=0;}
 else {//初始化無(有)向有權圖
  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)
//k1為0則無向否則為有向,k2為0則無權否則為有權
{int i,j,k,e,w;
 cout<<"輸入圖的總邊數:";
   cin>>e;
 if(k1==0 && k2==0) { //建立無向無權圖
  cout<<"輸入"<<e<<"條無向無權邊的起點和終點序號!"<<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) { //建立無向有權圖
   cout<<"輸入"<<e<<"條無向帶權邊的起點和終點序號及權值!"<<endl;
   for(k=1; k<=e; k++) {
    cin>>i>>j>>w;
    Check(n,i,j);
    GA[i][j]=GA[j][i]=w;}
  }
  else if(k1!=0 && k2==0) { //建立有向無權圖
    cout<<"輸入"<<e<<"條有向無權邊的起點和終點序號!"<<endl;
    for(k=1; k<=e; k++) {
     cin>>i>>j;
     Check(n,i,j);
     GA[i][j]=1;}
  }
  else if(k1!=0 && k2!=0) { //建立有向有權圖
    cout<<"輸入"<<e<<"條有向有權邊的起點和終點序號及權值!"<<endl;
    for(k=1; k<=e; k++) {
     cin>>i>>j>>w;
     Check(n,i,j);
     GA[i][j]=w;}}
  numE=e;   
  cout<<"創建后的鄰接矩陣:\n";   
  for(i=0;i<n;i++)
  {for(j=0;j<n;j++)
    cout<<setw(4)<<GA[i][j];
   cout<<endl;}
}
//從初始點vi出發深度優先搜索由鄰接矩陣表示的圖
void AdjMatrix::dfsMatrix(bool*& visited,int i,int n,int k2)
{cout<<g[i]<<':'<<i<<"  ";
 visited[i]=true;        //標記vi已被訪問過
 for(int j=0; j<n; j++)  //依次搜索vi的每個鄰接點
  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);
}
//從初始點vi出發廣度優先搜索由鄰接矩陣表示的圖
void AdjMatrix::bfsMatrix(bool*& visited,int i,int n,int k2)
{const int MaxLength=30;
 //定義一個隊列q,其元素類型應為整型
 int q[MaxLength]={0};
 //定義隊首和隊尾指針
 int front=0,rear=0;
 //訪問初始點vi
 cout<<g[i]<<':'<<i<<"  ";
 //標記初始點vi已訪問過
 visited[i]=true;
  //將已訪問過的初始點序號i入隊
 q[++rear]=i;
  //當隊列非空時進行循環處理
 while(front!=rear) {
  //刪除隊首元素,第一次執行時k的值為i
  front=(front+1)%MaxLength;
  int k=q[front];
  //依次搜索vk的每一個可能的鄰接點
  for(int j=0;j<n;j++)
   if(k2==0)
    {if(k!=j&&GA[k][j]!=0&&!visited[j])
     {//訪問一個未被訪問過的鄰接點vj
      cout<<g[j]<<':'<<j<<"  ";
      visited[j]=true;     //標記vj已訪問過
      rear=(rear+1)%MaxLength;//頂點序號j入隊
      q[rear]=j;
     }
    }
   else
    if(k!=j&&GA[k][j]!=MaxValue&&!visited[j])
     {//訪問一個未被訪問過的鄰接點vj
      cout<<g[j]<<':'<<j<<"  ";
      visited[j]=true;   //標記vj已訪問過
      rear=(rear+1)%MaxLength;//頂點序號j入隊
      q[rear]=j;
     }
}}
//檢查輸入的邊序號是否越界,若越界則重輸
void AdjMatrix::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 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;}
}}
//由圖的鄰接矩陣建立圖
void AdjMatrix::Creatgraph(int n,int k2)
{int i,j,k,m=0;
 if(k2==0)
 {for(i=0;i<n;i++){
   k=i;
  for(j=0;j<n;j++)
    if(GA[i][j]!=0)
     if(k==i&&m<n)
      {g[m]='A'+m;size++;
       cout<<g[m]<<'('<<i<<','<<j<<") ";
       m++;
      }
  }
  cout<<endl;}
 else {
  for(i=0;i<n;i++){
   k=i;
   for(j=0;j<n;j++)
    if(GA[i][j]!=0 && GA[i][j]!=MaxValue)
     if(k==i&&m<n)
      {g[m]='A'+m;size++;
       cout<<g[m]<<'('<<i<<','<<j<<','<<GA[i][j]<<") ";
       m++;
      }
  }
 cout<<endl;}
 g[n]='\0';
}
//取頂點i的值
char AdjMatrix::GetValue(const int i)
{if(i<0||i>size)
  {cerr<<"參數i越界!\n";exit(1);}
 return g[i];
}
//取弧<v1,v2>的權
int AdjMatrix::GetWeight(const int v1,const int v2)
{if(v1<0||v1>size||v2<0||v2>size)
  {cerr<<"參數v1或v2越界!\n";exit(1);}
 return GA[v1][v2]; 
}
//在位置pos處插入頂點V
void AdjMatrix::InsertV(const char &V,int pos)
{int i;
 if(size==MaxV)
  {cerr<<"表已滿,無法插入!\n";exit(1);}
 if(pos<0||pos>size)
  {cerr<<"參數pos越界!\n";exit(1);}
 for(i=size;i>pos;i--) g[i]=g[i-1];
 g[pos]=V;
 size++; 
}
//插入弧<v1,v2>,權為weight
void AdjMatrix::InsertEdge(const int v1,const int v2,int weight)
{if(v1<0||v1>size||v2<0||v2>size)
  {cerr<<"參數v1或v2越界!\n";exit(1);}
 GA[v1][v2]=weight;
 numE++; 
}
//刪除頂點v與頂點v相關的所有邊
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<<"表已空,無元素可刪!\n";exit(1);}
 if(v<0||v>size-1)
  {cerr<<"參數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<<"參數v1或v2出錯!\n";exit(1);}
 GA[v1][v2]=MaxValue;
 numE--;
}
//對非連通圖進行深度優先搜索
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;
}
//對非連通圖進行廣度優先搜索
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;
}
//圖的相關運算的測試graphM.cpp
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include "graph.cpp"
void main()
{cout<<"graphM.cpp運行結果:\n";
 //定義圖的點數及搜索起始點序號等
 int n,k,i,j;
 //k1為0則無向否則為有向,k2為0則無權否則為有權
 int k1,k2;
 //標記已訪問過的點
 bool *vis;
 //定義鄰接表
 adjlist AL;
 cout<<"輸入圖的點數n=";cin>>n;
 AL=new edgenode*[n];
 vis=new bool[n];
 if(!vis) {cout<<"申請堆內存失敗!\n";exit(1);}
 for(i=0;i<n;i++)
  vis[i]=false;
 cout<<"輸入選擇無向(權)與有向(權)圖的值k1,k2:";
 cin>>k1>>k2;
 //定義鄰接矩陣
 AdjMatrix A(n,k2);
 A.CreateMatrix(n,k1,k2);
 cout<<"出發點Vk的序號=";cin>>k;
 cout<<"\n輸出鄰接矩陣相應圖的每個頂點:\n";
 A.Creatgraph(n,k2);
 cout<<"當前的頂點數為:"<<A.NumV()<<endl;
 cout<<"當前的邊數為:"<<A.NumEdges()<<endl;

 cout<<"圖的深度優先搜索順序:\n";
 A.dfsMatrix(vis,k,n,k2);
 for(i=0;i<n;i++) vis[i]=false;
 cout<<"\n圖的廣度優先搜索順序:\n";
 A.bfsMatrix(vis,k,n,k2);

 cout<<"\n輸出鄰接表的每個鄰接點:\n";
 for(i=0;i<n;i++) vis[i]=false;
 A.graphChange(AL,n,k2);
 delete []vis;

 A.DeleteEdge(0,2);
 A.DeleteEdge(2,0);

 cout<<"當前的頂點數為:"<<A.NumV()<<endl;
 cout<<"當前的邊數為:"<<A.NumEdges()<<endl;
 cout<<"圖的深度優先搜索順序:\n";
 A.dfsMatrix(n,k2);
 cout<<"\n圖的廣度優先搜索順序:\n";
 A.bfsMatrix(n,k2);
 cin.get();cin.get();}
graphM.cpp運行結果:
輸入圖的點數n=7
輸入選擇無向(權)與有向(權)圖的值k1,k2:0  1
輸入圖的總邊數:12
輸入12條無向帶權邊的起點和終點序號及權值!
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
創建后的鄰接矩陣:
   0   1   1  99  99  99  99
   1   0  99   1   1  99  99
   1  99   0  99  99   1   1
  99   1  99   0  99  99  99
  99   1  99  99   0  99  99
  99  99   1  99  99   0  99
  99  99   1  99  99  99   0
出發點Vk的序號=0
輸出鄰接矩陣相應圖的每個頂點:
A(0,1,1) B(0,2,1) C(1,0,1) D(1,3,1) E(1,4,1) F(2,0,1) G(2,5,1) 
當前的頂點數為:7
當前的邊數為:12
圖的深度優先搜索順序:
A:0  B:1  D:3  E:4  C:2  F:5  G:6  
圖的廣度優先搜索順序:
A:0  B:1  C:2  D:3  E:4  F:5  G:6  
輸出鄰接表的每個鄰接點:
(0,1,1) (0,2,1) 
(1,0,1) (1,3,1) (1,4,1) 
(2,0,1) (2,5,1) (2,6,1) 
(3,1,1) 
(4,1,1) 
(5,2,1) 
(6,2,1) 
當前的頂點數為:7
當前的邊數為:10
圖的深度優先搜索順序:
A:0  B:1  D:3  E:4  C:2  F:5  G:6  
圖的廣度優先搜索順序:
A:0  B:1  D:3  E:4  C:2  F:5  G:6