算法与数据结构基础 - 图(Graph)
图基础
图(Graph)应用广泛，程序中可用邻接表和邻接矩阵表示图。依据不同维度，图可以分为有向图/无向图、有权图/无权图、连通图/非连通图、循环图/非循环图，有向图中的顶点具有入度/出度的概念。
面对图相关问题，第一步是将问题转为用图表示(邻接表/邻接矩阵)，二是使用图相关算法求解。
相关LeetCode题：
1042. Flower Planting With No Adjacent 题解
图的遍历(DFS/BFS)
图的遍历/搜索可使用DFS或BFS方法。DFS方法 可视化过程，BFS方法 可视化过程
相关LeetCode题：
802. Find Eventual Safe States 题解
1059. All Paths from Source Lead to Destination 题解
关于BFS，详见：算法与数据结构基础 - 广度优先搜索(BFS)
最短路径问题
BFS另可用于求解无权图的最短路径问题，相关LeetCode题：
对于有权图的单源最短路径问题，Dijkstra算法用于无负权边的问题求解 可视化过程，Bellman-Ford算法支持判断有无负权回路、若有则不存在最短路径。Floyd-Warshall是求解多源、无负权边的最短路径问题的算法 可视化过程
相关LeetCode题：
1129. Shortest Path with Alternating Colors 题解
928. Minimize Malware Spread II 题解
787. Cheapest Flights Within K Stops 题解
最小生成树
假设有权图中有这样一棵树，满足图任意两个顶点之间可达、并且这棵树所有边的权值之和最小。这样的树称之为图的最小生成树(MST,Minimum spanning tree)。求最小生成树有重要的现实应用，例如求城市之间航班的安排、使得整体成本最小。
求最小生成树的算法，有 Kruska算法 可视化过程 和 Prim算法 可视化过程
相关LeetCode题：
1168. Optimize Water Distribution in a Village 题解
1135. Connecting Cities With Minimum Cost 题解
图与并查集
如果需要求解图的某两个顶点是否连通、图分成多少非连通部分，这时可以用并查集(Union Find/Disjoint Set)，并查集方法 可视化过程
相关LeetCode题：
323. Number of Connected Components in an Undirected Graph 题解
更多关于Union Find，详见：算法与数据结构基础 - 合并查找(Union Find)
图与拓扑排序
有这样一类问题：节点之间存在依赖关系，求按依赖关系排列节点，这类问题可以转换为有向无环图(DAG)、使用拓扑排序(Topological Sort)求解。
相关LeetCode题：
444. Sequence Reconstruction 题解
更多关于拓扑排序，详见：算法与数据结构基础 - 拓扑排序(Topological Sort)
最新文章
- resolv.conf
- 安装YouCompleteMe
- js-JavaScript高级程序设计学习笔记1
- C#抽象类及其方法的学习【转】
- STL源码学习----lower_bound和upper_bound算法[转]
- 控件WebView网页的加载
- sgu 194 Reactor Cooling（有容量上下界的无源无汇可行流）
- C#判断操作系统是32位还是64位(超简单)
- soket.io.js + angular.js + express.js(node.js)
- Intellij IDEA 2017集成MyBatis三剑客
- HttpUrlConnection使用与总结
- websocket 实现单聊群聊 以及 握手原理+加密方式
- 数据库之mysql篇（1）—— 数据库管理系统简介/mysql的安装、配置
- 3dsmax不同版本 pyside qt UI 设置max窗口为父窗口的方法
- Docker Compose安装以及入门
- android下的样式
- hash、hashchange事件
- Netty中消除开始的日志消息修改日志级别
- 2019 A类
- mysql的collation-字符集