图的定义和存储结构

图的定义和基本术语、图的存储结构、图的遍历、最短路算法、最小生成树算法 图的定义和基本术语： 图是由顶点的集合V和边的集合E组成的数学模型，记为G = (V, E)。其中，V是顶点的有穷非空集合，E是边的有穷集合。图可以分为有向图和无向图两种。有向图的每条边都是有方向的，即顶点对<x, y>是有序的；无向图的每条边都是无方向的，即顶点对(x, y)是无序的。 图的基本术语包括： * 顶点（Vertex）：图中的一个节点，记为V。 * 边（Edge）：图中的一个连接两个顶点的线段，记为E。 * 邻接（Adjacency）：两个顶点之间的关系，如果存在边从一个顶点到另一个顶点，则称这两个顶点是邻接的。 * 度（Degree）：一个顶点的度是指与该顶点相连的边的数量。 * 权（Weight）：边或弧上的一个数值，表示从一个顶点到另一个顶点的距离或耗费。 图的存储结构： 图的存储结构可以分为邻接矩阵和邻接表两种。 * 邻接矩阵（Adjacency Matrix）：是一个n x n的矩阵，n是图中的顶点数量。矩阵的每个元素a[i][j]表示从顶点i到顶点j的边的存在与否。 * 邻接表（Adjacency List）：是一个数组，每个元素是一个链表，链表中的每个元素表示一个顶点的邻接点。 图的遍历： 图的遍历是指从一个顶点开始，访问图中的所有顶点的过程。常见的图遍历方法有： * 深度优先搜索（Depth-First Search，DFS）：从一个顶点开始，访问该顶点的所有邻接点，然后递归地访问这些邻接点的邻接点。 * 广度优先搜索（Breadth-First Search，BFS）：从一个顶点开始，访问该顶点的所有邻接点，然后访问这些邻接点的邻接点。 最短路算法： 最短路算法是指从一个顶点到另一个顶点的最短路径的算法。常见的最短路算法有： * Dijkstra算法：用于计算从一个顶点到所有其他顶点的最短路径。 * Bellman-Ford算法：用于计算从一个顶点到所有其他顶点的最短路径，考虑了边的权重。 最小生成树算法： 最小生成树算法是指从一个图中生成一个最小的生成树的算法。常见的最小生成树算法有： * 普里姆算法（Prim's algorithm）：用于生成一个最小的生成树。 * 克鲁斯卡尔算法（Kruskal's algorithm）：用于生成一个最小的生成树。 其他概念： * 完全图（Complete Graph）：是一个每个顶点都与其他所有顶点相连的图。 * 稀疏图（Sparse Graph）：是一个有很少边或弧的图。 * 稠密图（Dense Graph）：是一个有较多边或弧的图。 * 网（Network）：是一个带权的图，图中的边或弧具有相关数称为权，表示从一个顶点到另一个顶点的距离或耗费。