荣成信用建设官方网站,WordPress文章彩色标签,app软件小程序网站建设,企业logo设计思路图的存储
链式前向星 链式前向星和邻接表很相似#xff0c;只是存储方式变成了数组。 链式前向星一般要用到一个结构体数组和一个一维数组,结构体数组edges中包括三个变量。结构体数组的大小一般由边的大小决定。
edges数组中的to代表的是某条边的终点v。w代表的是这条边的…图的存储
链式前向星 链式前向星和邻接表很相似只是存储方式变成了数组。 链式前向星一般要用到一个结构体数组和一个一维数组,结构体数组edges中包括三个变量。结构体数组的大小一般由边的大小决定。
edges数组中的to代表的是某条边的终点v。w代表的是这条边的权值。next代表的是上一条和本条边同起点u的边的编号。
struct node
{int to;int w;int next;
}edges[m]; 怎样才能知道和本条边同起点的上一条边的编号呢用一个head数组记录以每第i为起点的边的编号,实际上这里的第一条边存储的位置其实是在以i为起点的所有边的最后输入的那个编号。
3.添加边的输入: for(i1;im;i) { scanf(%d %d %d,u,v,w); edges[i].tov; edges[i].ww; edges[i].nexthead[u]; head[u]i; } head初始化为0i表示每条边的编号。每一次都要更新相应的head。
如果按照索引顺序next表示下一条边的存储位置如果按照添加顺序next即为上一条添加的边的位置。
所以输入顺序和存图的顺序遍历顺序是相反的。
4.插入的模拟过程 5.代码如下 #includestdio.h int n,m; struct node { int to; int w; int next; }edges[100]; int head[100]; main() { int i,j,u,v,w; scanf(%d %d,n,m); for(i1;im;i) { scanf(%d %d %d,u,v,w); edges[i].tov; edges[i].ww; edges[i].nexthead[u]; head[u]i; } for(i1;in;i) { for(jhead[i];j!0;jedges[j].next) { printf(%d-%d%d\n,i,edges[j].to,edges[j].w); } } }
