图的广度优先遍历与深度优先遍历-蒲公英云

图的广度优先遍历与深度优先遍历

港控/mmm° 2022-03-15 06:48 562阅读 0赞

一. 广度优先遍历(Depth-First Search)

在进行遍历时，从图的深度入手，使用栈从起始顶点遍历到与之相连的某条通路的末尾，没有路时再选择回退，即顶点元素出栈。具体过程可以进行如下描述：

创建一个访问标记数组visited，并初始化为false，表示此顶点没有被访问
创建栈，将某个元素入栈(这里我们选取的是顶点数组中下标为0的元素)，并将其输出
while (!s.empty()) { //栈不为空
遍历顶点数组中所有顶点，寻找top元素的邻接点
s.top();//得到栈顶元素
可以进行遍历的两个条件

!visited[i]：没有被访问过
g.edge[top][i] > 0：顶点与元素之间有边相连
将该节点标记为遍历过
输出
将该元素压栈
s.pop();//与栈顶相邻的顶点全部遍历完成时，栈顶元素出栈
销毁访问标记数组visited
}

void DFS(Graph& g)
{
    bool* visited = new bool[g.vertexNum];
    // init
    for (int i = 0; i < g.vertexNum; ++i)
    {
        visited[i] = false;
    }
    // 从顶点数组中的第一个开始访问
    stack<int> st;    // int - 顶点数组的下标
    visited[0] = true;
    cout << g.vertex[0] << " ";
    st.push(0);
    while (!st.empty())
    {
        // 遍历所有的顶点, 找邻接点 - 栈顶元素对应的邻接点
        for (int i = 0; i < g.vertexNum; ++i)
        {
            // 栈顶元素在顶点数组中的位置
            int top = st.top();
            //1.没有被访问过：!visited[i]：以防止“走回头路”
            //2.在同一条边上：g.edge[top][i] > 0：即以边建立关联的两个节点。·
            if (!visited[i] && g.edge[top][i] > 0)
            {
                // 遍历该顶点
                visited[i] = true;
                cout << g.vertex[i] << " ";
                // 邻接点压栈
                st.push(i);
            }
        }
        // 栈顶的顶点与其余的顶点组成的边全部判断了一遍
        st.pop();
    }
    delete[] visited;
}

二. 深度优先遍历(Breadth-First Search)

从给出节点开始，遍历所有与之有边相连的节点，直到对此类节点全部完成访问。使用了队列进行操作，因为其先进先出的特性，对于首先进入的节点，遍历处所有具有关联关系的节点后才会弹出队列，从而开始遍历第二个加入队列的节点。

因为基本过程与广度优先遍历基本相似，所以就不多作赘述，直接给出以下代码：

void BFS(Graph& g)
{
    // 保证顶点不被重复遍历
    bool* visited = new bool[g.vertexNum];
    // init
    for (int i = 0; i < g.vertexNum; ++i)
    {
        visited[i] = false;
    }
    // 找一个顶点, 开始访问 - 0
    queue<int> q;    // 存储顶点的下标
    visited[0] = true;
    cout << g.vertex[0] << " ";
    q.push(0);
    // 如果队列为空, 遍历完成
    while (!q.empty())
    {
        // 队头顶点的下标值拿出来
        int front = q.front();
        // 遍历所有的顶点, 找邻接点
        for (int i = 0; i < g.vertexNum; ++i)
        {
            // 如果没被访问, 并且两顶点互为邻接点
            if (!visited[i] && g.edge[front][i] > 0)
            {
                // 访问,并且入队列
                visited[i] = true;
                cout << g.vertex[i] << " ";
                q.push(i);
            }
        }
        // 所有的邻接点都访问完成,出队列
        q.pop();
    }
    delete[] visited;
}