如何实现图的BFS和DFS

如何实现图的BFS和DFS2015-09-24图的存储结构

本文的重点在于图的深度优先搜索（DFS）和广度优先搜索（BFS），因此不再对图的基本概念做过多的介绍，但是要先大致了解下图的几种常见的存储结构。

邻接矩阵

邻接矩阵既可以用来存储无向图，也可以用来存储有向图。该结构实际上就是用一个二维数组（邻接矩阵）来存储顶点的信息和顶点之间的关系（有向图的弧或无向图的边）。其描述形式如下：

//图的邻接矩阵存储表示#define MAX_NUM 20 // 最大顶点个数enum GraphKind{GY,GN}; // {有向图,无向图}typedef struct{ VRType adj; // 顶点关系类型。对无权图，用1（是）或0（否）表示是否相邻；对带权图，则为权值 InfoType *info; // 与该弧或边相关信息的指针（可无）}ArcCell,AdjMatrix[MAX_NUM][MAX_NUM]; // 二维数组typedef struct{ VertexType vexs[MAX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵 int vexnum,arcnum; // 图的当前顶点数和弧（边）数 GraphKind kind; // 图的种类标志}Graph;

我们分别看下面两个图，左边为有向图，右边为无向图

上面两个图均为无权图，我们假设存储的时候，V0的序号为0，V1的序号为1，V2的序号为2。。。，且adj为1表示两顶点间没有没有连接，为0时表示有连接。则有向图的邻接矩阵如下图左边的矩阵所示，无向图的邻接矩阵如下图右边的矩阵所示；

根据邻接矩阵很容易判断图中任意两个顶点之间连通与否，并可以求出各个顶点的度。

1、对于无向图，观察右边的矩阵，发现顶点Vi的度即是邻接矩阵中第i行（或第i列）的元素之和。

2、对于有向图，由于需要分别计算出度和入读，观察左边的矩阵，发现顶点Vi的出度即为邻接矩阵第i行元素之和，入度即为邻接矩阵第i列元素之和，因此顶点Vi的度即为邻接矩阵中第i行元素和第i列元素之和。

很明显，邻接矩阵所占用的存储空间与图的边数或弧数无关，因此适用于边数或弧数较多的稠密图。