/////////////////////////////////////////////////
//DFS()私有成员函数
//递归:深度优先遍历图所有结点,start是起始结点
/////////////////////////////////////////////////
template<class T,class E>
void Graphlink<T,E>::DFS(int start)
{
    cout<<getValue(start)<<" ";      //访问当前的起始结点
    visited[start]=true;             //把对应的访问标志置为"已访问"

    int p=getFirstNeighbor(start);   //获取start的第一个邻接结点
    while(p!=-1)                     //递归访问start的所有邻接结点
    {
        if(visited[p]==false)        //如果neighbor没有被访问过
            DFS(p);                  //以neighbor为当前结点继续递归访问
        p=getNextNeighbor(start,p);  //获取下个邻接结点的结点号
    };
};
////////////////////////////DFS()私有成员函数结束

/////////////////////////////////////////////////
//DFSGraphic()公有成员函数
//深度优先遍历图所有结点,通过键盘输入起始结点
/////////////////////////////////////////////////
template<class T,class E>
void Graphlink<T,E>::DFSGraphic(int start)
{
    visited=new bool[numVertices];
    for(int i=0;i<numVertices;i++)
        visited[i]=false;//把每个结点的访问标志置为否

    cout<<endl<<"深度优先遍历的结果是:"<<endl;
    if(start>=0 && start<numVertices)
         DFS(start);      //如果输入的结点号合法就开始遍历
    else
        exit(1);
    delete [] visited;   //释放标记数组的内存空间
};
/////////////////////DFSGraphic()公有成员函数结束

/////////////////////////////////////////////////
//BFSGraphic()公有成员函数
/////////////////////////////////////////////////
template<class T,class E>
void Graphlink<T,E>::BFSGraphic()
{
    cout<<"请输入遍历的起始顶点号:";
    int start;                         //起始的结点号
    cin>>start;
    visited=new bool[numVertices];     //开辟标记数组的内存空间
    for(int i=0;i<numVertices;i++)
        visited[i]=false;              //把标记数组置为未访问
    LinkedQueue<int> Q;                //用于存放结点号的队列
    Q.EnQueue(start);                  //首先把起始顶点的标号压入队列
    if(start<0 || start>=numVertices)  //如果起始的结点号不合法
        exit(1);
    int p;                             //当前正在访问的顶点的顶点号
    int q;                             //所有邻接结点的游标指针

    while(!Q.IsEmpty())                //按层次遍历图的所有顶点
    {
        Q.DeQueue(p);                  //从队列中取出一个结点
        if(visited[p]==false)          //如果不曾被访问
        {
            cout<<getValue(p)<<" ";    //访问该结点
            visited[p]=true;           //已经被访问过
            q=getFirstNeighbor(p);     //获取当前访问结点的第一个邻接结点
            while(q!=-1)               //把所有的未被访问过的邻接结点全部送入队列
            {
                if(visited[q]==false)
                    Q.EnQueue(q);      //如果没有被访问过就压入队列
                q=getNextNeighbor(p,q);//获取下个邻接结点号
            };
        };
    };
    delete [] visited;                 //释放标记数组的内存空间
};
/////////////////////////BFSGraphic()公有函数结束

/////////////////////////////////////////////////
//Find_Connected_Component()公有成员函数
//寻找当前图的所有的连通分量(极大连通子图)
/////////////////////////////////////////////////
template<class T,class E>
void Graphlink<T,E>::Find_Connected_Component()
{
    visited=new bool[numVertices];    //开辟标记数组的空间
    for(int i=0;i<numVertices;i++)
        visited[i]=false;             //标记全部初始化为未被访问
    cout<<"所有连通分量顶点的集合如下:";
    cout<<endl;
    for(i=0;i<numVertices;i++)
    {
        if(visited[i]==false)         //如果没有被访问,则可以顺次找出
        {
            DFS(i);                   //连通分量
            cout<<endl;
        }
    };
    delete [] visited;
};
///////Find_Connected_Component()公有成员函数结束

/////////////////////////////////////////////////
//DFSTree()公有成员函数
//递归:得到当前图的深度优先生成树的算法
//其中该树采用FirstChild-NextSibling存储结束
//v是遍历起始的顶点,subTree是以v为当前顶点的生成子树
/////////////////////////////////////////////////
template<class T,class E>
TreeNode<T>* Graphlink<T,E>::DFSTree(int v)
{
    T value=getValue(v);                 //通过结点v创建一个树的结点
    TreeNode<T>* subTree;
    subTree=new TreeNode<T>(value);      //作为当前生成子树的根结
    visited[v]=true;                     //当前结点v已经访问过

    int flag=1;                          //判断是否是长子结点
    TreeNode<T>* ptr=NULL;               //获取长子树的树根
    TreeNode<T>* pre=NULL;               //保留前棵兄弟子树的根结点

    for(int p=getFirstNeighbor(v);       //递归遍历v的所有未访问的邻接结点
        p!=-1;p=getNextNeighbor(v,p))
    {                                    
        if(visited[p]==false)            //如果邻接点p还未被访问过
        {
            ptr=DFSTree(p);              //递归生成一棵子树
            if(flag==1)                  //如果是长子结点
            {
                subTree->firstChild=ptr;
                flag=0;                  //标志表示已经不是长子结点
            }
            else
                pre->nextSibling=ptr;    //接到前面的子树的后面
            pre=ptr;
        };
    };
    return subTree;                      //返回根结点指针
};
////////////////////////////////DFSTree()函数结束

/////////////////////////////////////////////////
//DisplayDFSTree()公有成员函数
//调用上面的DFSTree()递归函数求当前图的深度优先生成树
/////////////////////////////////////////////////
template<class T,class E>
void Graphlink<T,E>::DisplayDFSTree(int v)
{
    visited=new bool[numVertices];
    for(int i=0;i<numVertices;i++)
        visited[i]=false;
    cout<<"先根遍历以"<<getValue(v)
        <<"为起点的深度优先生成树:";
    Tree<T> T;             //定义一棵空树
    T.setRoot(DFSTree(v)); //设置根结点
    T.pre();               //先根遍历该树
    cout<<endl<<"深度优先生成树是:";
    T.Display();
    cout<<endl;
    cout<<"广度优先遍历的结果是:";
    T.levelOrder();

    delete [] visited;
};
/////////////////////////DisplayDFSTree()函数结束

/////////////////////////////////////////////////
//DisplayDFSTree()公有成员函数
//调用上面的DFSTree()递归函数求当前图的深度优先生成树
/////////////////////////////////////////////////
template<class T,class E>
void Graphlink<T,E>::DisplayDFSTree(int v)
{
    visited=new bool[numVertices];
    for(int i=0;i<numVertices;i++)
        visited[i]=false;
    cout<<"先根遍历以"<<getValue(v)
        <<"为起点的深度优先生成树:";
    Tree<T> T;             //定义一棵空树
    T.setRoot(DFSTree(v)); //设置根结点
    T.pre();               //先根遍历该树
    cout<<endl<<"深度优先生成树是:";
    T.Display();
    cout<<endl;
    cout<<"广度优先遍历的结果是:";
    T.levelOrder();

    delete [] visited;
};
/////////////////////////DisplayDFSTree()函数结束

/////////////////////////////////////////////////
//DisplayDFSTree()公有成员函数
//调用上面的DFSTree()递归函数求当前图的深度优先生成树
/////////////////////////////////////////////////
template<class T,class E>
void Graphlink<T,E>::DisplayDFSTree(int v)
{
    visited=new bool[numVertices];
    for(int i=0;i<numVertices;i++)
        visited[i]=false;
    cout<<"先根遍历以"<<getValue(v)
        <<"为起点的深度优先生成树:";
    Tree<T> T;             //定义一棵空树
    T.setRoot(DFSTree(v)); //设置根结点
    T.pre();               //先根遍历该树
    cout<<endl<<"深度优先生成树是:";
    T.Display();
    cout<<endl;
    cout<<"广度优先遍历的结果是:";
    T.levelOrder();

    delete [] visited;
};
/////////////////////////DisplayDFSTree()函数结束

/////////////////////////////////////////////////
//DFSForest()公有成员函数
//如果图是非连通的,则求其深度优先生成森林
//即每个连通分量的深度优先树构成的森林
/////////////////////////////////////////////////
template<class T,class E>
TreeNode<T>* Graphlink<T,E>::DFSForest(int v)
{
    visited=new bool[numVertices];
    for(int i=0;i<numVertices;i++)
        visited[i]=false;            //标志数组清为未访问
    TreeNode<T>* root;               //森林的根
    TreeNode<T>* ptr;                //游标指针
    TreeNode<T>* pre;                //前一棵生成树树的根结点
    int flag=1;                      //是否是森林里的第一棵树的标志
    for(int p=0;p<numVertices;p++)   //试着以每个结点开始寻找每个连通分量
    {                                //的深度优先生成树
        if(visited[p]==false)
        {
            ptr=DFSTree(p);          //找出以p为根的连通分量的深度优先生成树
            if(flag==1)              //是森林里的第一棵树
            {
                root=ptr;            //把ptr作为森林的根
                flag=0;
            }
            else
                pre->nextSibling=ptr;//把树连接入前面已经形成的森林中
            pre=ptr;                 //保留前棵树的根结点
        };
    };
    delete [] visited;
    return root;
};
//////////////////////////////DFSForest()函数结束

/////////////////////////////////////////////////
//getFirstUnvisit()公有成员函数
//得到p的第一个邻接的结点
/////////////////////////////////////////////////
template<class T,class E>
int Graphlink<T,E>::getFirstUnvisit(int p,bool* visited)
{
    Edge<T,E>* ptr=NodeTable[p].adj; //获得p的边链表的头指针
    while(ptr!=NULL)                 //搜索该边链表
    {
        int des=ptr->dest;           //获得每条边的目的结点号
        if(visited[des]==false)      //如果第一个碰到一个未访问的
            return des;              //返回结点号
        ptr=ptr->link;
    };
    return -1;                       //没有找到就返回-1
};
////////////////////////getFirstUnvisit()函数结束

/////////////////////////////////////////////////
//getNextUnvisit()公有成员函数
//得到p的w之后的未访问的邻接结点号
/////////////////////////////////////////////////
template<class T,class E>
int Graphlink<T,E>::getNextUnvisit(int p,int v,bool* visited)
{
    Edge<T,E>* ptr=NodeTable[p].adj;//获得p的边链表的首指针
    int flag=0;                     //判断是否已经找到v
    while(ptr!=NULL)                //搜索边链表中v的指针
    {
        int des=ptr->dest;          //获得每条边的目的结点号
        if(des==v)                  //如果找到
        {
            flag=1;                 //已经找到
            break;
        }
        ptr=ptr->link;
    };
    if(flag==0)                     //边链表中连v都没有
        return -1;
    ptr=ptr->link;                  //指向v后的第一个结点
    while(ptr!=NULL)                //从边结点v后的第一个结点开始搜索
    {
        int des=ptr->dest;          //搜索v后的第一个未被访问的邻接结点
        if(visited[des]==false)
            return des;
        ptr=ptr->link;
    };
    return -1;
};
/////////////////////////getNextUnvisit()函数结束