#include <iostream>
#define INF 9999 //表示无穷大
#define MAXVEX 10 //假设顶点最多不超过10个
using namespace std;

struct MGraph {
    int vertex[MAXVEX];//顶点集
    int arc[MAXVEX][MAXVEX];//邻接矩阵
    int vexnum;//顶点数量（如果不知道顶点数，就不知道邻接矩阵的大小）
    int edgenum;//边的数量（如果不知道边的数目，就不知道应该存储多少条边的权值信息）
};

int path[MAXVEX];//存储所有路径组合
int bestPath[MAXVEX];//存储最优路径
int visited[MAXVEX];//储存遍历过的顶点编号
int shortestDistance = 9999;//最短路径长度初始化为9999

//创建邻接矩阵
void create(MGraph& g){//"&"表示对图G的引用,可以用“.”引用该结构体内部的数据元素
    cout << "请输入顶点数：" ;
    cin >> g.vexnum;
    cout << "请输入边数：" ;
    cin >> g.edgenum;
    cout << "请输入顶点信息：" ;
    for (int i = 0; i < g.vexnum; i++) {//顶点初始化
        cin >> g.vertex[i];
    }
    for (int i = 0; i < g.vexnum; i++) {//邻接矩阵初始化
        for (int j = 0; j < g.vexnum; j++) {
            g.arc[i][j] = INF;
        }
    }
        //读入邻接矩阵信息（对所有有权值的边赋值）
        for (int k = 0; k < g.edgenum; k++) {
            int i, j, w;
            cout << "请输入边（vi,vj）的下标i,j和权值w: ";
            cin >> i >> j >> w;
            g.arc[i][j] = w;//赋值
        }
    }
//邻接矩阵输出
void printMatrix(MGraph &g) {
    cout << endl;
    for (int i = 0; i < g.vexnum; i++) {
        for (int j = 0; j < g.vexnum; j++) {
            printf("%8d", g.arc[i][j]);
        }
        cout << endl;//打印完一行就换行
    }
}
//深度优先遍历得到所有路径的可能性
void dfs(int number,MGraph &g) {//number表示顶点序号
    if (number == g.vexnum) { //递归出口
        int currentDistance = 0;
        cout << "当前路径为：【";
        for(int i=0;i<g.vexnum;i++)
        cout << path[i]<<"->";//输出当前路径组合
        cout << path[0]<<"】  ";
        for (int i = 0; i < g.vexnum - 1; i++) {//计算出当前路径长度
            currentDistance += g.arc[path[i]][path[i + 1]];
        }
        currentDistance += g.arc[path[g.vexnum - 1]][path[0]];//加上回到起点的那条路径
        cout << "当前路径长度为： 【" << currentDistance<<"】";
        if (currentDistance < shortestDistance) { //如果当前路径比最短路径段，就更新最短路径
            shortestDistance = currentDistance;
            for (int i = 0; i < g.vexnum; i++)
                bestPath[i] = path[i];
        }
    }
    cout << endl;
    for (int i = 0; i < g.vexnum;i++) {
        if (visited[i] == 0) {
            path[number] = g.vertex[i];//没有访问过就放到path数组中
            visited[i] = 1;//标记该顶点已经访问过
            dfs(number + 1,g);//继续访问下一个顶点
            visited[i] = 0;//返回时将顶点访问标志重置为0
        }
    }
}

int main() {
    MGraph g;
    create(g);
    cout << endl <<"===TSP代价矩阵如下===" << endl;
    printMatrix(g);
    cout << "===================" << endl;
    dfs(0,g);
    cout << endl << "===================" << endl << endl;
    cout << "最短路径为：【";
    for (int i = 0; i < g.vexnum; i++)
        cout << path[i] << "->";//输出当前路径组合
    cout << path[0] << "】  ";
    cout << "最短路径长度为：【"<<shortestDistance << "】"<<endl<<endl;
    system("pause");
    return 0;
}



//请输入顶点数：4
//请输入边数：12
//请输入顶点信息：0 1 2 3
/*
0 1 3
 0 2 6
 0 3 7
1 0 12
 1 2 2
 1 3 8
 2 0 8
 2 1 6
 2 3 2
 3 0 3
3 1 7
 3 2 6
 */