欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的深度优先搜索(DFS)与广度优先搜索(BFS)

程序员文章站 2022-06-04 08:22:38
...

一、深度优先搜索(DFS)

  深度优先搜索的思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点V出发,首先访问该顶点,然后从它的某一个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和V有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。显然,深度优先搜索是一个递归的过程。

1、图解深度优先搜索

  深度优先搜索可以用递归实现也可以用栈来实现:
图的深度优先搜索(DFS)与广度优先搜索(BFS)
图的深度优先搜索(DFS)与广度优先搜索(BFS)

2、深度优先搜索的demo:

(1)递归实现:

bool visited1[100] = {false};

void dfs_digui(int current, int m, vector<vector<int>> data)
{
    visited1[current] = true;
    cout << current << " ";
    for (int i = 0; i < m; ++i)
        if (data[i][0] == current && visited1[data[i][1]] == false)
            dfs_digui(data[i][1], m, data);
}

(2)非递归实现(栈):

bool visited2[100] = {false};
//深度优先搜索(随机访问一个节点,随后访问与之相邻的所有节点中未被访问过的一个)
void dfs(int current, int m, vector<vector<int>> data)
{
    stack<int> st;
    cout << current << " ";
    visited2[current] = true;//以顶点1为起点
    st.push(current);//入栈
    while (!st.empty())
    {
        for (int j = 0; j < m; ++j)
        {
            //访问和当前顶点相邻的所有顶点并将它们入栈
            if (data[j][0] == current && visited2[data[j][1]] == false)
                st.push(data[j][1]);
        }
        if (visited2[st.top()] == 0)//判断栈顶元素所在顶点是否被访问过
        {
            current = st.top();//栈顶元素作为新的顶点
            visited2[current] = true;
            cout << st.top() << " ";
            st.pop();//弹出已访问的顶点
        }
        else//如果栈顶元素被访问过则弹栈
            st.pop();
    }
}

二、广度优先搜索(BFS)

  广度优先搜索的思想是:从图中某顶点V出发,在访问了V之后依次访问V的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问,则需要另选一个未曾被访问过的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。

1、图解广度优先搜索
图的深度优先搜索(DFS)与广度优先搜索(BFS)
图的深度优先搜索(DFS)与广度优先搜索(BFS)

2、广度优先搜索的demo:

(1)使用队列实现:

bool visited3[100] = {false};
//广度优先搜索(随机访问一个节点,随后访问与之相邻的所有未被访问过的节点)
void bfs(int current, int m, vector<vector<int>> data)
{
    queue<int> qe;
    cout << current << " ";
    visited3[current] = true;//以顶点1为起点
    qe.push(current);//加入队列
    while (!qe.empty())
    {
        for (int j = 0; j < m; ++j)
        {
            //访问和当前顶点相邻的所有顶点并将它们入队列
            if (data[j][0] == current && visited3[data[j][1]] == false)
                qe.push(data[j][1]);
        }
        if (visited3[qe.front()] == 0)//判断队头元素所在顶点是否被访问过
        {
            current = qe.front();//队头元素作为新的顶点
            visited3[current] = true;
            cout << qe.front() << " ";
            qe.pop();//已访问的顶点出队
        }
        else//如果队头元素被访问过则出队
            qe.pop();
    }
}
//主函数
int main(int argc, char const *argv[])
{
    int m, n;
    cin >> m >> n;
    vector<vector<int>> data;
    for (int i = 0; i < m; ++i)
    {
        vector<int> vec;
        int x;
        for (int j = 0; j < n; ++j)
        {
            cin >> x;
            vec.push_back(x);
        }
        data.push_back(vec);
    }
    dfs_digui(1, m, data);
    cout << endl;
    dfs(1, m, data);
    cout << endl;
    bfs(1, m, data);
    system("pause");
    return 0;
}