图的存储与深度、广度优先遍历

在计算机科学中，图是一种用于表示对象之间关系的抽象数据类型。图由节点（顶点）和边组成，节点表示对象，边表示对象之间的关系。为了有效地存储和处理图，我们需要选择合适的存储方式以及遍历算法。

图的存储

图的存储方式主要有两种：邻接矩阵和邻接表。

1. 邻接矩阵：使用一个二维数组来表示图，其中矩阵的行和列都对应图中的节点。如果节点i和节点j之间存在一条边，则矩阵的第i行第j列的元素为1，否则为0。邻接矩阵的优点是易于理解和实现，但在表示稀疏图（即边的数量较少的图）时，会浪费大量的存储空间。
2. 邻接表：使用一个数组来表示每个节点与其邻居节点之间的边。对于每个节点，我们存储其邻居节点的索引或标识符。邻接表的优点是在表示稀疏图时更加节省空间，但实现起来相对复杂一些。

深度优先遍历（DFS）

深度优先遍历是一种用于遍历或搜索树或图的算法。该算法会尽可能深地搜索树的分支，当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

以下是深度优先遍历的伪代码：

DFS(node):
    if node is not visited:
        mark node as visited
        for each neighbor of node:
            DFS(neighbor)

广度优先遍历（BFS）

广度优先遍历是一种用于遍历或搜索树或图的算法。该算法从根节点开始，探索邻近的节点，然后是它们的邻居节点，以此类推。广度优先遍历使用一个队列来保存待访问的节点。

以下是广度优先遍历的伪代码：

```python
BFS(root):
创建一个队列Q，并将root节点放入队列中
while Q不空:
从队列中取出一个节点n
对节点n进行操作（例如打印节点的值）
将n的所有未被访问过的邻居节点添加到队列Q的尾部