链式前向星BFS

本文链接:http://i.cnblogs.com/EditPosts.aspx?postid=5399068

采用链式前向星的BFS:

#include <iostream>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <queue>

using namespace std;

typedef long long LL;

const int maxN =  + ;

const int maxM =  + ;

int head[maxN];

int visited[maxN];

int N, M;

struct EdgeNode

{

    int to;

    int w;

    int next;

};

EdgeNode Edges[maxM];

void BFS(int x)

{

    memset(visited, , sizeof(visited));

    queue<int> initQueue;

    for(int i = ; i <= N; i++)

    {

        if( !visited[i] )

        {

            visited[i] = ;

            initQueue.push( i );

            while( !initQueue.empty() )

            {

                i = initQueue.front(); //取得对头的节点，一定是下次待扩展的节点

                initQueue.pop();//队顶元素出队（出队代表着访问到了这个节点）

       　　　　　//遍历与当前节点相连的节点

                for(int j = head[i]; j !=  -; j = Edges[j].next)

                {

           　　　　　　 //如果没被访问，入队

                    if( !visited[ Edges[j].to ])

                    {

                        visited[ Edges[j].to ] = ;

                        initQueue.push( Edges[j].to );

                    }

                }

            }

        }

    }

}

int main()

{

    freopen("input.txt", "r", stdin);

    memset(head, -, sizeof(head));

    cin >> N >> M;

    for(int i = ; i <= M; i++)

    {

        int x, y ,z;

        cin >> x >> y >> z;

        Edges[i].to = y;

        Edges[i].w = z;

        Edges[i].next = head[x];

        head[x] = i;

    }

    memset(visited, , sizeof(visited));

    BFS();

    return ;

}