#define maxvex 10
#include <iostream>
#include <stack>
using namespace std;
int visit[maxvex];
typedef char vertextype;//结点数据
typedef struct
{
vertextype vexs[maxvex];//顶点表
int arc[maxvex][maxvex];//邻接矩阵
int numnodes,numedges,direction;//顶点数,边数,方向
}graph;
void creatematrix(graph *g)//邻接矩阵
{
int i,j;
vertextype e1,e2;
cout<<"输入顶点和边数"<<endl;
cin>>g->numnodes>>g->numedges;
cout<<"是否为有向图?有向图输入1,无向图输入0"<<endl;
cin>>g->direction;
cout<<"输入各个顶点数据"<<endl;
for(i=0;i<g->numnodes;i++)
cin>>g->vexs[i];//输入每个节点的字符数据到顶点表 vexs[0]=A
for(i=0;i<g->numnodes;i++)
{
for(int j=0;j<g->numnodes;j++)
g->arc[i][j]=0;
}//邻接矩阵初始化
cout<<"请输入每条边的两个顶点结点"<<endl;
for(int k=0;k<g->numedges;k++)//输入边数
{
cin>>e1>>e2;
for(i=0;i<g->numnodes;i++)//根据顶点表查找第一个结点
{
if(g->vexs[i]==e1)
break;
}
for(j=0;j<g->numnodes;j++)//根据顶点表查找第二个结点
{
if(g->vexs[j]==e2)
break;
}
g->arc[i][j]=1;
if(g->direction==0)
g->arc[j][i]=g->arc[i][j];//无向图的邻接矩阵对称
}
cout<<"邻接矩阵建立完成"<<endl;
cout<<"邻接矩阵如下"<<endl;
for(i=0;i<g->numnodes;i++)
{
for(j=0;j<g->numnodes;j++)
cout<<g->arc[i][j];
cout<<endl;
}
}
void matrixoutput(graph g)
{
cout<<"邻接矩阵如下"<<endl;
for(int i=0;i<g.numnodes;i++)
{
for(int j=0;j<g.numnodes;j++)
cout<<g.arc[i][j];
cout<<endl;
}
}
void DFS1(graph g,int i)
{
visit[i]=true;
cout<<g.vexs[i]<<" ";//打印顶点
for(int j=0;j<g.numnodes;j++)//一个连通分量的遍历
if(g.arc[i][j]==1 && !visit[j])
DFS1(g,j);
}
//邻接矩阵的深度遍历
void DFS(graph g)
{
for(int i=0;i<g.numnodes;i++)
visit[i]=0;//初始所有顶点状态都是未访问过状态
for(int i=0;i<g.numnodes;i++)//若是连通图,只会执行一次
if(!visit[i])//对未访问过的顶点调用DFS
DFS1(g,i);
}
void output(stack<int> s)//打印栈内元素
{
stack<int> out;
int e;
while(!s.empty())
{
e=s.top();
s.pop();
out.push(e);
}
while(!out.empty())
{
char b=char(out.top())+65;
cout<<b<<" ";
out.pop();
}
cout<<endl;
}
void way(graph g,vertextype e1,vertextype e2)
{
int visit[g.numnodes];
for(int i=0;i<g.numnodes;i++)
visit[i]=0;
stack<int> s;//栈内为顶点数据的整型
int a=int(e1)-65;//起点
int b=int(e2)-65;//终点
s.push(a);
while(s.top()!=b){
for(int i=0;i<g.numnodes;i++){
if(visit[i]=0 && g.arc[s.top()][i]==1){
s.push(i);
}
}
}
output(s);
while(!s.empty()){
int temp1=s.top();
s.pop();
for(int i=0;i<g.numnodes;i++){
if(visit[i]=0 && g.arc[s.top()][i]==1){
s.push(i);
}
}
if(s.top()==b)
output(s);
visit[temp1]=0;
}
}
main()
{
graph g;
vertextype e1,e2;
creatematrix(&g);
cout<<"对邻接矩阵进行深度优先遍历"<<endl;
DFS(g);
cout<<endl;
cout<<"请输入起点和终点"<<endl;
cin>>e1>>e2;
way(g,e1,e2);
system("pause");
}