数据结构与算法

图

图的遍历

1.深度优先搜索 类似于树先序遍历 DFS

若有N个顶点，E条边
用邻接表存储图 时间复杂度为 O（N+E）
用邻接矩阵存储图 时间复杂度为 O(N*N)

2.广度优先搜素 类似于树的层序遍历 BFS

若有N个顶点，E条边
用邻接表存储图 时间复杂度为 O（N+E）
用邻接矩阵存储图 时间复杂度为 O(N*N)

3.图不连通怎么办

例子：解救007

例子：6度空间

算法思路
对每个结点，进行bfs
搜索过程中累计访问的节点数
需要记录“层”数，仅仅计算6层涌诶的节点数

4.最短路径问题

在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径，这条路径就是两点之间的最短路径，第一个顶点为源点。
单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径
①有向无权图
按照递增（非递减）的顺序找出到各个顶点的最短路

②有向有权图
按照递增顺序找出到各个顶点的最短路 Dijkstra算法


多源最短路径问题：求任意两点间的最短路径
Floyd算法

算法

prim算法

1.什么是最小生成树
是一棵树
①无回路
② |v| 个顶点一定有|v|-1条边
是生成树
① 包含全部顶点
② |v|-1条边都在图里
边的权重和最小

KrusKal算法 适用于稀疏图

拓扑排序