【个人学习||算法】图论

一、图论是什么图Graph是由一些节点Vertices也叫顶点以及连接这些节点的线Edges边组成的结构。它是计算机科学中最强大、应用最广泛的数据结构之一。1. 主题与学习目标先做一个合理假设你目前是图论入门到中等水平已经会数组、队列、递归但还没有形成“看到题就知道怎么建图、怎么选算法”的体系。这次的主题是“图论入门总框架”。学完你应该能做到知道什么问题该抽象成图。会判断图是有向图还是无向图、带权图还是无权图。会用邻接表建图。会区分 DFS、BFS、拓扑排序、Dijkstra、并查集分别解决什么问题。能独立做最基础的图论题。2. 核心直觉图论的本质可以先只理解成一句话点 表示对象。边 表示对象之间的关系。所以做图论题第一反应不是“套哪个算法”而是先问自己四个问题谁是点什么关系连边边有没有方向边有没有代价权值图论里最常见的任务其实就这几类能不能到达看连通性。一共有几块看连通块。最少几步到达看最短路。任务有没有先后依赖看拓扑排序。怎么把若干点连起来总代价最小看最小生成树。所以图论不是一个算法而是一类“关系建模 算法选择”的题。3. 正式定义与关键概念图记作 G (V, E)。V 是顶点集合E 是边集合。顶点也叫节点表示一个对象比如一个城市、一门课、一个格子。边表示两个节点之间有关系比如“能走到”“依赖于”“有道路连接”。有向图边有方向比如 u - v表示从 u 到 v 有关系但反过来不一定成立。无向图边没有方向u 和 v 是双向连通的。带权图边上有权值比如距离、费用、时间。无权图边没有权值或者每条边权值都可视为 1。路径从一个点出发沿边走到另一个点的经过序列。环从某个点出发最后又回到自己并且中间形成闭合。连通块无向图中彼此可以互相到达的一组点。入度在有向图中指向某个点的边数。出度在有向图中从某个点指出去的边数。有向无环图简称 DAG意思是“有向图里没有环”。很多依赖关系题本质上就是 DAG。邻接表对每个点存它能直接到达哪些点。大多数算法题都用它。邻接矩阵用二维数组 graph[u][v] 表示边是否存在或边权是多少。适合边很多的稠密图但空间通常更大。补一句经验稀疏图边数远小于 n^2优先用邻接表。稠密图边很多邻接矩阵才可能划算。4. 解题框架抽点连边判断图的类型选算法只是想遍历、判连通、数连通块DFS 或 BFS无权最短路BFS正权最短路Dijkstra存在负权边一般考虑 Bellman-Ford依赖顺序、判有向环拓扑排序动态连边、快速判断是否在同一集合并查集最小代价把所有点连起来最小生成树二、 经典题型解析给你一个由1陆地和0水组成的的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外你可以假设该网格的四条边均被水包围。