Breadth-First Search

This is a discussion on Breadth-First Search within the C++ Programming forums, part of the General Programming Boards category; I know this is probably one of the most fundamental algorithms you will have to learn when you are a ...

  1. #1
    Registered User
    Join Date
    Sep 2002
    Posts
    92

    Breadth-First Search

    I know this is probably one of the most fundamental algorithms you will have to learn when you are a CS major but I cannot seem to understand this part. I need to understand the BFS algorithm and this is what I have so far:
    Code:
    #include <string>
    #include <queue>
    
    // aren't typedef's cool?
    typedef string Vertex;
    typedef queue<Vertex> queue;
    
    void BFS(V1, V2) {
    queue Q;
    // find the first vertex and push it in
    Q.push(V1);
    
     while(!Q.empty()){
       Vertex t = Q.front();
       // for(every unvisited neighbor of n) --- HOW DO YOU KNOW?
             Q.push(n);
             if(n == V2) Success(Q);
       // }
       Q.pop();
       Failure(Q);
     }
    }
    My question is how can you process the for loop... a.k.a how do you know which ones are unvisited and which ones are not. Assume that we are given a queue data strucutre and the start vertex and goal vertex.

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Typically the program also keeps an array of bools where each index corresponds to a particular vertex. When a vertex is added to the queue then the bool is set to true. So just check to see if it is set to true before adding to the queue and if it is then skip it.

    Another idea is to include a bool in the vertex struct.

  3. #3
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146

    Re: Breadth-First Search

    Originally posted by supaben34
    // aren't typedef's cool?
    typedef queue<Vertex> queue;
    Typedefs are cool, but that one in particular looks suspect to me. I'd suggest a unique identifier like v_queue or something rather than using 'queue' which is already defined elsewhere.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Shortest Path Maze Solver (Breadth Search Help)
    By Raskalnikov in forum C Programming
    Replies: 5
    Last Post: 04-07-2009, 08:41 PM
  2. Using Breadth First Search
    By neandrake in forum C++ Programming
    Replies: 4
    Last Post: 05-06-2005, 06:13 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21