//正确
//现为无向图
//但是一下改成有向图好像有点不对，要琢磨下
#include <iostream>
#include <queue>//
using namespace std;
const int MaxSize =5;
struct ArcNode //边表节点
{
int adjvex;//邻接点域
ArcNode* next;
};
template <class T>
struct VertexNode //定义顶点表节点
{
T vertex;
ArcNode* firstedge;
};
template <class T>
class AdjGraph
{
public:
AdjGraph(T a[],int n,int e); //构造函数，建立具有n个顶点e条边的图
~AdjGraph(){} //析构
void dfs(int v); //深度优先遍历图
void bfs(int v); //广度优先遍历图
//void Insert(int a,int b);//插入边表
void Show(); //显示邻接表
private:
VertexNode<int> adjlist[MaxSize]; //存放顶点表的数组
int vertexNum,arcNum; //图的顶点数和边数
int visited[MaxSize]; //有没访问数组
queue<int> que;//
};
template <class T>
AdjGraph<T>::AdjGraph(T a[],int n,int e)
{
vertexNum = n;
arcNum = e;
for(int i=0;i<vertexNum;i++) //初始化头节点表
{
visited[i]=0;
adjlist[i].vertex = a[i];//存放顶点表的数组
adjlist[i].firstedge=NULL;
}
cout<<"初始化完成."<<endl;
cout<<"请依次输入每条边的两个顶点编号:"<<endl;
for(int k=0;k<arcNum;k++)
{
int i,j;
cin>>i>>j;//输入边所依附的两个顶点的编号
cout<<"输入完成。"<<endl;
ArcNode *s1=new ArcNode;//生成一个边表结点
s1->adjvex=j;
s1->next=adjlist[i].firstedge;//将结点s插入到第i个边表的表头
adjlist[i].firstedge=s1;
//这里画个图理解下
//如果只有上面那个部分的话，就是有向图而不是无向图，注意。
ArcNode *s2=new ArcNode;//生成一个边表结点
s2->adjvex=i;
s2->next=adjlist[j].firstedge;//将结点s插入到第i个边表的表头
adjlist[j].firstedge=s2;
}
}
template <class T>//这个显示部分要好好整理一下
void AdjGraph<T>::Show()
{
cout<<"邻接表为："<<endl;
for(int i = 0; i < vertexNum; i++)
{
cout<<adjlist[i].vertex;//输出顶点表的结点
ArcNode *p=adjlist[i].firstedge;
while(p!=NULL)
{
cout <<"->"<<p->adjvex;//输出改顶点的边表emmmm
p = p->next;
}
cout <<"->NULL"<<endl;
}
}
template <class T>
void AdjGraph<T>::dfs(int v) //深度优先
{
int j=0;
cout<<adjlist[v].vertex<<" ";
visited[v]=1;
ArcNode *p;
p=adjlist[v].firstedge; //工作指针指向顶点v的边表
while(p!=NULL)//依次搜索顶点v的邻接点
{
j = p->adjvex;
if(visited[j]==0) dfs(j);//
p=p->next;
}
}
template <class T>
void AdjGraph<T>::bfs(int v) //广度优先
{
for(int i=0;i<vertexNum;i++)//被访问标记数组的初始化
{
visited[i]=0;
}
cout<<adjlist[v].vertex<<" ";
visited[v]=1;
que.push(v);//先把第一个元素放入队列
while(!que.empty())//队列非空时
{
v=que.front();//获取队头元素并弹出
que.pop();//获取队头元素并弹出
ArcNode *p = adjlist[v].firstedge;//指向顶点v的边表
while(p!=NULL)
{
int j=p->adjvex;//邻接点
if(visited[j]==0)//若没被访问
{
cout<<adjlist[j].vertex<<" ";
visited[j]=1;
que.push(j);
}
p=p->next;
}
}
}
int main()
{
//int a[5] = {0,1,2,3,4};
int a[5];
cout<<"请输入该向图的顶点个数和边的条数:"<<endl;
int num,arc;
cin>>num>>arc;
cout<<"顶点个数和边的条数录入完毕"<<endl;
cout<<endl<<"请录入"<<num<<"个顶点的信息:"<<endl;
for(int numm=0;numm<num;numm++)
{
cout<<"第"<<numm+1<<"个顶点:"<<endl;
cin>>a[numm];//依次输入各个顶点信息
}
cout<<"顶点信息录入完毕。"<<endl;
AdjGraph<int> myGraph(a,num,arc);//构造函数
myGraph.Show();
cout<<endl<<"请输入一个顶点作为深度优先遍历的起始点:"<<endl;
int shen;
cin>>shen;
myGraph.dfs(shen);
cout<<endl;
cout<<endl<<"请输入一个顶点作为广度优先遍历的起始点:"<<endl;
int guang;
cin>>guang;
myGraph.bfs(guang);
cout<<endl;
return 0;
}
