1、 创建图类，存储结构使用邻接矩阵。

2、 输入图的节点数n（小于10个）、边数m，节点分别用1-n代表。

3、 采用“起始节点，终止节点，权值”输入图的m条边，创建图。

4、 输出从节点1开始的BFS遍历，在遍历过程中，如有多个可以选择的节点，则优先选择编号较小的节点。

5、 输出从节点1开始的DFS遍历，在遍历过程中，如有多个可以选择的节点，则优先选择编号较小的节点。

6、 输出从第1节点到第n节点最短路径的长度，如果没有路经，输出0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<iostream>
#include <queue>
using namespace std;
queue<int> resultQueue;

class Graph {
public:
    int **nodes = new int*[10];
    int nodeNum = 0;
    int **weight = new int*[10];
    int *status = new int[10];
    Graph(){
        for (int i = 0; i < 10; ++i) {
            initStatus();
            nodes[i]= new int[10];
            weight[i] = new int[10];
            for (int j = 0; j < 10; ++j) {
                nodes[i][j] = 0;
                weight[i][j] = 0;
            }
        }
    }

    void initStatus() const{
        for (int i = 0; i < 10; ++i) {
            status[i] = 0;
        }
    }

    void BFS() const {
        initStatus();
        queue<int> nodeQueue;

        for (int i = 1; i <= nodeNum; ++i) {
            if (nodes[1][i] == 1){
                nodeQueue.push(i);
                status[i] = 1;
            }
        }
        status[1] = 1;//1这个节点已经用过了
        resultQueue.push(1);

        while (!nodeQueue.empty()){
            int nodeNow = nodeQueue.front();
            nodeQueue.pop();//记下第一个元素并将其弹栈
            resultQueue.push(nodeNow);//放到结果栈里
            for (int i = 0; i <= nodeNum; ++i) {
                if (nodes[nodeNow][i] == 1 && status[i] == 0){//有边而且还没到达过
                    nodeQueue.push(i);
                    status[i] = 1;
                }
            }
        }

        while (!resultQueue.empty()&&resultQueue.size() != 1){
            cout<<resultQueue.front()<<",";
            resultQueue.pop();
        }
        cout<<resultQueue.front()<<endl;
        resultQueue.pop();

    }

    void DFS(int i) const {
        resultQueue.push(i);
        for (int j = 1; j <= nodeNum; ++j) {
            if (nodes[i][j] == 1 && status[j] == 0){//有边而且还没到达过
                status[j] = 1;
                DFS(j);
            }
        }
    }

    void findWay(int targetLocation) const{
        initStatus();
        for (int i = 2; i <= targetLocation; ++i) {
            status[i] = 100000;//足够大了,用它来表示到初始节点最近的距离
        }

        queue<int> nodeQueue;

        for (int i = 1; i <= nodeNum; ++i) {
            if (nodes[1][i] == 1){
                nodeQueue.push(i);
                int wt = status[1] + weight[1][i];
                if (wt<status[i]){
                    status[i] = wt;
                }
            }
        }
        while (!nodeQueue.empty()){
            int nodeNow = nodeQueue.front();
            nodeQueue.pop();//记下第一个元素并将其弹栈

            for (int i = 0; i <= nodeNum; ++i) {
                if (nodes[nodeNow][i] == 1){//有边而且还没到达过
                    nodeQueue.push(i);
                    int wt = status[nodeNow] + weight[nodeNow][i];
                    if (wt<status[i]){
                        status[i] = wt;
                    }
                }
            }
        }
        cout<<status[targetLocation]<<endl;
    }
};


int main() {
    cout << "Input" << endl;
    int m = 0, n = 0;
    scanf("%d,%d",&n,&m);
    Graph graph = *new Graph();
    graph.nodeNum = n;
    int start = 0, end = 0, weight = 0;
    for (int i = 0; i < m; ++i) {
        scanf("%d,%d,%d",&start,&end,&weight);
        if (start<end){
            graph.nodes[start][end] = 1;
            graph.weight[start][end] = weight;
        } else{
            graph.nodes[end][start] = 1;
            graph.weight[end][start] = weight;
        }

    }

    cout << "Output" << endl;
    graph.BFS();
    graph.initStatus();
    graph.DFS(1);
    while (!resultQueue.empty()&&resultQueue.size() != 1){
        cout<<resultQueue.front()<<",";
        resultQueue.pop();
    }
    cout<<resultQueue.front()<<endl;
    if (resultQueue.front() != graph.nodeNum){
        cout<<"0"<<endl;
    } else{
        graph.findWay(graph.nodeNum);
    }
    resultQueue.pop();

    cout << "End" << endl;
    return 0;
}