【数据结构】图
待完善。。。
目录
-
图的遍历
- DFS图的深度优先搜索遍历
- 基本思想：
- 1⃣️首先访问出发点v，并将其标记为访问过
- 2⃣️然后选取与v邻接的没有访问过的任意一个顶点w，并访问它
- 3⃣️再选取与w邻接的没访问过的顶点访问，重复上述动作，直到所有顶点被访问过。
- PS：
- 需要一个visit[]数组，用来作为顶点的访问标记
- 需要一个visit[]数组，用来作为顶点的访问标记
- 基本思想：
- BFS图的广度优先搜索遍历
- 基本思想：
- 1⃣️首先访问起始顶点v
- 2⃣️然后选取与v邻接的全部顶点w1 w2 ... wn 进行访问
- 3⃣️再依次访问与w1 w2 ... wn邻接的全部顶点，重复动作，直到所有顶点被访问过。
- PS：
- 需要一个队列，用来存放顶点的全部未被访问过的邻接顶点p = p -> nextarc;(邻接表)
- 队列为空的时候跳出循环
- 基本思想：
- DFS图的深度优先搜索遍历
-
最小代价生成树（无向图）
- 普里姆算法Prim
- 算法思想
- 1⃣️任意取出一个顶点，把它当成一棵树，
- 2⃣️然后从与这棵树邻接的边中挑一条最短的边，并将这条边所连接的顶点加入这棵树
- 3⃣️然后再找一条与这棵树邻接的一条最短的边，重复上述动作，直至所有顶点加入树中
- 算法执行过程中的关键理解点
- 两个数组，vset[]和lowcost[]，vset[i]]=1表示顶点i已经加入树中。lowcost[i]保存当前生成树到顶点i的最短一条边的权值
- 复杂度分析
- n^2
- 适用于稠密图。无向图。
- 算法思想
- 克鲁斯卡尔Kruskal
- 算法思想
- 1⃣️用每次找出候选边权值最小的边，并入生成树中
- 2⃣️重复上述动作，直至所有边都检测完毕。
- 算法执行过程中的关键理解点
- 图中所有边按照权值大小排序sort（）
- ????从最小的边开始扫描，检测是否为候选边（该边加入不会形成回路），是，并入。
- 关于回路问题【并查集】，一棵或者几颗树，找妈妈（root节点）妈妈一样就是一家子（一个集合）。
- 复杂度分析
- 取决于排序算法的复杂度。规模由图的边数e决定
- 适用于稀疏图。无向图。
- 算法思想
- 普里姆算法Prim
-
最短路径（有向图）
- 迪杰斯特拉算法Dijkstra
- 求图中某顶点到其余顶点的最短路径
- 算法思想
- 设两个集合S，T。S存放已经找到的最短路径的顶点，T存放剩余顶点。
- 找v0到集合T中的所有顶点路径最短的点Vu加入S中。
- ????每并入一个顶点，都要更新v0到T集合中剩余顶点的最短路径长度。
- 不断重复上述动作，直至所有节点并入S中。
- 执行过程
- 引入3个数组，dist[]，path[]和set[]数组。
- dist[]：当前已经找到的v0:奥vi的最短路径的长度。初态：有边就是边的权值，无边dist[vi] = ∞
- Path[]：保存从v0到vi最短路径的前一个顶点。初态为：v0到vi有边，path[vi] = v0，否则path[vi] = -1 。本体就是-1。path保存的是一棵树，一颗双亲存储结构存储的树。借助栈，可以直接输出叶子到根路径上的节点。
- Set[]：标记数组，set[vi] = 0 表示vi在T中，未并入S。初态：set[vo] = 1，其余全为0 。
- 复杂度
- n^2
- 弗洛伊德算法Floyd
- 求任意一对顶点间的最短路径
- 算法思想
- 执行过程
- 复杂度
- n^3
mindmap
- 迪杰斯特拉算法Dijkstra
-