数据结构之＜图＞的介绍

图（Graph）的概念：
在数据结构中，图是由节点（顶点）和边组成的非线性数据结构。图用于表示不同对象之间的关系，其中节点表示对象，边表示对象之间的连接或关系。

1.图的基本组成元素：

1. 节点（Vertex 或 Node）： 表示图中的实体或对象。节点可以有不同的属性和值。在某些情况下，节点也被称为顶点。

2. 边（Edge）： 表示连接节点的关系。边可以是有向的（有方向性）或无向的（无方向性），也可以有权重或权值（表示边的成本、距离或其他度量）。

2.图的分类：

2.1.有向图（Directed Graph）：

有向图是一种图，其中边有方向。也就是说，从一个节点到另一个节点的边具有明确的起点和终点。有向图中的边可以是单向的，也可以是双向的。

2.2.无向图（Undirected Graph）：

无向图是一种图，其中边没有方向。也就是说，从一个节点到另一个节点的边没有明确的起点和终点。无向图中的边是双向的，表示节点之间的对等关系。

2.3.连通图（Connected Graph）：

连通图是指图中任意两个节点之间都存在路径的图。也就是说，从图中的任意一个节点出发，都可以到达图中的其他所有节点。

2.4.非连通图（Disconnected Graph）：

非连通图是指图中存在孤立的节点或者多个不相连的子图。也就是说，从某个节点出发，无法到达图中的其他某些节点。

2.5.加权图（Weighted Graph）：

加权图是一种图，其中每条边都有一个权重或者值。这些权重可以表示节点之间的距离、成本、容量等。加权图用于解决一些需要考虑边的权重的问题，如最短路径问题、最小生成树问题等。

3.图的表示方式：

1. 邻接矩阵（Adjacency Matrix）： 用二维数组表示节点之间的连接关系。矩阵的行和列表示节点，矩阵元素表示节点之间是否存在边或边的权重。

2. 邻接表（Adjacency List）： 用链表、数组或字典等数据结构表示图中的节点及其相邻节点。每个节点记录其相邻节点的信息。

4.图的常见操作和算法：

• 遍历（Traversal）： 深度优先搜索（DFS）和广度优先搜索（BFS）是常用的图遍历算法，用于访问和搜索图中的节点和边。

• 最短路径算法（Shortest Path Algorithms）： 例如 Dijkstra 算法和 Bellman-Ford 算法，用于找到图中两个节点之间的最短路径。

• 最小生成树算法（Minimum Spanning Tree Algorithms）： 如 Prim 算法和 Kruskal 算法，用于找到连接图中所有节点的最小成本树形结构。

• 拓扑排序（Topological Sorting）： 用于有向无环图（DAG）中节点的线性排序，使得图中任何一对顶点u和v，若边(u, v)存在，则u排在v的前面。