作者:
Phinecos(洞庭散人) 來源:
博客園 發布時間: 2008-08-16 22:25 閱讀: 766 次 推薦: 0
原文鏈接 [收藏]
const int MAXSIZE = 50; //頂點最大數目
#include <vector>
using namespace std;
template<typename T>
class CGraph
{
public:
CGraph(void);
~CGraph(void);
private:
vector<T> vecNodes;//頂點列表
int edge[MAXSIZE][MAXSIZE];//邊表
int numVertexs;//頂點數
int numEdges;//邊數
bool visited[MAXSIZE];//用于圖的遍歷
int FindVertex(const T& vertex,const vector<T> &lst);
void ClearVisitFlag();
vector<T>& GraphDepthFirstSearch(const T& beginVertex);//深度遍歷圖
vector<T>& GraphBreadthFirstSearch();//廣度遍歷
public:
bool GraphEmpty(void)const;
bool GraphFull(void)const;
int NumberOfVertices(void)const;//獲取頂點數
int NumberOfEdges(void)const;//獲取邊數
int GetWeight(const T&vertex1,const T& vertex2);//獲取指定兩個頂點間的權值
vector<T>& GetNeighbors(const T& vertex);//獲取指定頂點的鄰接頂點
void CreateGraph();//創建圖
int GetVertexPos(const T& vertex);//獲取指定頂點的位置
int InsertVertex(const T& vertex);//插入頂點
void InsertEdge(const T& vertex1,const T& vertex2,int weight);//插入邊
void DeleteVertex(const T& vertex);//刪除頂點
void DeleteEdge(const T& vertex1,const T& vertex2);//刪除邊
//int MinimumPath(const T& sVertex,const T& desVertex);最短路徑
void DepthFirstSearch();//深度遍歷圖
void BreadthFirstSearch();//廣度遍歷圖
};
圖的實現代碼
#include "Graph.h"
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
template<typename T>
CGraph<T>::CGraph(void)
{
for (int i=0;i<MAXSIZE;++i)
{
for (int j=0;j<MAXSIZE;++j)
{
this->edge[i][j] = 0;
}
}
this->numVertexs = 0;
this->numEdges = 0;
}
template<typename T>
CGraph<T>::~CGraph(void)
{
this->vecNodes.clear();
for (int i=0;i<MAXSIZE;++i)
{
for (int j=0;j<MAXSIZE;++j)
{
this->edge[i][j] = 0;
}
}
this->numVertexs = 0;
this->numEdges = 0;
}
template<typename T>
int CGraph<T>::NumberOfEdges()const
{
return this->numEdges;
}
template<typename T>
int CGraph<T>::NumberOfVertices()const
{
return this->numVertexs;
}
template<typename T>
int CGraph<T>::GetWeight(const T&vertex1,const T& vertex2)
{
int pos1,pos2;
pos1 = this->GetVertexPos(vertex1);
pos2 = this->GetVertexPos(vertex2);
return this->edge[pos1][pos2];
}
template<typename T>
bool CGraph<T>::GraphFull()const
{
return this->numVertexs>=MAXSIZE;
}
template<typename T>
bool CGraph<T>::GraphEmpty()const
{
return this->numVertexs==0;
}
template<typename T>
int CGraph<T>::InsertVertex(const T& vertex)
{//插入頂點,返回插入位置
int result=-1;
if (!this->GraphFull())
{
this->vecNodes.push_back(vertex);
result = this->numVertexs;
this->numVertexs++;
}
}
template<typename T>
void CGraph<T>::InsertEdge(const T& vertex1,const T& vertex2,int weight)
{//插入邊
int pos1,pos2;
pos1 = this->GetVertexPos(vertex1);
pos2 = this->GetVertexPos(vertex2);
if (pos1==-1&&pos2==-1)
{//兩個都是新頂點
pos1 = this->InsertVertex(vertex1);
pos2 = this->InsertVertex(vertex2);
}
else if (pos1==-1)
{//一個是新頂點
pos1 = this->InsertVertex(vertex1);
}
else if (pos2==-1)
{
pos2 = this->InsertVertex(vertex2);
}
this->edge[pos1][pos2] = weight;
this->edge[pos2][pos1] = weight;
}
template<typename T>
void CGraph<T>::DeleteVertex(const T& vertex)
{//刪除頂點
int pos = this->GetVertexPos(vertex);
if (pos!=-1)
{
this->vecNodes.erase(remove(this->vecNodes.begin(),this->vecNodes.end(),vertex),this->vecNodes.end());//刪除頂點
for (int i=0;i<this->numVertexs;++i)
{
if(this->edge[pos][i]>0)
this->edge[pos][i] = 0;
if (this->edge[i][pos]>0)
this->edge[i][pos] = 0;
}
this->numVertexs--;
this->numEdges--;
}
}
template<typename T>
void CGraph<T>::DeleteEdge(const T& vertex1,const T& vertex2)
{//刪除邊
int pos1,pos2;
pos1 = this->GetVertexPos(vertex1);
pos2 = this->GetVertexPos(vertex2);
if (pos1!=-1&&pos2!=-1)
{
if (this->edge[pos1][pos2]>0)
{
this->edge[pos1][pos2] = 0;
this->edge[pos2][pos1] = 0;
this->numEdges--;
}
}
}
template<typename T>
void CGraph<T>::CreateGraph()
{//創建圖
cout<<"輸入頂點數，邊數: ";
cin>>this->numVertexs;
cin>>this->numEdges;
int i;
T item;
cout<<"輸入頂點: ";
for (i=0;i<this->numVertexs;++i)
{
cout<<"第"<<i+1<<"個頂點: ";
cin>>item;
this->vecNodes.push_back(item);
}
T vert1,vert2;
int pos1,pos2,weight;
for (i=0;i<this->numEdges;++i)
{
cout<<"輸入第"<<i+1<<"條邊(尾，頭，權值): ";
cin>>vert1>>vert2>>weight;
pos1 = this->GetVertexPos(vert1);
pos2 = this->GetVertexPos(vert2);
this->edge[pos1][pos2] = weight;
this->edge[pos2][pos1] = weight;
}
}
template<typename T>
int CGraph<T>::GetVertexPos(const T& vertex)
{//獲取頂點位置
return this->FindVertex(vertex,this->vecNodes);
}
template<typename T>
int CGraph<T>::FindVertex(const T &vertex,const vector<T> &lst)
{//在頂點列表中找指定數據的下標
int pos = -1;
for (pos = lst.size()-1;pos>=0;--pos)
{
if (lst[pos]==vertex)
{
break;
}
}
return pos;
}
template<typename T>
vector<T>& CGraph<T>::GraphDepthFirstSearch(const T& beginVertex)
{//深度遍歷
vector<T> *result = new vector<T>();
vector<T> adjLst;
stack<T> s;
s.push(beginVertex);
int pos;
T vertex;
vector<T>::iterator iter;
while (!s.empty())
{
vertex = s.top();
s.pop();
if (this->FindVertex(vertex,*result)==-1)
{
pos = this->GetVertexPos(vertex);
visited[pos] = true;
(*result).push_back(vertex);
adjLst = this->GetNeighbors(vertex);
for ( iter= adjLst.begin();iter != adjLst.end();++iter)
{
if (this->FindVertex(*iter,*result)==-1)
{
s.push(*iter);
}
}
}
}
return *result;
}
template<typename T>
void CGraph<T>::ClearVisitFlag()
{
for (int i=0;i<this->numEdges;++i)
{
this->visited[i] = false;
}
}
template<typename T>
void CGraph<T>::BreadthFirstSearch()
{
vector<T>::const_iterator iter;
vector<int> vec;
this->ClearVisitFlag();
vec = this->GraphBreadthFirstSearch();
for (iter = vec.begin();iter!=vec.end();++iter)
{
cout<<*iter<<" ";
}
this->ClearVisitFlag();
}
template<typename T>
vector<T>& CGraph<T>::GraphBreadthFirstSearch()
{//廣度遍歷
vector<T> *result = new vector<T>();
vector<T> adjLst;
vector<T>::iterator iter;
queue<T> q;
T item;
int pos;
this->ClearVisitFlag();
for (int i=0;i<this->numVertexs;++i)
{
if (!this->visited[i])
{
visited[i] = true;
result->push_back(this->vecNodes[i]);
q.push(this->vecNodes[i]);
while (!q.empty())
{
item = q.front();
q.pop();
adjLst = this->GetNeighbors(item);
for ( iter= adjLst.begin();iter != adjLst.end();++iter)
{
if (this->FindVertex(*iter,*result)==-1)
{
result->push_back(*iter);
pos = this->GetVertexPos(*iter);
visited[pos] = true;
}
}
}
}
}
return *result;
}
template<typename T>
vector<T>& CGraph<T>::GetNeighbors(const T& vertex)
{//獲取鄰接頂點
vector<T> *result;
result = new vector<T>();
int pos = this->GetVertexPos(vertex);
if (pos==-1)
{
cerr<<"頂點不在圖中"<<endl;
return *result;
}
for (int i=0;i<this->numVertexs;++i)
{
if (edge[pos][i]>0)
{
result->push_back(this->vecNodes[i]);
}
}
return *result;
}
template<typename T>
void CGraph<T>::DepthFirstSearch()
{
vector<T>::const_iterator iter,iter2;
int pos;
vector<int> vec1;
this->ClearVisitFlag();
for (iter = this->vecNodes.begin();iter!=this->vecNodes.end();++iter)
{
pos = this->GetVertexPos(*iter);
if (!visited[pos])
{//還未訪問，從這點開始
vec1 = this->GraphDepthFirstSearch(*iter);
for (iter2 = vec1.begin();iter2!=vec1.end();++iter2)
{
cout<<*iter2<<" ";
}
}
}
this->ClearVisitFlag();
}
測試程序：
#include "Graph.cpp"
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
CGraph<int> *graph1 = new CGraph<int>();
graph1->CreateGraph();
graph1->DepthFirstSearch();
graph1->BreadthFirstSearch();
system("pause");
return 0;
} 文章列表
留言列表
