图是啥结构

图是一种常见的数据结构，也是程序设计中经常用到的一种表现形式。在计算机科学中，图由节点（vertex，也称为顶点或点）和边（edge）这两个基本元素组成，图可以用来表示各种不同的现象或事物之间的关系，例如网络拓扑结构、社交网络关系、城市道路交通等。本文将从多个角度分析图这一结构。

一、基本概念

在图中，节点是图的基本组成单位，各个节点之间通过边进行连接。如果两个节点之间存在边，那么这两个节点之间就存在一种关系，可以更直观地理解成“有相似之处”。图可以有有向边（指定方向）或无向边（不指定方向）。边可以有权值，表示两个节点之间的权重或距离等信息。

二、分类

图可以分为有向图和无向图。有向图中，每条边只能够单向通行，例如A->B表示从A到B的有向边，但从B到A没有边；无向图中，每条边是双向的，例如A-B表示连接A和B的无向边，A和B之间的关系是相互的。此外，还有带权图（weighted graph），权重通常用来表示两个节点之间的距离、价值等信息。

三、表示方式

图可以用邻接矩阵（adjacent matrix）或邻接表（adjacent list）来表示。邻接矩阵是一个V x V的矩阵，其中V表示节点的数量，如果节点i与节点j之间有边（或权重），那么矩阵中第i行第j列的元素就是1（或者权重）。邻接表是一种链表的形式，用来表示节点i与其它节点之间的关系。邻接表的优秀性能在于存储空间占用与图的密度成正比，适合存储稀疏图。

四、常用算法

在图的基础上，有很多常用的算法，例如最短路径算法、深度优先搜索算法（DFS）、广度优先搜索算法（BFS）、拓扑排序等。最短路径算法包括Dijkstra算法和Floyd算法；DFS通过将图看做一个树结构，从一个顶点开始，优先访问其相邻的节点，不断深入，直到到达叶子节点，然后回溯到其他的节点，重复该过程；BFS则是按照逐层访问的方式，从源节点开始，依次访问其相邻节点的所有未访问节点，将访问到的节点入队列，然后逐一访问队列中的节点，直到队列为空为止；拓扑排序用于解决有向无环图的问题，即对有向无环图中所有节点进行排序，使得对于任何一条边i->j，都有i排在j的前面。

综上，图是是一种常见的数据结构，由节点和边组成，用来表示各种不同的现象或事物之间的关系。图可以分为有向图和无向图，可以用邻接矩阵或邻接表来表示。常用的算法有最短路径算法、DFS、BFS、拓扑排序等。图是计算机科学领域中重要的一部分，也是程序设计和算法分析中不可或缺的一种数据结构。