优化 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}
。首先 a
将 b,c,d
推入队列但未设置其已访问。然后b
将d
推入队列,之后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);
}
}
我正在学习 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}
。首先 a
将 b,c,d
推入队列但未设置其已访问。然后b
将d
推入队列,之后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);
}
}