C++

C++ – 树与图的遍历

_Redstone_c_

BFS – 广度优先遍历

一种利用队列实现的搜索算法。简单来说，其搜索过程和 “湖面丢进一块石头激起层层涟漪” 类似。形象一点如下：

总的来说，就是先遍历离根节点近的，一层一层的。

程序思路

函数传入需要遍历的树/图的根节点，然后将根节点放入队列，开始循环操作，只要队不是空的，就取队首并且将队首元素所连接的点放入队中。

要注意的是，图中可能出现环，可能会陷入死循环，所以要定义一个数组记录节点是否被访问过。

实现方法 – 存储方式为点对点

广度优先遍历，参数v是开始遍历的点，即root
建立链表迭代器，用于访问链表储存的点所连接的点
将当前访问的节点设置为已经访问过的，防止以后重复访问
建立队列
将起点放入队列
如果在操作中队列变空，说明遍历已经完成
v表示当前操作的节点，在这里重置为队首
队首已经被v记录好了，所以可以直接扔掉
利用迭代器访问v所连接的所有点
判读当前的点是否被访问过
将起点放入队列
将当前访问的节点设置为已经访问过的，防止以后重复访

PS：与下文程序一一对应

程序实例 – 存储方式为点对点

bool visited[MAXN] = {};
vector< list<int> > graph; 
void bfs(int v) {
    list<int>::iterator it; 
    visited[v] = true;
    /************Do something************/
    printf("%d ", v);
    /************************************/
    queue<int> q;
    q.push(v);
    while(!q.empty()) {
        v = q.front();
        q.pop();
        for(it = graph[v].begin(); it != graph[v].end(); it++)
            if (!visited[*it]) {
                /************Do something************/
                printf("%d ", *it);
                /************************************/
                q.push(*it);
                visited[*it] = true;
            }
    } 
}

DFS – 深度优先遍历

是一种利用递归实现的搜索算法。简单来说，其搜索过程和 “不撞南墙不回头” 类似。 形象一点如下：

实现方法 – 存储方式为点对点

深度优先遍历，参数v是开始遍历的点，即root
建立链表迭代器，用于访问链表储存的点所连接的点
将当前访问的节点设置为已经访问过的，防止以后重复访问
利用迭代器访问v所连接的所有点
判读当前的点是否被访问过
开始递归

PS：与下文程序一一对应

程序实例 – 存储方式为点对点

bool visited[MAXN] = {};
vector< list<int> > graph; 
void dfs(int v) {
    list<int>::iterator it;
    visited[v] = true;
    /************Do something************/
    printf("%d ", v);
    /************************************/
    for(it = graph[v].begin(); it != graph[v].end(); it++)<>
        if (!visited[*it])
            dfs(*it);
}

发表回复