左神算法基础巩固--4
文章目录
- 图
- 图的表示
- 图的遍历
- 图的宽度优先遍历
- 图的深度优先遍历
- 解题
图
在面试中图的考察并不寻常，但并不是没有，所以我们也需要学习学习。
图的题目之所以会显得比较难其主要原因便是我们不知道如何正确表示一个图即用一个合适的数据结构将题目中出现的图正确的表示出来。接下来我便为大家介绍一个能适用于大部分常见场景的图的表示。
图的表示
在这个数据结构中主要分为两种一种是点集和边集
点集中的点主要包含点的值，点的入度，点的出度，点所指向的其他的点，点所指向的其他的点的边的信息
边集上的边则包括边的初始点，边的终止点，边的权值
图的遍历
图的宽度优先遍历
图的深度优先遍历
解题
这道题的重点在于找到入读为0的点，在将其输出的同时修改他所指向的所有的点的入度，不断循环直到，所有的点都输出过
kruskal算法是一种用来生成最小生成树的算法，其具体的思路在于，遍历所有的边，找到未选择的一条权值最小的边，在保证其在加入这条边后不会产生环的情况下，加入一个集合。
prim算法是一种用来生成最小生成树的算法，其具体流程为选定一个节点作为初始节点，遍历找到初始节点相邻的所有节点，选择边的权值最下的那条边，重复以上过程直到所有的节点都被链接。注意，在此过程中不可出现环。
djkstra算法是一种用来寻找单源最短路径的算法，其基于贪心策略，它在每一步都选择当前已知的最短路径，然后更新与该路径相连的其他顶点的距离。
