廣度優先搜尋(BFS) C++實作

本文提供了一個廣度優先搜尋的C++實作~

#include <iostream>
#include <vector>
#include <list>
#include <queue>

using namespace std;


//圖上的一個頂點
class TableEntry
{
public:
    list<int> vertexs;
    int dist;
    int path; //最短路徑的上一個頂點
};
typedef vector<TableEntry> Table;

class Bfs
{
public:

    void IntializeTable(Table & T)
    {
        ReadGraph(T);
        for (int i = ; i < T.size(); i++)
        {
            T[i].dist = -;
            T[i].path = -;
        }

    }

    void Run(Table & T, int start)
    {
        T[start].dist = ;
        queue<int> Q;
        Q.push(start);

        while (!Q.empty())
        {
            int v = Q.front();
            Q.pop();

            list<int>::iterator it;
            for (it = T[v].vertexs.begin(); it != T[v].vertexs.end(); it++)
            {
                if (T[*it].dist < )
                {
                    T[*it].path = v;
                    T[*it].dist = T[v].dist + ;
                    Q.push(*it);
                }
            }

        }
    }

    void PrintPath(Table & T, int v)
    {
        if (T[v].path >= )
        {
            PrintPath(T, T[v].path);
            cout << "->";
        }
        cout << v;
    }

private:
    //這裡大家自行發揮~
    void ReadGraph(Table & T)
    {
        T[].vertexs.push_back();
        T[].vertexs.push_back();
        T[].vertexs.push_back();
        T[].vertexs.push_back();
        T[].vertexs.push_back();
        T[].vertexs.push_back();
        T[].vertexs.push_back();
        T[].vertexs.push_back();
        T[].vertexs.push_back();
        T[].vertexs.push_back();
        T[].vertexs.push_back();
    }
};



int main()
{
    Table T(, TableEntry());
    Bfs bfs;
    bfs.IntializeTable(T);
    bfs.Run(T, );
    bfs.PrintPath(T, );
    cout << endl << T[].dist << endl;

    system("PAUSE");
}