c++ - BFS 实施

Question

我最近正在解决一个 bfs 问题，其中每个节点都是数组元素的不同排列。但我无法想出一个合适的数据结构来跟踪扩展树中的访问节点。通常节点是不同的字符串，所以我们可以使用地图将节点标记为已访问但在上述情况下我应该使用什么 DS？

Answer 1

考虑以下伪代码：

type Node;  // information pertaining to a node
type Path;  // an ordered list of nodes
type Area;  // an area containing linked neighboring nodes
type Queue; // a FIFO queue structure

function Traverse(Area a, Node start, Node end) returns Path:
    Queue q;
    Node n;
                        // traverse backwards, from finish to start
    q.push(end);        // add initial node to queue
    end.parent = end;   // set first node's parent to itself

    while (not q.empty()):
        n = q.pop();    // remove first element

        if (n == start) // if element is the final element, we're done
            break;

        for (Node neighbor in a.neighbors(n)): // for each neighboring node
            if (neighbor.parent != Null):      // if already visited, skip
                continue;
            neighbor.parent = n;               // otherwise, visit 
            q.push(neighbor);                  // then add to queue

    Path p;             // prepare to build path from visited list

    for (Node previous = Null, current = n;
              previous != current;
              previous = current, current = current.parent):
        p.add(current); // for each node from start to end, add node to p
                        // Note that the first node's parent is itself
                        // thus dissatisfying the loop condition
    return p;

“访问列表”存储为节点的父节点。将其编码为 C++，您可能会将大多数节点作为引用或指针处理，因为此伪代码依赖于引用行为。

您从一个区域开始，它是一个节点字段。该区域知道每个节点相对于其他节点的位置。您从一个特定节点开始，即“开始”节点，并将其推入队列。

遍历区域就像从区域中获取相邻节点的列表一样简单，如果它们已经被访问过，则跳过它们，否则设置它们的父节点并将它们添加到队列中。当从队列中删除的节点等于目标节点时，遍历结束。当最初遇到节点时，您可以通过在邻居循环期间执行此检查来稍微加快算法速度。

注意：您不需要在开始遍历之前在区域内生成每个可能的节点，区域只需要在创建节点后跟踪它。这可能有助于您使用字符串或数组排列的情况：您可以将起始节点和结束节点推送到区域中，并且它可以动态生成和缓存相邻节点。您可以将它们存储为向量，可以使用 == 运算符根据它们的顺序和内容来比较它们是否相等。 请参阅此示例。

遍历是向后而不是向前，因为它使重建路径更容易（而不是在结束节点结束，每个父节点在它之前的节点，你在开始节点结束，每个父节点在它之后）

数据结构总结

Node需要跟踪足够的信息Area以唯一地识别它（通过数组索引或名称或其他东西）以及父节点。父节点应在遍历之前设置为 NULL 以避免奇怪的行为，因为遍历将忽略具有其父集的任何节点。这也跟踪访问状态：访问等同于 (parent != NULL)。这样做还可以让您不必跟踪队列中的整个路径，这将是非常计算密集的。

Area需要维护一个列表Node，并且需要一个邻居映射，或者一个哪些节点与哪些其他节点相邻的映射。这种映射可能是使用函数动态生成的，而不是从表或一些更典型的方法中查找。它应该能够向调用者提供节点的邻居。拥有一个清除每个节点的父节点的辅助方法可能会有所帮助。

Path基本上是一个列表类型，包含一个有序的节点列表。

Queue是任何可用的 FIFO 队列。你可以用一个链表来做到这一点。

我喜欢语法突出显示在我的 Wuggythovasp++ 上的工作方式。

Answer 2

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author VAISAKH N
 */
public class BFSME {

public static String path = "";
public static String add = "";

public static void findrec(String temp, String end, String[][] m, int j) {
    if (temp.equals(m[j][1])) {
        add = m[j][0] + temp + end + "/";
        end = temp + end;
        System.out.println(end);
        path = path + add;
        temp = "" + add.charAt(0);
        System.out.println("Temp" + temp);
        for (int k = 0; k < m.length; k++) {
            findrec(temp, end, m, k);
        }
    }
}

public static void main(String[] args) {

    String[][] data = new String[][]{{"a", "b"}, {"b", "c"}, {"b", "d"}, {"a", "d"}};
    String[][] m = new String[data.length][2];
    for (int i = 0; i < data.length; i++) {
        String temp = data[i][0];
        String end = data[i][1];
        m[i][0] = temp;
        m[i][1] = end;
        path = path + temp + end + "/";
        for (int j = 0; j < m.length; j++) {

            findrec(temp, end, m, j);
        }

    }
    System.out.println(path);
}
}

Answer 3

至少作为开始，您可以尝试使用/实现类似 Java 的 Arrays.toString() 并使用地图。每种排列都会产生不同的字符串，因此它至少会到达某个地方。

Answer 4

只是为了理解，我在这里提供了我的示例代码（它在 C# 中）

  private void Breadth_First_Travers(Node node)
  {
        // First Initialize a queue - 
        // it's retrieval mechanism works as FIFO - (First in First Out)
        Queue<Node> myQueue = new Queue<Node>();

        // Add the root node of your graph into the Queue
        myQueue.Enqueue(node);

        // Now iterate through the queue till it is empty
        while (myQueue.Count != 0)
        {
            // now, retrieve the first element from the queue 
            Node item = myQueue.Dequeue();
            Console.WriteLine("item is " + item.data);

            // Check if it has any left child   
            if (item.left != null)
            {
                // If left child found - Insert/Enqueue into the Queue
                myQueue.Enqueue(item.left);
            }

            // Check if it has right child 
            if (item.right != null)
            {
                // If right child found Insert/Enqueue into the Queue  
                myQueue.Enqueue(item.right);
            }

            // repeat the process till the Queue is empty
        }
   }

这里的示例代码是参考http://en.wikipedia.org/wiki/Binary_tree给出的， 因为树是它自身的一种图。

Answer 5

这是使用 C++ STL（邻接列表）的 BFS 实现。这里使用三个 Array 和一个 Queue 来完成实现。

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

//Adding node pair of a Edge in Undirected Graph 
void addEdge( vector<int> adj[], int u, int v){
    adj[u].push_back(v);  // 1st push_back
    adj[v].push_back(u);  //2nd push_back
    //for Directed Graph use only one push_back i.e., 1st push_back() rest is same 
}
//Traversing through Graph from Node 0 in Adjacency lists way
void showGraph( vector<int>adj[], int size){
    cout<<"Graph:\n";
    for(int i=0; i<size ; i++){
        cout<<i;
        for( vector<int>::iterator itr= adj[i].begin() ; itr!=adj[i].end(); itr++){
        cout<<" -> "<<*itr;
    }
    cout<<endl;
}
}
//Prints Array elements
void showArray(int A[]){
    for(int i=0; i< 6; i++){
        cout<<A[i]<<" ";
    }
}


void BFS( vector<int>adj[], int sNode, int N){

    //      Initialization
    list<int>queue; //Queue declaration
    int color[N]; //1:White, 2:Grey, 3:Black
    int parentNode[N];  //Stores the Parent node of that node while   traversing, so that you can reach to parent from child using this 
    int distLevel[N];   //stores the no. of edges required to reach the node,gives the length of path

    //Initialization
    for(int i=0; i<N; i++){
        color[i] = 1;   //Setting all nodes as white(1) unvisited
        parentNode[i] = -1;  //setting parent node as null(-1)
        distLevel[i] = 0;  //initializing dist as 0
    }

    color[sNode] = 2;  //since start node is visited 1st so its color is grey(2)
    parentNode[sNode] = -1;  //parent node of start node is null(-1)
    distLevel[sNode] = 0;    //distance is 0 since its a start node
    queue.push_back(sNode);  //pushing start node(sNode) is queue

    // Loops runs till Queue is not empty if queue is empty all nodes are visited
    while( !queue.empty()){

    int v = queue.front();  //storing queue's front(Node) to v
    // queue.pop_front();//Dequeue poping element from queue

    //Visiting all  nodes connected with v-node in adjacency list
    for(int i=0; i<adj[v].size() ;i++){

        if( color[ adj[v][i] ] == 1){// if node is not visited, color[node]==1  which is white 
            queue.push_back(adj[v][i]);  //pushing that node to queue
            color[adj[v][i]]=2;  //setting as grey(2)
            parentNode[ adj[v][i] ] = v; //parent node is stored                distLevel[ adj[v][i] ] = distLevel[v]+1;  //level(dist) is incremented y from dist(parentNode)
        }
    }//end of for
    color[v]=3;
    queue.pop_front();//Dequeue

}

printf("\nColor: \n");showArray(color);
printf("\nDistLevel:\n");showArray(distLevel);
printf("\nParentNode:\n");showArray(parentNode);
}

int main(){

int N,E,u,v;//no of nodes, No of Edges, Node pair for edge
cout<<"Enter no of nodes"<<endl;
cin>>N;
vector<int> adj[N];  //vector adjacency lists

cout<<"No. of edges"<<endl;
cin>>E;

cout<<"Enter the node pair for edges\n";
for( int i=0; i<E;i++){
    cin>>u>>v;
    addEdge(adj, u, v);  //invoking addEdge function
}

showGraph(adj,N);  //Printing Graph in Adjacency list format
BFS(adj,0,N);  /invoking BFS Traversal
}