首页 > 代码库 > 邻接表
邻接表
除了邻接矩阵外储存图的另一种方法,适用于稀疏图。
用一个有n结点,p条边的有向图,用a[i],b[i],l[i]分别表示第i条边的起点,终点,权值。first[x]表示x号结点连出的第一条边,next[i]表示与第i条边是同一个结点连出的下一条边,如果为0则表示已经没有下一条了。
初始化:用last[x]表示第x号结点目前已读入的最后一条边,方便操作
void init() { for (int i=1;i<=p;cin>>a[i]>>b[i]>>l[i],i++) if (last[a[i]]==0) first[a[i]]=last[a[i]]=i; else last[a[i]]=next[last[a[i]]]=i; }
调用:对于第x号结点,调用它连出的每一条边和每一个点
void print(int x) { int u=first[x]; while (u!=0) { cout<<b[u]<<endl;//输出终点 cout<<l[h]<<endl;//输出权值 u=next[u];//前往下一条边 } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。