/无向图
//正确，无向图可以改成有向图\
//如果用模板，要记得
//template <class T>
//void Mgra<T>::BFS(int v)
//{
//
//}
#include<iostream>
using namespace std;
const int Maxsize=10;//图中最多的顶点个数
//template <class T>
class Mgra
{
public:
Mgra();//构造函数，建立具有n个顶点e条边的图
~Mgra(){}//析构函数为空
void DFS(int v);//深度优先遍历图
void BFS(int v);//广度优先遍历图
void guilin();//将visited重新置0,这个一定不要遗漏！！！
private:
int vertex[Maxsize];//存放图中顶点的数组编号
int arc[Maxsize][Maxsize];//存放图中边的数组
int vertexnum,arcnum;//图中的顶点数和边数
int visited[Maxsize];//记录是否访问
};
//template <class T>
Mgra::Mgra()//前面不加void
{
//int a[Maxsize];
int n,e;
cout<<"请输入顶点数和边数:"<<endl;
cin>>n>>e;//n个顶点，e条边
cout<<"请依次输入各个顶点信息:"<<endl;
vertexnum=n;//顶点数
arcnum=e;//边数
for(int i=0;i<vertexnum;i++)
{
cin>>vertex[i];
visited[i]=0;//标记是否放问，初始化为0
}
for(int i=0;i<vertexnum;i++)//初始化邻接矩阵
{
for(int j=0;j<vertexnum;j++)
{
arc[i][j]=0;
}
}
cout<<"请输入该无向图各边对应的两个顶点，不用重复输入:"<<endl;
for(int k=0;k<arcnum;k++)//依次输入每一条边
{
int i,j;
cin>>i>>j;//输入边依附的两个顶点的编号
//cout<<"111"<<endl;
arc[i][j]=1;
arc[j][i]=1;//该无向图置有边标志
}
}
void Mgra::guilin()
{
for(int i=0;i<vertexnum;i++)
{
visited[i]=0;//标记是否放问，初始化为0
}
}
//template <class T>
void Mgra::DFS(int v)//深度优先遍历
{
cout<<vertex[v]<<" ";//遍历顶点
visited[v]=1;//已经访问了，对应的visited数组元素置为1
for(int j=0;j<vertexnum;j++)
{
if(arc[v][j]==1&&visited[j]==0)//以此顶点的邻接顶点且未被访问
{
DFS(j);//递归
}
}
}
//template <class T>
void Mgra::BFS(int v)//广度优先遍历
{
int front,rear;
int Q[vertexnum];
front=rear=-1;//初始化队列，假设队列采用顺序存储且不会发生溢出
cout<<vertex[v]<<" ";//vertex是存放顶点的数组
visited[v]=1;//标记
Q[++rear]=v;//当访问顶点入队
while(front!=rear)//当队列非空时
{
v=Q[++front];//将队头元素出队并送到V中
for(int j=0;j<vertexnum;j++)
{
if(arc[v][j]==1&&visited[j]==0)
{
cout<<vertex[j]<<" ";
visited[j]=1;
Q[++rear]=j;
}
}
}
}
int main()
{
Mgra mgra;
int ding,dian;
cout<<endl<<"请输入任意顶点作为起始进行深度优先遍历:"<<endl;
cin>>ding;
mgra.DFS(ding);
mgra.guilin();//将标记数组重新置为0
cout<<endl<<"请输入任意顶点作为起始进行广度优先遍历:"<<endl;
cin>>dian;
mgra.BFS(dian);
mgra.guilin();//将标记数组重新置为0
return 0;
}
网友评论