📁图形数据结构算法

📄图数据结构

1. 图数据结构概述：图数据结构由一系列相互连接的节点（称为顶点）组成，每个节点包含数据，并通过边与其他节点相连。例如，Facebook 的图数据结构包含用户、照片、群组等作为节点，这些节点通过诸如“好友关系”、“加入群组”等边相连。

1. 生成树定义：生成树是无向连通图的子图，包含所有顶点并尽量少使用边。完全图上带有 n 个顶点的生成树数量等于 n^(n-2)。

1. 强连通分量定义：强连通分量是有向图中的一部分，其中任意两个顶点都通过路径相互可达。

1. 定义和表示：邻接矩阵是一种使用矩阵表示图的方法，矩阵中的每个元素代表两个顶点之间是否存在路径，即如果存在从顶点 i 到 j 的路径，则矩阵中的 Aij 为1，否则为0。

1. 定义和结构：邻接表是一种用于表示图的数据结构，其中数组的每个索引表示一个顶点，每个元素是一个链表，代表与该顶点相连的其他顶点。

1. 基本概念：深度优先搜索（DFS）是一种在图形或树结构中遍历或搜索所有顶点的递归算法，按照深度优先的顺序进行。

1. 广度优先搜索定义：广度优先搜索（BFS）是一种用于遍历或搜索树或图的数据结构的算法，它从一个节点开始，然后遍历节点的所有邻居，再遍历邻居的邻居，以此类推。

1. 贝尔曼-福特算法特点：贝尔曼-福特算法能处理带有负权重的边的图，并能检测负权重循环，避免了迪杰斯特拉算法无法处理负权重边的限制。