(此文为王道数据结构学习笔记，只供个人后续复习使用，若有错误，还望指出我改正，谢谢）
图的遍历
广度优先遍历：
树的广度优先遍历：层序遍历，树是特殊的图
同样的，图也可以使用辅助队列实现层序遍历
bool visited[MAX_VERTEX_NUM];//初始全部为false，用来表示一个点是否被访问过了
void BFS(Graph G, int v){
visit(v);//访问点v
visited[v]=TRUE;//标记为被访问过
Enqueue(Q,v);//辅助队列，v入队Q
while(!isEmpty(Q)){
DeQueue(Q,v);//v出队
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))//检测v的邻接点
if(!visited[w]){//如果w为邻接点
visit(w);//访问w
visited[w]=TRUE;//标记为被访问过
EnQueue(Q,w);//w入队
}
}
}如果为非连通图，以上算法将不能遍历为连上的子图，可以加一个判断改进
void BFSTraverse(Graph G){
for(i=0;i<G.vexnum;++i)
visited[i]=FALSE;//标记数组置为false
InitQueue(Q);//初始化辅助队列
for(i=0;i<G.vexnum;++i)//从第一个结点开始判断
if(!visited[i])//如果该结点为被遍历
BFS(G,i);//从该结点开始进行广度优先遍历
}空间复杂度：辅助队列最大需要顶点数量个数的空间，即O(v)；
时间复杂度：邻接矩阵存储，需要邻接矩阵查找的时间×顶点数，即O(V2)。邻接表存储，需要O(V+E)的时间，V为点数，E为边数
广度优先生成树/森林：
即进行遍历时，经过的边，N-1条，会形成一个树/或多个树。
深度优先遍历：
void DFSTraverse(Graph G){
for(i=0;i<G.vexnum;++i)
visited[i]=FALSE;//标记数组置为false
InitQueue(Q);//初始化辅助队列
for(i=0;i<G.vexnum;++i)//从第一个结点开始判断
if(!visited[i])//如果该结点为被遍历
DFS(G,i);//从该结点开始进行深度优先遍历
}
void DFS(Graph G, int v){
visit(v);
visited[v]=TRUE;
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighor(G, v, w))
if(!visited[w])
DFS(G,w);
}时间复杂度于广度一样
深度优先生成树/森林：
即进行遍历时，经过的边，N-1条，会形成一个树/或多个树。
同一个图，不同邻接表，生成序列不同，而邻接矩阵一样。
有向图同一个图，不同顶点的遍历，最后生成的生成树，可能数量不同。
最小生成树：（最小代价树）MST
一个连通图中加权路径最短的树
一个连通的图，本身就是树，则其最小生成树为本身
Prim算法 普里姆算法
从某一点开始构建生成树，每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。
时间复杂度：O(V2) 点个数的平方 适合图的边稠密的图
Kruskal算法 克鲁斯卡尔算法
每次选择权值最小的边，让这条边的两头连通，原本连通的则不选，直到所有点都连通。
时间复杂度：O(E*LOG2 E) 边×边的二为底对数 适合图的边稀疏的图
最短路径问题
广度优先算法 BFS算法（无权图）
将边的权视为1，每遍历一层代价+1
void BFS_MIN_Distance(Graph G, int u){
for(i=0;i<G.vexnum;++i){
d[i]=INFINITY; //表示u到i的距离，初始全部为无穷
path[i]=-1; //最短路径经过的点，初始设为-1
}
d[u]=0;
visited[u]=TRUE;
EnQueue(Q,u);
while(!isEmpty(Q)){ //BFS算法
DeQueue(Q,u);
for(w=FirstNeighbor(G,u);w>=0;w=NextNeighor(G, u, w))
if(!visited[w]){ //w为u尚未访问的邻接结点
d[w]=d[u]+1; //路径长度+1
path[w]=u; //最短路径从u到w
visited[w]=TRUE;//w标记为已访问
EnQueue(Q,w);
}
}
}Dijkstra 迪杰斯特拉算法
对V0实现到其他所有点的最短路径Dijkstra算法：
设置三个数组：
final数组，用于存放顶点连通信息，如已和V0连通，则置为TRUE，初始V0为TRUE，其余为FALSE；
dist数组，用于存放此时V0到该点的最短路径长度，初始V0为0，邻接点为其权值，未邻接点为无穷；
path数组，用于存放到V0到该点长度为dist长时，所经过的上一个点的序号，即为该点的前驱。初始时，邻接点为V0序号（即0），其余点为-1；
算法流程：
查看final数组，找到为FALSE的点，对比它们dist，选取最小的顶点，将之final置为TRUE，更新三个数组。更新方式：判断其他点经过所选取的点后，V0与其的最短路径是否缩短，如缩短则改dist，同时将path改为所选取点作为前驱，同时将原本与V0不能连通，现在经过所选取的点与V0连通后的点的final置为TRUE。开启新一轮，重复上述操作，直到final值全部为TRUE为止。
完成后，dist即为V0到该点的最短路径长度，path即为到该点所经过的倒数第二个点，最短路径可通过path进行反推得出。（目标点path得知后，再查看目标点path所存序号的点的path，重复操作，直到某点path为0，即V0）
时间复杂度为O(n2）
Dijistra的不适用于权值有负数的情况
Floyd 弗洛伊德算法：求出每一对顶点之间的最短路径
使用动态规划思想，将问题分为多个阶段
对于n个顶点的图G，求任意一堆顶点Vi，Vj之间的最短路径可以分为以下阶段：
初始：不允许经过其他点中转，则Vi到Vj的最短路径长度为？
第1轮：允许经过V0中转，则Vi到Vj的最短路径长度为？
第1轮：允许经过V0、V1中转，则Vi到Vj的最短路径长度为？
第2轮：允许经过V0、V1、V2中转，则Vi到Vj的最短路径长度为？
第3轮：允许经过V0、V1、V2、V3中转，则Vi到Vj的最短路径长度为？
......
第n-1轮次：允许经过V0、V1、V2...Vn-1中转，则Vi到Vj的最短路径长度为？
经过不断优化实现即可
?循环部分的代码：
for(int k=0;k<n;k++){ //考虑以Vk作为中转点
for(int i=0;i<n;i++){ //遍历矩阵，i为行，j为列
for(int j=0;j<n;j++){
if(A[i][j]>A[i][k]+A[k][j]){//经过Vk更短
A[i][j]=A[i][k]+A[k][j];//更新最短路径长度
path[i][j]=k; //将中转点作为前驱path
}
}
}
}三重循环，时间复杂度为O(）
使用了辅助二维数组，空间复杂度为O(）
弗洛伊德算法可以解决带有负数权值的图，但不能解决有负数权值的回路的图，例如V0，V1，V0三个点，分别有V0—>V1权为 -3 ，V1—>V2权为 1 ，V2—>V0权为 1 ，此时经过越多次的回路，会让加权路径长度不断减小，无最短路径。
?
