在這篇文章中，我們要討論一下關(guān)于圖的知識(shí)點(diǎn)：
1.圖的存儲(chǔ)方式——鄰接矩陣存儲(chǔ)和鄰接表存儲(chǔ)
*鄰接矩陣存儲(chǔ)code如下所示
#include <iostream>
using namespace std;
template <class T>
class Graph
{
protected:
int n,e; //e是邊數(shù),n是節(jié)點(diǎn)數(shù)
public:
virtual bool GInsert(int u,int v,T w)=0; //圖中在節(jié)點(diǎn)u和v之間插入一條權(quán)值為w的邊
virtual bool GRemove(int u,int v)=0; //刪除圖中節(jié)點(diǎn)u和v之間的邊
virtual bool GExist(int u,int v) const=0; //判斷圖中節(jié)點(diǎn)u和v之間是否存在路徑
};
template <class T>
class MGraph:public Graph<T>
{
protected: //這里用protected權(quán)限是為了未來可能存在的繼承該MGraph的類可以訪問
T **a; //二維數(shù)組指針指向圖的鄰接矩陣
public:
MGraph(int mSize);
~MGraph();
bool GInsert(int u,int v,T w);
bool GRemove(int u,int v);
bool GExist(int u, int v)const;
};
template <class T>
MGraph<T>::MGraph(int mSize) //鄰接矩陣是n*n的大小，即有n個(gè)節(jié)點(diǎn)
{
n=mSize;
a=new T* [n]; //申請(qǐng)一個(gè)大小為n的T*指針類型數(shù)組空間，每個(gè)空間存儲(chǔ)一個(gè)T指針
for(int i=0;i<n;i++) //初始化鄰接矩陣
{
a[i]=new T [n]; //i個(gè)數(shù)組空間中的指針a[i]分別指向一段n連續(xù)的T類型數(shù)組空間
for(int j=0;j<n;j++)
{
a[i][j]=-1; //賦值-1，表明i和j節(jié)點(diǎn)之間沒有邊
}
a[i][i]=0; //節(jié)點(diǎn)無自回路
}
}
template <class T>
MGraph<T>::~MGraph()
{
for(int i=0;i<n;i++)
delete []a[i];
delete []a;
}
template <class T>
bool MGraph<T>::GInsert(int u, int v, T w)
{
if(u<0||v<0||u>n-1||v>n-1)
{
cout<<"節(jié)點(diǎn)值越界"<<endl;
return false;
}
if(a[u][v]!=-1)
{
cout<<"邊已經(jīng)存在"<<endl;
return false;
}
a[u][v]=w;
e++;
return true;
}
template <class T>
bool MGraph<T>::GRemove(int u,int v)
{
if(u<0||v<0||u>n-1||v>n-1)
{
cout<<"節(jié)點(diǎn)值越界"<<endl;
return false;
}
if(a[u][v]==-1)
{
cout<<"要?jiǎng)h除的邊不存在"<<endl;
return false;
}
a[u][v]==-1;
e--;
return true;
}
template <class T>
bool MGraph<T>::GExist(int u, int v) const
{
if(u<0||v<0||u>n-1||v>n-1)
{
cout<<"GExit:節(jié)點(diǎn)越界"<<endl;
return false;
}
if(a[u][v]==-1)
{
cout<<"GExit:邊不存在"<<endl;
return false;
}
cout<<"GExit:邊存在"<<endl;
return true;
}
int main()
{
MGraph<int> a(4);
a.GInsert(0,1,1);
a.GExist(0,2);
return 0;
}
*鄰接表類似于一個(gè)哈希表，鄰接表存儲(chǔ)方式的圖code如下所示
#include <iostream>
using namespace std;
template <class T> class LGraph;
template <class T>
class LNode //鄰接表節(jié)點(diǎn)類
{
private:
int adjVex; //節(jié)點(diǎn)號(hào)
T w; //邊權(quán)值
LNode<T> *nextArc; //節(jié)點(diǎn)指針
public:
LNode(int vertex,T weight,LNode<T> *next)
{
adjVex=vertex;
w=weight;
nextArc=next;
}
friend class LGraph<T>; //友元類LGraph可以訪問類LNode中的private成員
};
template <class T>
class LGraph //鄰接表類
{
private:
LNode<T> **a; //鄰接表二維指針
int n; //圖的節(jié)點(diǎn)數(shù)
int e; //圖的邊數(shù)
public:
LGraph(int mSize);
~LGraph();
bool LExist(int u,int v);
bool LInsert(int u,int v,T w);
bool LRemove(int u,int v);
};
template<class T>
LGraph<T>::LGraph(int mSize) //初始化鄰接表
{
n=mSize;
a=new LNode<T>* [n];
for(int i=0;i<n;i++)
{
a[i]=NULL;
}
}
template<class T>
LGraph<T>::~LGraph()
{
for(int i=0;i<n;i++)
{
delete [] a[i];
}
delete []a;
}
template<class T>
bool LGraph<T>::LExist(int u,int v)
{
if(u<0||v<0||u>n-1||v>n-1)
{
cout<<"LExist：節(jié)點(diǎn)號(hào)越界"<<'\n';
return false;
}
LNode<T> *p=a[u];
while(p)
{
if(p->adjVex==v)
{
cout<<"LExist:存在"<<u<<"-"<<v<<"邊"<<'\n';
return true;
}
p=p->nextArc;
}
if(!p)
return false;
}
template<class T>
bool LGraph<T>::LInsert(int u,int v,T w)
{
if(u<0||v<0||u>n-1||v>n-1)
{
cout<<"LInsert：節(jié)點(diǎn)號(hào)越界"<<'\n';
return false;
}
if(LExist(u,v))
{
cout<<"LInsert:已經(jīng)存在"<<u<<"-"<<v<<"邊"<<'\n';
return false;
}
LNode<T> *p=new LNode<T>(v,w,a[u]);
a[u]=p;
e++;
return true;
}
template<class T>
bool LGraph<T>::LRemove(int u,int v)
{
if(u<0||v<0||u>n-1||v>n-1)
{
cout<<"LRemove：節(jié)點(diǎn)號(hào)越界"<<'\n';
return false;
}
if(!LExist(u,v))
{
cout<<"LRemove:不存在"<<u<<"-"<<v<<"邊"<<'\n';
return false;
}
LNode<T> *p=a[u],*q=NULL;
while(p&&p->adjVex!=v)
{
q=p;
p=p->nextArc;
}
if(!p)
return false;
if(q)
q->nextArc=p->nextArc;
else
a[u]=p->nextArc;
delete p;
e--;
return true;
}
2.圖的深度優(yōu)先遍歷(DFS)，這里我們討論以鄰接表形式存儲(chǔ)的圖如何進(jìn)行深度優(yōu)先遍歷。這里采用了遞歸法，大致思路如下
(1)訪問任意節(jié)點(diǎn)v，并對(duì)v打上已經(jīng)訪問過的標(biāo)記
(2)依次從v的未訪問鄰接點(diǎn)出發(fā)，深度優(yōu)先搜索圖
#include "lgraph.cpp"
//圖的搜索
template <class T>
class ExtLGraph:public LGraph<T>
{
private:
void DFS(int v,bool *visited); //從v節(jié)點(diǎn)出發(fā)深度優(yōu)先搜索，visited是標(biāo)志位數(shù)組指針
//void BFS();
public:
ExtLGraph(int mSize):LGraph<T>(mSize){} //調(diào)用父類的構(gòu)造函數(shù)來初始化子類構(gòu)造函數(shù)
void DFS(); //深度優(yōu)先遍歷
//void BFS(); //寬度優(yōu)先遍歷
};
template <class T>
void ExtLGraph<T>::DFS()
{
bool *visited=new bool [n]; //創(chuàng)建標(biāo)志位數(shù)組
for(int i=0;i<n;i++)
visited[i]=false; //所有標(biāo)志位至false，表明未訪問過
for(int i=0;i<n;i++)
if(!visited[i]) //未訪問過的節(jié)點(diǎn)進(jìn)行深度優(yōu)先搜索遞歸算法
DFS(i,visited);
delete [] visited;
}
template <class T>
void ExtLGraph<T>::DFS(int v,bool *visited)
{
visited[v]=true; //v節(jié)點(diǎn)標(biāo)志位至為true
cout<<" "<<v; //打印輸出訪問到的節(jié)點(diǎn)v
LNode<T> *p=a[v];
while(p)
{
if(!visited[p->adjVex])
DFS(p->adjVex,visited);
p=p->nextArc;
}
}
注意：由于ExtLGraph類是LGraph的子類，由于友元類無法繼承的原因，在ExtLGraph類中無法訪問LNode類中的private成員，因此LNode類中應(yīng)該將ExtLGraph類設(shè)置為友元類?。?！
