优化 BFS 的实现

Optimizing an implementation of BFS

我正在学习 Graph 的基础知识并着手解决问题
https://www.hackerrank.com/challenges/bfsshortreach。代码工作正常,但我正在为单个测试用例获取 TLE。我将 cin/cout 更改为 printf/scanf 希望它被接受但没有成功。我现在的代码是

#include <iostream>
#include <queue>
#include <climits>
#include <stdio.h>
#include <queue>
#include <list>
#include <vector>

struct Graph
{
    int size;
    std::list<int> *adj;
};

Graph* createGraph(int size)
{
    Graph *graph = new Graph();
    graph->size = size;
    graph->adj = new std::list<int>[size];
    return graph;
}
void addEdge(Graph *graph, int source, int dest)
{
    graph->adj[source].push_back(dest);
    graph->adj[dest].push_back(source);
}

void printGraph(Graph *graph)
{
    for (int i = 0; i < graph->size; ++i)
    {
        for(std::list<int>::iterator it = graph->adj[i].begin(); it!= graph->adj[i].end(); ++it)
          {
            std::cout<<*it<<' ';
          }
          std::cout<<std::endl;
    }
}

void BFS(Graph *graph, int src)
{
    std::queue <int> nodes;
    std::vector<bool> v(graph->size,false);
    std::vector<int> distance(graph->size, INT_MAX);
    v[src] = true;
    distance[src] = 0;
    nodes.push(src);
    std::list<int>::iterator it;
    while(!nodes.empty())
    {
        int temp = nodes.front();
        v[temp] = true;
        nodes.pop();
        for(it = graph->adj[temp].begin(); it!= graph->adj[temp].end(); ++it)
          {
            if(!v[*it])
            {
                nodes.push(*it);
                int current = distance[temp] != INT_MAX? distance[temp] : 0;
                distance[*it] = std::min(current + 6, distance[*it]);
            }
          }
    }
    for (int i = 0; i < distance.size(); ++i)
    {
        int dist = distance[i] != INT_MAX ?  distance[i] : -1;
        if(i!= src)
        {
            printf("%d ", dist);
        }
    }
        printf("\n");
}

int main(int argc, char const *argv[])
{
    int T;
    scanf(" %d", &T);
    while(T--) {
        int n, m, s;
        // cin>>n>>m;m
        scanf(" %d %d", &n, &m);
        Graph *graph = createGraph(n);
        while(m--)
        {
            int x, y;
            // cin>>x>>y;
            scanf(" %d %d", &x, &y);
            addEdge(graph, x-1, y-1);
        }
        // cin>>s;
        scanf(" %d", &s);
        BFS(graph, s-1);
        // printGraph(graph);
    }
    return 0;
}

我认为这个算法的时间复杂度为O(m log n) 。而插入一条边所需的时间复杂度为 O(1) 。所以 AFAIK,这是我们能做的最好的(也许?)。我不确定这是否是存储图表的最佳方式。任何更好更快的存储图形的方法和改进它的建议都会很棒。

这不是优化问题。您应该在将它们放入 queue 之后立即将放入队列 true 的每个节点设置为已访问,否则您将多次重新访问某些节点。您将 node 放入队列但未将其访问设置为 true 并延迟此操作,直到您将该节点从队列中取出,然后将其访问设置为 true。那么会发生什么?考虑这个图表 V={a,b,c,d}E={a->b, a->c, a->d, b->d, c->d}。首先 ab,c,d 推入队列但未设置其已访问。然后bd推入队列,之后c也将d推入队列。所以你的队列看起来像这样 q={d,d,d}。所以你要访问 d 三次。而且这是很小的情况,你看大情况怎么会出大问题。

像这样:

queue <int> q;
q.push(source);
visited[source] = true;
while ( q.size() ){
    int current_node = q.front();
    q.pop();
    for ( int i=0; i<adjacencyList[current_node].size(); ++i ){
        int next_node = adjacencyList[current_node][i];
        if ( visited[next_node] )
            continue;
        dist[next_node] = dist[current_node] + 1;
        visited[next_node] = 1;
        q.push(next_node);
    }
}