简单的bfs
2018-06-18 03:49:02来源:未知 阅读 ()
这里主要是写的一个简单的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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 加边的无向图--并查集 2020-04-10
- 排兵布阵 2020-02-21
- 二叉树(四)二叉堆 2020-02-03
- BFS和队列 2020-01-18
- C/C++产生随机数 2019-12-25
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash