图的基本概念
定义：图是由顶点（节点）和边组成的集合，通常表示为(G=(V, E))，其中V是顶点的集合，E是边的集合。
分类：
有向图与无向图：有向图的边有方向，无向图的边没有方向。
加权图与无权图：加权图的边带有权值，无权图的边权值视为相等。
稀疏图与稠密图：边数远小于顶点数平方的图为稀疏图，边数接近顶点数平方的图为稠密图。
简单图：没有自环和重边的图。
性质：
顶点的度：在无向图中，顶点的度是指连接该顶点的边的数目。在有向图中，顶点的入度是指指向该顶点的边的数目，出度是指该顶点指出的边的数目。
路径与环：从一个顶点到另一个顶点的通路称为路径，若路径的起点和终点相同，则称为环。
连通性：若图中两个顶点有路径，则称这两个顶点是连通的，若图中任意两点都连通，则称该图为连通图。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
图的存储结构
邻接矩阵：用一个二维数组表示图，对于有n个顶点的图，邻接矩阵是一个(n×n)的二维数组。若顶点 i和顶点j之间有边，则数组中对应位置的值为1或边的权重，否则为0。适合表示稠密图，空间复杂度为(O(n^2))。
邻接表：用链表数组表示图，数组长度为顶点数，每个元素都是一个链表，链表中存储与该顶点相邻的所有顶点。适合表示稀疏图，空间复杂度为(O(n + m))，其中n为顶点数，m为边数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
图的遍历算法
深度优先搜索（DFS）：通过递归或栈实现，从某个顶点出发，尽可能深入地访问相邻顶点，直到无法继续，然后回溯到上一个顶点，继续访问其他未访问的相邻顶点。可用于连通性判断、找连通分量、检测环、拓扑排序（后序逆序）等。
广度优先搜索（BFS）：使用队列实现，从起始顶点开始，逐层访问其相邻顶点，先访问的顶点的相邻顶点先被访问。常用于求最短路径（无权图）、层序遍历等。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
最短路径算法
Dijkstra 算法：用于求解单源最短路径问题，即从一个给定顶点到图中其他各顶点的最短路径。该算法要求图中不存在负权边，时间复杂度为(O((n + m)\log n))，其中n为顶点数，m为边数。
Floyd 算法：用于求解多源最短路径问题，即图中任意两个顶点之间的最短路径。时间复杂度为(O(n^3))，其中n为顶点数。
Dijkstra：(蓝点（设为 v1）、红点（设为 v2）、黄点（设为 v3))
初始状态
#距离：dist[a]=0，dist[v1]=∞，dist[v2]=∞，dist[v3]=∞，dist[b]=∞
已处理节点：{}
#处理节点a
更新邻接节点：dist[v1]=5（a→v1），dist[v3]=11（a→v3）
已处理节点：{a}
#处理距离最小的未处理节点v1（距离 = 5）
遍历邻接节点：
v1→v2：5+8=13 → dist[v2]=13
v1→v3：5+3=8 → 比当前dist[v3]=11更小，更新为8
已处理节点：{a, v1}
#处理距离最小的未处理节点v3（距离 = 8）
遍历邻接节点：
v3→v2：8+1=9 → 比当前dist[v2]=13更小，更新为9
v3→b：8+7=15 → dist[b]=15
已处理节点：{a, v1, v3}
#处理距离最小的未处理节点v2（距离 = 9）
遍历邻接节点：
v2→b：9+5=14 → 比当前dist[b]=15更小，更新为14
已处理节点：{a, v1, v3, v2}
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
拓扑排序
并非排序，用于有向无环图（DAG），将图中的顶点排成一个线性序列，使得对于图中的任意一条有向边((u, v))，u在序列中都排在v的前面。可通过 DFS 的后序逆序或 BFS（ Kahn 算法）实现，常用于处理任务调度等逻辑关系问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
