首页 > 代码库 > 建图方式一 之 “邻接链表”
建图方式一 之 “邻接链表”
唉o(︶︿︶)o ,我果然还是玩不了 邻接链表,捣鼓了一晚上,只实现了 DFS的搜索 ,BFS 至今还不会,快回宿舍了,等校赛后再研究吧
邻接链表:
n个顶点m条边的无向图,表示中有 n 个顶点表结点和 2m 个边表结点。(也就是说,每条边 u-v 在邻接表 中出现两次:一次在关于u的邻接表中,另一次在关于v的邻接表中)PS:注意是无向图,有向图时,DFS搜索会漏点,也就是说只能访问到当前点 指向 的 点;
优点:
便于查找任一顶点的关联边及关联点,查找运算的时间复杂性平均为O(m/n);
缺点:
要查找一个顶点的前驱顶点和以此顶点为终点的边、以及该顶点的入度就不方便了,需要扫描整个表,时间复杂度为O(n+e)。可以用十字邻接表改进;<------ PS:这是。。。。还没搞过呢!!!
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> const int maxe = 10001; using namespace std; struct node{ int to,w; node *next; }*head[maxe];//head[a]以a为起点的第一条边 int n,m; bool visbfs[maxe]={0}; bool visdfs[maxe]={0}; void init()//初始化 { memset(head,NULL,sizeof(head)); memset(visbfs,0,sizeof(visbfs)); memset(visdfs,0,sizeof(visdfs)); } void add(int a,int b,int c)//加边 { node *p = new node; p->to = b; p->w = c; p->next = head[a];//指向a的下一条边 head[a] = p; } void Print()//打印原图 { int i; for(i = 1;i<=n;i++) { node *q; for(q = head[i];q!=NULL;q=q->next) { printf("%d->%d %d\n",i,q->to,q->w); } } } void DFS(int x) { visdfs[x] = true; printf("%d\n",x); node *q; for(q = head[x];q!=NULL;q = q->next) { if(!visdfs[q->to]) DFS(q->to); } } int main() { int a,b,c,in; while(scanf("%d%d",&n,&m)) { init(); for(int i = 0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); } in = 1;//以1为例,开始遍历 puts("连接方式"); Print(); puts("dfs搜索"); DFS(in); } return 0; }
5 6
1 2 5
2 3 4
3 1 4
3 5 8
4 5 1
2 5 9
2 3 4
3 1 4
3 5 8
4 5 1
2 5 9
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。