简单的bfs

2018-06-18 03:49:02来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

这里主要是写的一个简单的bfs,实例运行了RMAT10无向图,总共有1024个顶点。这种简单的bfs算法存在很明显的缺陷,那就是如果图数据过大,那么进程将会直接被系统杀死。

代码如下:

#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <sys/types.h>
#include <unistd.h>
#include <sys/stat.h>
#include <fcntl.h>
using namespace std;
#define MAX_NODES 1024
float edges[MAX_NODES][MAX_NODES];
bool IsVisited[MAX_NODES];
int main(){
	for(int i=0;i<MAX_NODES;i++){
		for(int j=0;j<MAX_NODES;j++)
			edges[i][j]=-1;//-1 represents no link
		IsVisited[i]=false;
	}
	int fd1;
	fd1=open("../zhangyangData/RMAT10_undirect",O_RDONLY,0);
	if(fd1==-1){
		cout<<"error "<<endl;
		return 0;
	}
	int s,t;
	float f;
	while(read(fd1,&s,4)>0&&n>0){
		read(fd1,&t,4);
		read(fd1,&f,4);
		//cout<<s<<" "<<t<<":"<<f<<endl;
		edges[s][t]=1;
	}
	int flag=0,count=0;
	for(int i=0;i<MAX_NODES;i++){
		for(int j=0;j<MAX_NODES;j++){
			if(edges[i][j]==1) flag=1;
			//cout<<edges[i][j]<<" ";
		}
		if(flag) count++;
		//cout<<endl;
	}
	cout<<count<<endl;
	vector<int> ves;
	ves.push_back(1023);
	while(!ves.empty()){
		int next_node=*ves.begin();
		cout<<next_node<<" ";
		IsVisited[next_node]=true;
		cout<<IsVisited[next_node]<<endl;
		ves.erase(ves.begin());
		for(int i=0;i<MAX_NODES;i++){
			if(edges[next_node][i]>0&&IsVisited[i]==false){																					ves.push_back(i);
			       IsVisited[i]=true;
			}
		}
		if(ves.empty()){
			for(int i=0;i<MAX_NODES;i++){
				if(IsVisited[i]==false)
					ves.push_back(i);
			}
		}
	}
	return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:浮点数据有损压缩算法 附完整C代码

下一篇:关于VC++6.0与WIN10系统不兼容的解决办法