图的建立与遍历

图是一种抽象数据类型，它是由节点以及它们之间的关系所组成的。在计算机科学中，图被广泛应用于多种领域，如网络分析、图像处理、计算机视觉等。本文将从图的定义、图的建立和图的遍历三个方面逐步介绍图这种数据类型。

一、图的定义

图是由节点和边组成的集合，其中节点表示图中的元素，边表示节点之间的关系。通常，节点用圆圈表示，边用连线表示。具有一定特点的图可称作特殊图，形态各异的特殊图有以下几种：

1.无向图：每条边都没有方向。

2.有向图：每条边都有方向。

3.带权图：每条边都有权值。

4.简单图：没有重复的边和自环。

5.多重图：可能存在重复的边和自环。

二、图的建立

图的建立指的是将具有特定特点的图以数据的形式存储在计算机中。常用的两种建立图的方式是邻接矩阵和邻接表。

1.邻接矩阵

邻接矩阵又称为关联矩阵，是一个二维数组，其中的元素表示节点之间的连通性。它有以下优点：可以快速判断节点之间是否联通；方便计算两个节点之间的距离和路径。但是，邻接矩阵不便于插入或删除节点，且它的存储空间复杂度为O(n²)，当节点过多时不适宜使用。

2.邻接表

邻接表是以链表的形式存储每个节点及它们所连接的节点。它的主要优点在于可以方便地插入或删除节点，同时它的存储空间复杂度为O(n+m)，m为边的数量。但是，邻接表不便于查找节点之间的距离和路径。

三、图的遍历

图的遍历是指在图中按照一定的规则从一个节点出发，访问图中的所有节点。常见的图遍历方法有深度优先搜索和广度优先搜索。

1.深度优先搜索

深度优先搜索是从起始节点出发，按照深度方向遍历图，直到遍历到末端节点。其遍历路径呈现为一条条通路，类似于深入地下的策略。深度优先搜索可以用递归或堆栈的方式实现。

2.广度优先搜索

广度优先搜索是从起始节点出发，按照广度方向遍历图，一层一层地遍历下去。其遍历路径呈现为一层一层扩展，类似于漫水填海的策略。广度优先搜索可以用队列的方式实现。