首页 > 代码库 > 建图方式一 之 ”前向星“ BFS&&DFS 简单应用
建图方式一 之 ”前向星“ BFS&&DFS 简单应用
三种建图方式,邻接矩阵、前向星(边表集)、邻接链表!
耗时一晚上 ,好好研究了一下 前向星,因为我的指针用的实在是很烂,所以还是 入赘 前向星吧。
问了学长,看了大牛们的博客,终于有点收获了,个人认为 前向星Very Well。
前向星
建图方法:
以储存边的方式来储存图。在构造图时,把边存放在数组里,不需使用指针,只需一个 next 即可是整个图构建完成 。
适用条件:
点集特别多的稀疏图,边数多且繁杂,开邻接矩阵会浪费大量内存。
时间复杂度:
O(m),并不比邻接链表差。
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #define mae 10010 // 最大边数 #define mav 110 // 最大顶点数 using namespace std; struct EdgeNode{ int v; int w; int next; }g[mae]; int head[mae]; int t = 1;//edgenum 作用 int n, m; bool visdfs[mav]; bool visbfs[mav]; void init() //初始化 { memset(head, 0, sizeof(head)); memset(visbfs,0,sizeof(visbfs)); memset(visdfs,0,sizeof(visdfs)); t = 1; } void add(int a,int b,int c)//加边 { g[t].v = b; //当年节点 a指向b g[t].w = c; // a->b 边的权值是 c g[t].next = head[a]; // next指向 上一条以a为起点的边 head[a] = t; //head[a] 表示以a为起点的最后输入的边的 编号 t++; // 给每一条以构建的边 制定编号(edgenum) } void Print() { int k,i; for(i = 1; i <= n; i++) { if(head[i])//找边 { for(k = head[i]; k != 0; k = g[k].next) { printf("%d->%d %d\n", i, g[k].v, g[k].w); } } } } void DFS(int x) { visdfs[x] = true; printf("%d\n",x); for(int i = head[x]; i != 0; i = g[i].next) { if(!visdfs[g[i].v]) { DFS(g[i].v); } } } void BFS(int x) { int q[mav];//队列 int jin = 0,chu=0,st; q[jin++] = x; visbfs[x] = true;//标记 while(chu < jin) { st = q[chu++]; printf("%d\n",st); for(int k = head[st]; k != 0; k = g[k].next) { if(!visbfs[g[k].v]) { visbfs[g[k].v] = true; //标记 q[jin++] = g[k].v; } } } } int main() { int U,V,W,in; while(~scanf("%d%d",&n,&m)) { init(); for(int i = 1; i <= m; i++) { scanf("%d%d%d",&U,&V,&W); add(U,V,W); } in = 1;//此处以1为例开始搜索 puts("建图为"); Print(); puts("dfs访问结果:"); DFS(in); printf("-----------\n"); puts("bfs访问结果:"); BFS(in); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。