#include
using namespace std;
/*********************各类定义******************************/
class Node//基本抽象数据类型
{
public:
char ch; //记录名称，如果将这里改成数组，结点名称可以是多个字符
int flag;//记录结点是否被访问
};
class Graph //图类，此类中，封装了图的一些成员和一些必须的成员函数
{
private:
int getSub(char); //获取某名称的下标
Node* arrNode; //记录名称和是否访问的数组
int numVertex,numEdge;//记录图的顶点数和边数
int matrix; //用一个二维数组记录两点间是否相连，1相连，0断开
public:
void setCh(char,int); //将数组的arrNode的每一个单元设置一个结点名称
Graph(int);
~Graph();
int getNumVertex();//获得图的顶点数
char first(char ch);//获得相邻结点
char next(char ch1,char ch2);//获得隔着ch2，但与ch2相邻的结点
void setEdge(char,char,int w=1);//设置两顶点的边和权重（权重默认为1）
void eraserEdge(char,char);
void outPut();
int getMark(char);//获取是否被访问的记录，已访问返回1，未访问返回0
void setMark(char);//把已访问的结点，设置标记
};
template
class myQueue
{
private:
int theFront; // 1 counterclockwise from theFront element
int theBack; // position of theBack element
int arrayLength; // queue capacity
T queue; // element array
public:
myQueue(int initialCapacity = 10);
~myQueue() {delete [] queue;}
bool empty() const {return theFront == theBack;}
int size() const
{return (theBack - theFront + arrayLength) % arrayLength;}
T& front()
{// return front element
/*if (theFront == theBack)
throw queueEmpty();/
return queue[(theFront + 1) % arrayLength];
}
T& back()
{// return theBack element
/*if (theFront == theBack)
throw queueEmpty();*/
return queue[theBack];
}
void pop()
{// remove theFront element
/*if (theFront == theBack)
throw queueEmpty();*/
theFront = (theFront + 1) % arrayLength;
queue[theFront].~T(); // destructor for T
}
void push(const T& theElement);
};
/***********各函数的函数体*****************************/
Graph::Graph(int n)
{
int i,j;
arrNode=new Node[n];
numVertex=n;
numEdge=0;
for(i=0;i<numVertex;i++)
arrNode[i].flag=0;
matrix=new int*[numVertex];
for(i=0;i<numVertex;i++)
matrix[i]=new int[numVertex];
for(i=0;i<numVertex;i++)
for(j=0;j<numVertex;j++)
matrix[i][j]=matrix[j][i]=0;
}
Graph::~Graph()
{
delete [] arrNode;
for(int i=0;i<numVertex;i++)
delete [] matrix[i];
delete [] matrix;
}
int Graph::getSub(char ch) //获取下标
{
for(int i=0;i<numVertex;i++)
if(ch==arrNode[i].ch)
return i;
}
int Graph::getNumVertex() //获取顶点数
{
return numVertex;
}
char Graph::first(char ch) //获取相邻结点
{
for(int i=0;i<numVertex;i++)
if(matrix[getSub(ch)][i]!=0)
return arrNode[i].ch;
return ch;
}
char Graph::next(char ch1,char ch2) //获取与ch2相邻的结点
{
for(int i=getSub(ch2)+1;i<numVertex;i++)
if(matrix[getSub(ch1)][i]!=0)
return arrNode[i].ch;
return ch1;
}
void Graph::setEdge(char ch1,char ch2,int w) //设置边
{
if(matrix[getSub(ch1)][getSub(ch2)]==0)
{
numEdge++;
matrix[getSub(ch1)][getSub(ch2)]=matrix[getSub(ch2)][getSub(ch1)]=1;
}
}
void Graph::eraserEdge(char ch1,char ch2)
{
if(matrix[getSub(ch1)][getSub(ch2)]==1)
{
numEdge--;
matrix[getSub(ch1)][getSub(ch2)]=matrix[getSub(ch2)][getSub(ch1)]=0;
}
}
void Graph::outPut()
{
for(int i=0;i<numVertex;i++)
{
for(int j=0;j<numVertex;j++)
{
cout<<matrix[i][j]<<" ";
}
cout<<endl<<endl;;
}
}
int Graph::getMark(char ch)//获取访问信息
{
for(int i=0;i<numVertex;i++)
if(ch==arrNode[i].ch)
return arrNode[i].flag;
return -1;
}
void Graph::setMark(char ch) //设置标记
{
for(int i=0;i<numVertex;i++)
if(ch==arrNode[i].ch)
arrNode[i].flag=1;
}
void Graph::setCh(char ch,int n)//将结点名称设置在字符中
{
arrNode[n].ch=ch;
}
template
myQueue::myQueue(int initialCapacity)
{// Constructor.
/*if (initialCapacity < 1)
{ostringstream s;
s << "Initial capacity = " << initialCapacity << " Must be > 0";
throw illegalParameterValue(s.str());
}*/
arrayLength = initialCapacity;
queue = new T[arrayLength];
theFront = 0;
theBack = 0;
}
template
void myQueue::push(const T& theElement)
{// Add theElement to queue.
// increase array length if necessary
if ((theBack + 1) % arrayLength == theFront)
{// double array length
// allocate a new array
T* newQueue = new T[2 * arrayLength];
// copy elements into new array
int start = (theFront + 1) % arrayLength;
if (start < 2)
// no wrap around
copy(queue + start, queue + start + arrayLength - 1, newQueue);
else
{ // queue wraps around
copy(queue + start, queue + arrayLength, newQueue);
copy(queue, queue + theBack + 1, newQueue + arrayLength - start);
}
// switch to newQueue and set theFront and theBack
theFront = 2 * arrayLength - 1;
theBack = arrayLength - 2; // queue size arrayLength - 1
arrayLength *= 2;
queue = newQueue;
}
// put theElement at the theBack of the queue
theBack = (theBack + 1) % arrayLength;
queue[theBack] = theElement;
}
/***************主函数*********************/
void DFS(Graph*,char); //深度优先遍历函数声明
void BFS(Graph*,char,myQueue*); //广度优先遍历函数声明
int main()
{
char option;
int numVer,numE,i;
char temp1,temp2; //temp1,temp2作临时变量，记录输入的值
// myQueue* q=new myQueue;
cout << "输入定点数和弧数：";
cin >> numVer >> numE;
Graph myGraph1(numVer);
Graph myGraph2(numVer);
cout << "请输入" << numVer << "个顶点：\n";
for(i=0;i
{
cout
cin >> temp1;
myGraph1.setCh(temp1,i);
myGraph2.setCh(temp1,i);
}
cout << "请输入" << numE << "条弧：\n";
for(i=0;i
{
cout
cin >> temp1 >> temp2;
myGraph1.setEdge(temp1,temp2);
myGraph2.setEdge(temp1,temp2);
}
myGraph1.outPut();
while(1)
{
cout<<"2:删除边 "<<endl;
cout<<"3: 深度遍历"<<endl;
cout<<"4: 广度遍历"<<endl;
cout<<"0: 退出"<<endl;
cout<<"\n请输入你的选择:";
cin>>option;
switch(option)
{
case'0':
exit(0);
break;
case'2':
{
cout << "输入弧的顶点：" << endl;
cin >> temp1 >> temp2;
myGraph1.eraserEdge(temp1,temp2);
myGraph2.eraserEdge(temp1,temp2);
myGraph1.outPut();
break;
}
case'3':
{
cout << "深度优先结果:";
DFS(&myGraph1,'a');
cout<<endl;
break;
}
case'4':
{
cout << "\n广度优先结果:";
//BFS(&myGraph2,'a',q);
cout<<endl;
break;
}
cout<<endl;
}
}cout<<endl;
}
void DFS(Graph* G,char ch) //深度优先遍历函数体
{
int i=0;
cout << ch << " ";
G->setMark(ch);
for(char w=G->first(ch);igetNumVertex();w=G->next(ch,w),i++)
if(G->getMark(w)==0)
DFS(G,w);
}
void BFS(Graph* G,char ch,myQueue* q) //广度优先遍历函数体
{
char v,w;
q->push(ch);
G->setMark(ch);
while(q->size()!=0)
{
q->pop(v);
cout << v << " ";
int i=0;
for(w=G->first(v);igetNumVertex();w=G->next(v,w),i++)
if(G->getMark(w)==0)
{
G->setMark(w);
q->push(w);
}
}
}
/*输入顶点数和弧数:8 9 输入8个顶点.
输入顶点0:a
输入顶点1:b
输入顶点2:c
输入顶点3:d
输入顶点4:e
输入顶点5:f
输入顶点6:g
输入顶点7:h
输入9条弧.
输入弧0:a b 1
输入弧1:b d 1
输入弧2:b e 1
输入弧3:d h 1
输入弧4:e h 1
输入弧5:a c 1
输入弧6:c f 1
输入弧7:c g 1
输入弧8:f g 1 */
