【数据结构】图-最短路径算法

图的最短算法从起点开始访问所有路径，可以到达终点的有多条地址,其中路径权值最小的为最短路径。
最短路径算法有深度优先遍历、广度优先遍历、Bellman-Ford算法、弗洛伊德算法、SPFA(Shortest Path Faster Algorithm)算法和迪杰斯特拉算法等。

本代码使用深度优先遍历

主要实现思路：

从起点开始，到达终点有多条分支，这些分支中又有多条分支...
选择其实一条分支，走到终点，再选择另一个分支(temp = temp - next)走到终点，分支的分支......

大致流程:
代码实现:

#include iostream 

#include queue 

using namespace std;

 邻接列表的大致排列类似于哈希表

 自己定义出"邻接桶"的概念，类似于“哈希桶”

 邻接桶中存着每个顶点

 每个顶点的通过EdgeNode——边，来链接着顶点和顶点，

 每个顶点都可以作为起始点，指向/被指向。


 cin G.adjlist[i].data;//输入顶点所存数据

 G.adjlist[i].first = NULL;//边和边的关系，置空，先不与任何边相连。


 char v1 = 0, v2 = 0;//保存输入的顶点的字符

 int i1 = 0, i2 = 0;//保存顶点在数组中的下标

 //将i1和i2链接起来

 //i1为起点。i2为终点。

 //保存边的权重

 int weight = 0;

 cout "请输入想关联边的顶点" endl;

 for (int i = 0; i G.edge; i++)

 cin v1 v2 weight;//以v1为起点，v2为终点的边，权重是weight

 i1 = Location(G, v1);

 i2 = Location(G, v2);

 //说明存在

 if (i1 != -1 i2 != -1)

 EdgeNode* temp = new EdgeNode;

 temp- adjvex = i2;

 temp- next = G.adjlist[i1].first;//头插法-类似于hashtable中的插入数据

 temp- weight = weight;

 G.adjlist[i1].first = temp;

//图的最短路径算法

int min_weight = 0x7FFFFFFF;//定义一个最大的方便与之比较。（INT_MAX）

int steps = 0;//已走过的步数

int path[Max_Size ] = { 0 };//保存走过的路径

int shortest_path[Max_Size] = { 0 };//保存最短路径

//求图的最短路径——深度优先遍历（前提是连通图）

// 起点 终点 已走过的权重和 

void DFS(AdjListGraph G,int start ,int end,int weights)

 int cur = -1;

 if (start == end)//已经找到终点了，不需要遍历了

 for (int i = 0; i steps; i++)

 cout G.adjlist[path[i]].data " ";//path中存的是对应结点在邻接桶中的下标，通过这个下标就能找到对应的data,即可找到走过的路径

 cout "该路径对应的长度是:" weights endl;//输入对应的路径长度

 if (min_weight weights)//取到当前最小路径

 min_weight = weights;

 memcpy(shortest_path, path, steps * sizeof(int));

 return;

 visited[start] = 1;

 EdgeNode* temp = G.adjlist[start].first;//指向第一条边

 while (temp)

 int weight = temp- weight;

 cur = temp- adjvex;//通过这条边的指向，指过来的这个顶点，在邻接桶中的下标

 if (!visited[cur])

 visited[cur] = 1;//标记已经访问

 path[steps++] = cur;

 //递归

 DFS(G, cur, end, weights+weight);

 visited[cur] = 0;//前一步探索完成后，置空cur,（应该是有路线含有重复结点时起到作用）

 path[--steps] = 0;//路径回退

 temp = temp- next;

int main(void)

 AdjListGraph G;

 //初始化

 initGraph(G);

 //创建图

 createGraph(G);

 //深度优先-寻找最短路径

 DFS(G, Location(G, A), Location(G, D), 0);

 cout "成功得到最短路径为" endl;

 //最短路径

 int i = 0;

 cout "起点";

 while (shortest_path[i] 0 i Max_Size)

 cout "- " G.adjlist[shortest_path[i]].data ;

 i++;

 cout endl;

 return 0;

输入示例：

大数据开发基础的数据结构和算法的数据结构的图 在大数据开发中，图是一种重要的数据结构。图可以用来描述各种实体之间的关系，例如社交网络中的用户之间的关系、物流系统中的货物之间的运输路径等等。
Redis 底层数据结构大揭秘：五张图看透Redis数据结构 Redis的数据结构从用户层面看就是普通的字典，列表。但是其实在不同的情况下，Redis 会使用不同的底层数据结构进行优化，本文通过五张流程图对其进行了总结。
数据结构和算法之图的认识 什么是图 ● 1. 一组顶点：通常用V(Vertex)表示顶点集合 ● 2. 一组边：通常用E(Edge)表示边的集合 ⅰ. 1. 边是顶点对：(v,w)属于E，其中v,w属于V ⅱ. 2. 有向边 v,w 表示从v指 ⅲ. 3.不考虑重边和自回路 抽象数据类型定义 ● 1.类型名称：图(Graph) ● 2. 数据对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成(可以一条边都没有，但不 能一个顶点都没有) ● 3. 操作集：对于任意图G属于Graph，以及v属于V，e属于E 1. Graph Create()：建立并返回空图
数据结构和算法之如何建立图 小白BG.1 邻接矩阵表示的图结点的结构 typedef struct GNode *PtrToGNode;//PtrToGNode是指向GNode的一个指针 struct GNode{ int Nv;//顶点数 int Ne;//边数 WeightType G[MaxVertexNum][MaxVertexNum]; DataType Data[MaxVertexNum];//存顶点的数据 typedef PtrToGNode MGraph;//以邻接矩阵存储的图类型。定义为指向节点的指针。因为要用到的时候 一个指针远远比一整个图来的快捷 小白BG.2 邻接矩阵表示的图——初始化