图的应用

/*在程序设计中更多的是注重程序的逻辑性，因此在设计验证实验程序中，更多的是考虑程序完整性，
也就是在设计程序时有一个清晰地思路，经过认真的研究，对面向对象的程序设计语言的前提下，
对抽象数据类型的了解显得更为重要，在做实验之前更多的是要知道程序的功能，以便设计更为人性化
程序
*/
/*该实验采用邻接矩阵作为存储结构
首先建立以邻接矩阵为存储结构的图的抽象数据类型
方法的实现：对建立的无向图，进行深度及广度优先遍历，因此该实验主要是设计抽象数据类型，
并做好算法的实现与调用。
*/
/*生成树的求解：
生成树可以在图的遍历中得到：
在一个连通无向图G=(V,E)中，如果从任一个顶点开始进行深度优先遍历，必定将边集E分成两个集合T和B,其中T是遍历过程中经历的边的集合，
B是剩余的边的集合。显然，边集T和图G所有顶点一起构成连通图G的一棵生成树。因此，修改深度优先遍历算法，输出遍历所经过的边。
*/

#include<iostream.h>
const int MaxSize=10;
template<class T>
class MGraph
{
public:
   MGraph(T a[],int n,int e);    //构造函数
   ~MGraph() {}                 //析构函数
   void DFSTraverse(int v);      //深度优先遍历
   void DFSTraverse1(int v);     //深度优先非递归算法 ,这里的v代表数组元素的下标
   void DFSTraverse2(int v);
   void DFSTraverseSCH(int v);   //生成树求解，利用深度优先遍历算法改进即可
   void BFSTraverse(int v);      //广度优先遍历
private:
   T vertex[MaxSize];            //存放图中顶点的数组
   int arc[MaxSize][MaxSize];     //存放图中边的数组，邻接存储的核心部分，其取值就是两个顶点之间有没有边相连
   int vertexNum,arcNum;
   int visited[MaxSize];
};
//构造函数
template<class T>
MGraph<T>::MGraph(T a[],int n,int e)
{
vertexNum=n; arcNum=e;
for(int i=0;i<vertexNum;i++)
   vertex[i]=a[i];           //初始化定点数组，将定点数组赋值
for(i=0;i<MaxSize;i++)
   visited[i]=0;
for(i=0;i<vertexNum;i++)       //初始化邻接矩阵
   for(int j=0;j<vertexNum;j++)
    arc[i][j]=0;
for(int k=0;k<arcNum;k++)      //程序在此处跳转的原因是，arcNum赋给的初值为零
{  
   int i,j;
   cout<<"请输入两位正整数："<<endl;
   cin>>i>>j;
   arc[i][j]=1;
   arc[j][i]=1;               //由于其为无向图邻接矩阵，矩阵关于对角线对称
}
}
template<class T>
void MGraph<T>::DFSTraverse(int v)    //深度优先遍历递归算法
{
//int visited[MaxSize];               //visited[数组一定要初始化】,初始化问题是一个相当重要的问题，在下面的判断语句中，其显得尤为重要，不然的话程序将跳出循环，不向下执行
/*for(int i=0;i<MaxSize;i++)
   visited1[i]=0;*/
cout<<vertex[v]<<" ";                //visited 数组不能再这里进行初始化，递归调用将使数组不断地初始化，陷入死循环
visited[v]=1;
   for(int j=0;j<vertexNum;j++)
{ if(arc[v][j]==1&&visited[j]==0)
     DFSTraverse(j);
}
}
template<class T>
void MGraph<T>::DFSTraverse1(int v)
{
int s[MaxSize];
int visited1[MaxSize];
for(int i=0;i<MaxSize;i++)
   visited1[i]=0;
int top=-1;
cout<<vertex[v]<<" ";
visited1[v]=1;
s[++top]=v;               //利用栈的思想
while(top!=-1)
{
   v=s[top];              //初步调试是栈顶元素无法取出，v没有进栈
   for(int j=0;j<vertexNum;j++)
    if(arc[v][j]==1&&visited1[j]==0)
    {
     cout<<vertex[j]<<" ";
     visited1[j]=1; //这里的visited1该函数中的visited独立与主函数中的visited数组
     s[++top]=j;
     //break;
    }
    if(j==vertexNum) top--;
}
}
/*在这个算法中我们需要注意的是：visited1数组的记录问题，由于在类中已经定义了一个visited数组，一定要区别两者，在编写程序运行无误后，并不等于我们就已经成功，我
要做的还要验证程序是否符合运算的结果，在调试程序的过程中，寻找到这种方法，我们才能在编写程序中寻找到乐趣。在非递归算法中一定要理解栈的概念，它能帮助你理解程序的逻辑性
在调试程序总起着至关重要的作用*/
template<class T>
void MGraph<T>::DFSTraverse2(int v)
{
int s[MaxSize];
int visited1[MaxSize];
for(int i=0;i<MaxSize;i++)
   visited1[i]=0;
int top=-1;
cout<<vertex[v]<<" ";
visited1[v]=1;        //这里的visited1为正确，在以后的程序中其没有任何变化
s[++top]=v;               //利用栈的思想
while(top!=-1)
{
   v=s[top];              //初步调试是栈顶元素无法取出，v没有进栈； 问题的关键是让最开始的顶点出栈
   for(int j=0;j<vertexNum;j++)
   { if(arc[v][j]==1&&visited1[j]==0)
    {
     //cout<<vertex[j]<<" ";
     cout<<"("<<v<<j<<")"<<" ";
     visited1[j]=1; //这里的visited1该函数中的visited独立与主函数中的visited数组
     s[++top]=j;
     //break;
    }
    //if(j==vertexNum) top--;
   }
  
   if(top>0)      //此函数设计是让栈顶元素无法出栈
   {
    cout<<vertex[s[top]]<<" ";
    top--;
   }
   if(top==0)
    top--;
}
}
template<class T>
void MGraph<T>::DFSTraverseSCH(int v)   //由于此算法采用的visited数组同深度优先遍历算法是一样的，为避免发生两者的冲突，建立一一验证
{
visited[v]=1;
for(int j=0;j<vertexNum;j++)
   if(arc[v][j]==1&&visited[j]==0)
   {
    cout<<"("<<v<<j<<")"<<" ";
    DFSTraverseSCH(j);
   }

}
/*
1，visited2数组初始化
2,重复下面的操作直到front==rear
    队头元素后移；
    以v存在未被访问的结点
     访问标志置1；
     队尾数组下标后移
*/
template<class T>
void MGraph<T>::BFSTraverse(int v)
{
int front,rear;
int visited2[MaxSize],q[MaxSize];
for(int i=0;i<MaxSize;i++)
   visited2[i]=0;
front=rear=-1;
cout<<vertex[v]<<" ";
visited2[v]=1;
q[++rear]=v;
while(front!=rear)
{
   v=q[++front];                  //此种方法模拟出队，就是头数组下标后移
   for(int j=0;j<vertexNum;j++)
    if(arc[v][j]==1&&visited2[j]==0)
    {
     cout<<vertex[j]<<" ";
     visited2[j]=1;
     q[++rear]=j;
    }
}
}

void main()
{
//char a[4]={"we","are","good","!"};    定义一个数组，其存储的是图中的结点元素,对于整数元素不需要将双引号，因为编译器会认为其为字符，引起编译错误
int a[4]={1,3,4,5};
int b[5]={1,2,3,4,5};
MGraph<int> g(a,4,4);        //对象的初始化，采用对象调用定义的构造函数，根据函数的重载，其会自动匹配定义的构造函数，而不是默认的构造函数,注意图的逻辑性，
//int a[5]={1,2,3,4,5,};
//MGraph<int> g(a,5,5);
//cout<<"深度优先遍历递归算法的结果为：";
    //g.DFSTraverse(0);cout<<endl;
cout<<"深度优先非递归算法的结果为：";
g.DFSTraverse2(0);   cout<<endl;
cout<<"深度优先算法2的结果为：";
g.DFSTraverse1(0);cout<<endl;
cout<<"广度优先遍历非递归算法：";
g.BFSTraverse(0); cout<<endl;
cout<<"深度优先遍历生成树为：";
g.DFSTraverseSCH(0);
MGraph<int> G(b,5,5);
cout<<"深度优先遍历递归算法的结果为：";
G.DFSTraverse(0);cout<<endl;
G.DFSTraverse2(0);cout<<endl;               //示例数据组合

}