邻接矩阵和邻接表的使用

邻接矩阵

为了遍历一个图，我们使用了邻接矩阵，及用$a_{i,j}$表示由a到b的边权
注：若这两个点不相连或$i=j$，那么这个值就会设定为一个非正常的值，以便遍历时特判不走这条边
使用：

scanf("%d%d%d",&x,&y,&z);//x指向y，边权为z a[i][j]=z;b[1] = 0; for(int i=1;i<=n;++i)//总共n个点if (a[1][i]) b[i]=b[1]+a[1][i];//到点i

邻接表

使用邻接矩阵会有许多不足之处，如空间时间浪费太多
所以我们又使用了另一种存储方法——邻接表
我们定义如下

我们定义head_A为A读入的最后一条边（为了便于分辨，把数字的编号写成大写英文字母）
$a_k.to$为$k$这条边连向的点
$a_k.l$为$k$这条边的边权
$a_k.next$为和$k$源头相等的上一条边
使用：

scanf("%d%d%d",&x,&y,&z);//读入 a[++tot].to=y;//tot是这条边的编号，指向y a[tot].l=z;//边长为z a[tot].next=head[x];//它的上一条边是加载它之前的最后一条边 head[x]=tot//现在的最后一条边是它b[1] = 0; for(int i=head[1];i;i=a[i].next)//从1的最后一条边开始遍历，每一次遍历上一条边，直到没有上一条边，及遍历完 {x=1;//源头y=a[i].to;//指向哪z=a[i].l;//边权 }

总结

以上是生活随笔为你收集整理的邻接矩阵和邻接表的使用的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。