图的深度优先搜索和广度优先搜索

本文首先对图的深度优先搜索和广度优先搜索进行介绍，然后给出其C++实现，也可访问我的Github获取源码。

深度优先搜索（DFS）

1、DFS介绍

  图的深度优先搜索和树的先序遍历比较相似，思想是：假设初始状态下图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发，进行深度优先遍历，直到图中所有和v相连的顶点都被访问。若此时尚有其他顶点未被访问到，则另选顶点作为起始点，重复以上过程，直到图中所有顶点都被访问过。

2、DFS图解

下面以无向图为例，介绍DFS的遍历过程：

第1步：访问A。
第2步：访问(A的邻接点)C。

在第1步访问A之后，接下来应该访问的是A的邻接点，即"C,D,F"中的一个。但在本文的实现中，顶点ABCDEFG是按照顺序存储，C在"D和F"的前面，因此，先访问C。 

第3步：访问(C的邻接点)B。

在第2步访问C之后，接下来应该访问C的邻接点，即"B和D"中一个(A已经被访问过，就不算在内)。而由于B在D之前，先访问B。 

第4步：访问(C的邻接点)D。

在第3步访问了C的邻接点B之后，B没有未被访问的邻接点；因此，返回到访问C的另一个邻接点D。 

第5步：访问(A的邻接点)F。

前面已经访问了A，并且访问完了"A的邻接点B的所有邻接点(包括递归的邻接点在内)"；因此，此时返回到访问A的另一个邻接点F。 

第6步：访问(F的邻接点)G。
第7步：访问(G的邻接点)E。

因此访问顺序是：A -> C -> B -> D -> F -> G -> E

广度优先搜索（BFS）

1、BFS介绍

  图的广度优先搜索的思想是：从图中某顶点v出发，在访问v之后一次访问v的各个未被访问的邻接点，然后分别从这些邻接点出发，依次访问他们的邻接点（分层访问的意思），直到图中所有已被访问的顶点的邻接点都被访问到。如果此时尚有顶点未被访问，则选取另一个未被访问过的顶点作为新的起始点，重复以上过程，直到图中所有顶点都被访问。

2、BFS图解

第1步：访问A。
第2步：依次访问C,D,F。

在访问了A之后，接下来访问A的邻接点。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，C在"D和F"的前面，因此，先访问C。再访问完C之后，再依次访问D,F。 

第3步：依次访问B,G。

在第2步访问完C,D,F之后，再依次访问它们的邻接点。首先访问C的邻接点B，再访问F的邻接点G。 

第4步：访问E。

在第3步访问完B,G之后，再依次访问它们的邻接点。只有G有邻接点E，因此访问G的邻接点E。

因此访问顺序是：A -> C -> D -> F -> B -> G -> E

C++实现

下面给出DFS和BFS的C++实现，首先定义一个存放顶点的类Node：

class Node
{
public:
    //构造函数
    Node(char data = 0);

    //数据
    char m_cData;

    //定义顶点是否被访问过
    bool m_bIsVisited;
};

//构造函数的实现
Node::Node(char data)
{
    m_cData = data;
    m_bIsVisited = false;
}

然后定义Graph类，如下：

class Graph
{
public:
    Graph(int capacity);        //构造函数
    ~Graph();                   //析构函数
    void DepthFirstSearch(int nodeInedx);               //深度优先搜索
    void BreadthFirstSearch(int nodeIndex);             //广度优先搜索
    void BreadthFirstSearchImpl(vector<int> preVec);    //广度优先搜索的实现函数

private:
    int m_iCapacity;            //图中能够容纳的结点数量
    Node *m_pNodeArray;         //存放顶点的数组指针
    int *m_pMatrix;             //存放邻接矩阵的指针
};

下面是构造函数和析构函数的实现：

//构造函数的实现
Graph::Graph(int capacity)
{
    m_iCapacity = capacity;
    m_iNodeCount = 0;
    m_pNodeArray = new Node[m_iCapacity];                               //分配大小存放结点，一个数组
    m_pMatrix = new int[m_iCapacity * m_iCapacity];                     //分配大小存放邻接矩阵
    memset(m_pMatrix, 0, m_iCapacity * m_iCapacity * sizeof(int));      //将邻接矩阵的元素都置为0
}

//析构函数的实现
Graph::~Graph()
{
    delete []m_pNodeArray;
    delete []m_pMatrix;
}

DFS的实现：

//深度优先遍历
void Graph::DepthFirstSearch(int nodeIndex)
{
    //先访问当前传入的结点
    m_pNodeArray[nodeIndex].m_cData;
    m_pNodeArray[nodeIndex].m_bIsVisited = true;

    for(int i = 0; i < m_iCapacity; i++)
    {
        //m_pMatrix[nodeIndex * m_iCapacity + i 为邻接矩阵的nodeIndex行，i列的值
        if(m_pMatrix[nodeIndex * m_iCapacity + i] == 1 && m_pNodeArray[i].m_bIsVisited == false)
        {
            DepthFirstSearch(i);
        }
    }
}

BFS的实现：

//广度优先搜索
void Graph::BreadthFirstSearch(int nodeIndex)
{
    m_pNodeArray[nodeIndex].m_cData;
    m_pNodeArray[nodeIndex].m_bIsVisited = true;

    vector<int> curVec;
    curVec.push_back(nodeIndex);

    BreadthFirstSearchImpl(curVec); 
}

//实现递归的函数
void Graph::BreadthFirstSearchImpl(vector<int> preVec)
{
    //int value = 0;
    vector<int> curVec;

    for(int j = 0; j < preVec.size(); j++)
    {
        for(int k = 0; k < m_iCapacity; k++)
        {
            if(m_pMatrix[preVec[j] * m_iCapacity + k] == 1 && m_pNodeArray[k].m_bIsVisited == false)
            {
                m_pNodeArray[k].m_cData;
                m_pNodeArray[k].m_bIsVisited = true;
                curVec.push_back(k);
            }
        }
    }
    if(curVec.size() == 0)
    {
        return;
    }
    else
    {
        BreadthFirstSearchImpl(curVec);
    }
}