链式前向星
int cnt; //边的编号 struct edge{
//边的结构体 int from,to,w,next; //from是边的起点（这个可有可无，因为他可以用head数组表示） //to是边的终点 w是权值 next表示这条边指向的下一条相同起点的边的编号 }edge[maxn*maxn]; //maxn为图中最大节点编号 int head[maxn]; //head的下标表示节点的编号 存的是以这个节点为起点的添加进来的边的最后一个编号 void init(){
//建图之前一定要初始化！！！ memset(head,-1,sizeof(head)); //没有边时为-1 cnt=0; //第一条边编号为0 } void addedge(int u,int v,int w){
//添加边（建图） u是起点 v是终点 w是权值 edge[cnt].from=u;//结构体没定义from这句可以不要 edge[cnt].to=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } int main(){
int m; //边的总数 题中给出边的总数，那用链式前向星就很方便了 int u,v,w; init(); for(int i=1;i<=m;i++){
cin>>u>>v>>w; addedge(u,v,w); } } 
比如节点1为起点的边有编号分别为1，2，3的边 向节点1插入边1的时候，这时的初始head[1]是等于-1的，然后进行e[1].next=head[1]（这时边1的指向-1），然后进行head[1]=1（1为起点的最后一条边为边1，再插入以节点1为起点的边的时候，比如边2，然后进行e[2].next=head[1] （此时的head[1]存的是边1，进行e[2].next=head[1]时边2的指向边1，然后在遍历时的那个i=e[i].next就变成了边2跳向了边1）,插入以1为起点的边3时也是如此，边3就指向了边2，head[1]就更新成了3。
因为最后存的是边3，遍历时就是从边3开始，然后指向边2，然后指向边1，然后就指向-1，-1时退出遍历
就这样可以通过对所有节点建边，进行建图
遍历图
for(int i=1;i<=n;i++) //遍历节点1~n for(int j=head[i];~j;j=edge[j].next) //遍历以i为起点的边 ~这个符号，只有当j=-1是，他才等于0，终止循环,也可以用 j!=-1 printf("%d -> %d\n",i,edge[j].to); 遍历以u为起点的边
for(int i=head[u];~i;i=edge[i].next) printf("%d -> %d\n",u,edge[i].to); 版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/222320.html原文链接：https://javaforall.net
