首页 > 其他 > 详细

图的浅谈(图的贮存)

时间:2019-04-29 12:41:50      阅读:101      评论:0      收藏:0      [点我收藏+]

1.有关图的储存

初始化及变量设置

#define MANX 3500
#define INF 99999999

book[MANX],dis[MANX],e[MANX][MANX]//e表示邻接矩阵

for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    if(i!=j)e[i][j]=INF;

 

<1>.领接矩阵——稠密图

设有n个顶点,用一个n*n的二维数组进行储存,下标表示连接到的两点,内容表示距离

for(i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        if(e[a][b]==INF||e[a][b]>c){
        e[a][b]=c;
        e[b][a]=c;    
        }
    }

 

<2>.邻接表——稀疏图

用五个数组,分别是w,u,v,first,next(w保存权值,u,v分别表示该边连接的两点,用first与next的关系进行图之间的关系连接)

for(i=1;i<=n;i++)
first[i]=-1;
for(i=1;i<=m;i++){
    cin>>u[i]>>v[i]>>w[i];
    next[i]=first[u[i]];
    first[u[i]]=i;
}

说明:next数组储存有关边的编号,从而用数组进行查找,而first[i]储存的则是点i最后连接的边的编号,不过之前的也不用担心丢失,next帮你存好了。

遍历代码如下

for(i=1;i<=n;i++){
    k=first[i];
    while(k!=-1){
        cout<<u[k]<<" "<<v[k]<<" "<<w[k]<<endl;
        k=next[k];
    }
}

 

图的浅谈(图的贮存)

原文:https://www.cnblogs.com/dancemu/p/10772081.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!