#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

#define MAX_LENGTH 100000

template<class T>
class Graph
{
    private:
        T * data;       //数据域
        int ** matrix;    //邻接矩阵
        int vertexNum;
        bool *visited;
    public:
        Graph();    //构造函数，生成一个空图
        ~Graph();   //析构函数，主要是释放数据域和邻接矩阵
        void printmatrix();//打印邻接矩阵
        void CreatGraph();  //创建一个图，参数为图中点的个数
        void DFS_recursive(int pos);//递归的深度优先
        void DFS_unrecursive(int pos);//非递归的深度优先
        void visit(int pos);//访问节点
        void DFS(int _pos,bool isres = true);//深度优先入口函数 true-递归，false-非递归
        void BFS(int _pos);//广度优先搜索入口
        void Floyd();
        void Dijkstra(int start);
};

template<class T>
Graph<T>::Graph()
{
    data = nullptr;
    matrix = nullptr;
    visited = nullptr;
    vertexNum = 0;
}

template<class T>
void Graph<T>::CreatGraph()
{
    //确定节点个数
    cout<<"输入节点的个数：";
    cin>>vertexNum;
    if(vertexNum > 0) data = new T[vertexNum];
    else return;
    visited = new bool[vertexNum];
    //输入节点数据
    if(data)
    {
        cout<<"输入"<<vertexNum<<"个结点所储存的点的数据:";
        for(int i=0;i<vertexNum;i++) cin>>data[i];
    }
    else return;
    //创建邻接矩阵
    matrix = (int **)new int * [vertexNum];
    for(int i=0;i<vertexNum;i++)
        matrix[i] = new int [vertexNum];
    for(int i=0;i<vertexNum;i++)
        for(int j=0;j<vertexNum;j++)
             if(i!=j) matrix[i][j]=MAX_LENGTH;
             else matrix[i][j]=0;

    cout<<"输入路径信息，格式为 “点1 点2 长度”："<<endl;
    int i=0,j=0,k=0;
    cin>>i>>j>>k;
    while(i!=-1 && i<vertexNum && j<vertexNum)
    {
        matrix[i][j]=k;
        cin>>i>>j>>k;
    }

}

template<class T>
void Graph<T>::DFS_recursive(int pos)
{
    visited[pos]= true;
    visit(pos);
    for(int i=0;i<vertexNum;i++)
        if(matrix[pos][i]<MAX_LENGTH && !visited[i]) DFS_recursive(i);

}

template<class T>
void Graph<T>::DFS_unrecursive(int pos)
{
    stack<int> temp;
    temp.push(pos);
    while(!temp.empty())
    {
        int v;
        v = temp.top();
        temp.pop();
        if(!visited[v]) visit(v);
        visited[v]= true;
        for(int i=vertexNum-1;i>=0;i--)
            if(matrix[v][i]<MAX_LENGTH && !visited[i]) temp.push(i);
    }
}

template<class T>
void Graph<T>::printmatrix()
{
    cout<<"当前图的邻接矩阵是："<<endl;
    for(int i=0;i<vertexNum;i++)
    {
        for(int j=0;j<vertexNum;j++)
        {
            if (matrix[i][j]>99999) cout<<"  ∞  ";
            else printf(" %3d ",matrix[i][j]);
        }
        cout<<endl;
    }
}

template<class T>
void Graph<T>::DFS(int _pos,bool isres)
{
    for(int i = 0;i<vertexNum;i++) visited[i]= false;
    cout<<"深度优先搜索的结果为：";
    if (isres) DFS_recursive(_pos);
    else DFS_unrecursive(_pos);
    for(int i = 0;i<vertexNum;i++)
    {
        if(!visited[i])
        {
            if (isres) DFS_recursive(i);
            else DFS_unrecursive(i);
        }
    }
    if(isres) cout<<"(递归)";
    else     cout<<"(非递归)";
    cout<<endl<<"深度优先搜索结束"<<endl;
    for(int i = 0;i<vertexNum;i++) visited[i]= false;
}

template<class T>
void Graph<T>::visit(int pos) {cout<<data[pos]<<" ";}

template<class T>
void Graph<T>::BFS(int _pos)
{
    cout<<"广度优先搜索的结果为：";
    for (int i = 0; i < vertexNum; i++) visited[i] = false;
    queue<int> temp;
    while(_pos!=-1)
    {
        temp.push(_pos);
        while (!temp.empty())
        {
            int v = temp.front();
            if (!visited[v]) visit(v);
            visited[v] = true;
            temp.pop();
            for (int j = 0; j < vertexNum; j++)
                if (matrix[v][j] < MAX_LENGTH && !visited[j]) temp.push(j);
        }
            _pos=-1;
            for (int i = 0; i < vertexNum; i++)
            {
                if (!visited[i])
                {
                    _pos = i;
                    break;
                }

            }

    }
    cout<<endl<<"广度优先搜索结束"<<endl;
}

template <class T>
void Graph<T>::Floyd()
{
    cout<<"Floyd算法实现："<<endl;
    int adj[vertexNum][vertexNum],path[vertexNum][vertexNum];
    for(int i=0;i<vertexNum;i++)
        for(int j=0;j<vertexNum;j++)
        {
            adj[i][j]=matrix[i][j];
            path[i][j]=i;
        }

    for(int i=0;i<vertexNum;i++)
    {
        for(int j=0;j<vertexNum;j++)
        {
            for(int k=0;k<vertexNum;k++)
            {
                if(adj[j][i]+adj[i][k]<adj[j][k])
                {
                    adj[j][k]=adj[j][i]+adj[i][k];
                    path[j][k]=path[i][k];
                }
            }
        }
    }
    cout<<"adj矩阵为："<<endl;
    for(int i=0;i<vertexNum;i++)
    {
        for(int j=0;j<vertexNum;j++)
            if(adj[i][j]<MAX_LENGTH) cout<<adj[i][j]<<"  ";
            else cout<<"  ∞  ";
        cout<<endl;
    }
    cout<<"path矩阵为："<<endl;
    for(int i=0;i<vertexNum;i++)
    {
        for(int j=0;j<vertexNum;j++)
            cout<<path[i][j]<<"  ";
        cout<<endl;
    }
    cout<<"Floyd算法结束"<<endl;
}

template<class T>
void Graph<T>::Dijkstra(int start)
{
    int dist[vertexNum];
    int path[vertexNum];
    //初始化
    for(int i=0;i<vertexNum;i++)
    {
        visited[i]=false;
        dist[i]=matrix[start][i];
        if(i==start || dist[i]>=MAX_LENGTH) path[i]=-1;
        else path[i]=start;
    }

    for(int i=0;i<vertexNum;i++)
    {
        int min=-1;
        //找一个权值最小的
        for(int j=0;j<vertexNum;j++)
            if ((min == -1 && !visited[j]) || (!visited[j] && dist[min] > dist[j])) min = j;
        //标记为已找到最小
        visited[min]=true;
        //更新从这点出发的边
        for(int j=0;j<vertexNum;j++)
        {
            if(!visited[j] && dist[min]+matrix[min][j]<dist[j])
            {
                dist[j]=dist[min]+matrix[min][j];
                path[j]=min;
            }
        }
    }
    cout<<"---Dijkstra算法---"<<endl;
    cout<<"dist数组：";
    for(int i=0;i<vertexNum;i++) cout<<dist[i]<<"  ";
    cout<<endl;
    cout<<"path数组：";
    for(int i=0;i<vertexNum;i++)
    {
        cout<<path[i]<<"  ";
        visited[i]= false;
    }
    cout<<endl;
}

template<class T>
Graph<T>::~Graph()
{
    delete []data;
    if(matrix)
    {
        for (int i = 0; i < vertexNum; i++)
            delete[]matrix[i];
        delete[]matrix;
    }
}

int main()
{
    Graph<int> a;
    a.CreatGraph();
    a.printmatrix();
    a.DFS(0, true);
    a.DFS(0, false);
    a.BFS(1);
    a.Floyd();
    a.Dijkstra(0);
    return 0;
}