广度优先搜索(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");
}