图的深度优先遍历求最短路径dfs求最短距离
图的基本知识
图是有N个顶点和M条边组成的集合 。图可以分为有向图和无向图，如果给图的每一条边规定一个方向，那么就称改图为有向图，边称为有向边 。在有向图中，与每一个顶点相关联的边有出边和入边之分，与每一个有向边相关联的两个点也有起点和终点之分 。边没有方向的图称为有向图 。
什么是深度优先遍历（DFS） dfs思想
首先以一个未被访问过的节点作为起始节点u，沿节点u的边走到未被访问的第一个顶点v，然后将顶点v作为新的起始节点；如果当前顶点v没有未被访问的顶点时，则回到上一个顶点u，继续访问u还没有被访问的顶点，重复上述过程，直到所有的顶点都已被访问过为止 。
DFS是沿着图的某一分支遍历直到末端，然后回溯，再沿着另一条进行同样的遍历 。直到所有的顶点都被访问为止 。
举例说明
【图的深度优先遍历求最短路径】图以及其邻接矩阵表示如下（book表示是否被访问过）：
dfs遍历具体步骤：
代码实现
/*测试用例：1 2 21 5 102 3 32 5 73 1 43 4 44 5 55 3 3*/#include #include using namespace std;class DFS_Traverse{private:int vertice = 0;//顶点数int edge = 0;//边数vector> e;vector book;//判断顶点j是否扩展过int sum = 0;//统计dfs访问的节点数之和public:DFS_Traverse(int x, int y) :vertice(x), edge(y){//图的初始化从下标1开始e.resize(vertice + 1);//初始化二维数组的行for (int i = 0; i <= vertice; i++){e[i].resize(vertice + 1);//初始化二维数组的列}book.resize(vertice + 1);}//图的初始化void Init_tu(){for (int i = 0; i <= vertice; i++){for (int j = 0; j <= vertice; j++){if (i == 0 || j == 0){e[i][j] = 0;}if (i == j){e[i][j] = 0;}else{e[i][j] = INT_MAX;}}book[i] = false;}book[1] = true;}//读入图的边，并且根据边的信息初始化数组dis，数组bookvoid GetEdgeInfo(){cout << "输入边的信息（节点1，节点2，权重）：" << endl;int e1 = 0, e2 = 0, weigth = 0;for (int i = 1; i <= edge; i++){cin >> e1 >> e2 >> weigth;e[e1][e2] = weigth;}}//打印void Print(){for (int i = 1; i <= vertice; i++){for (int j = 1; j <= vertice; j++){cout << e[i][j] << "";}cout << endl;}cout << endl;}//dfs核心思想void dfs_Alg(int current)//current当前所在的节点编号{sum++;if (sum == vertice)//所有的节点均已被访问{cout << current << endl;return;}else{cout << current << " ->";}for (int k = 1; k <= vertice; k++){if (e[current][k] != INT_MAX && current != k && book[k] == 0){book[k] = 1;dfs_Alg(k);}}}};int main(){DFS_Traverse dfs(5, 8);dfs.Init_tu();dfs.GetEdgeInfo();cout << "初始信息：" << endl;dfs.Print();dfs.dfs_Alg(1);return 0;}
dfs求最短距离
从顶点u开始遍历，找到达节点v的所有路径，取最短距离 。
实现（上文所示案例）
#include #include using namespace std;class DFS_Traverse{private:int vertice = 0;//顶点数int edge = 0;//边数vector> e;vector book;//判断顶点j是否扩展过int sum = 0;//统计dfs访问的节点数之和int min = INT_MAX;//最短路径距离public:DFS_Traverse(int x, int y) :vertice(x), edge(y){//图的初始化从下标1开始e.resize(vertice + 1);//初始化二维数组的行for (int i = 0; i <= vertice; i++){e[i].resize(vertice + 1);//初始化二维数组的列}book.resize(vertice + 1);}//图的初始化void Init_tu(){for (int i = 0; i <= vertice; i++){for (int j = 0; j <= vertice; j++){if (i == 0 || j == 0){e[i][j] = 0;}if (i == j){e[i][j] = 0;}else{e[i][j] = INT_MAX;}}book[i] = false;}book[1] = true;}//读入图的边，并且根据边的信息初始化数组dis，数组bookvoid GetEdgeInfo(){cout << "输入边的信息（节点1，节点2，权重）："