图的存储

一、邻接矩阵

邻接矩阵就是开辟一个二维数组来唯一的表示一个图。有向图和无向图的存储方式又各有异同。

有向图：

我们设二维数组，其中点a[i][j]表示从点i到点j的距离，若距离不计，则a[i][j]记为1。

代码如下：

1   int n,m,a[105][105];
2   cin>>n>>s;       //n：点的个数  s：边数
3   for(int i=1;i<=s;i++)   //输入各点关系
4   {
5       int x,y;             
6       cin>>x>>y>>a[x][y];  //从x到y的距离为a[x][y]
7   }

无向图：

无向图之间两点间的关系可以看成从x到y，从y到x。

代码：

1  int n,m,a[105][105];
2  cin>>n>>s;       //n：点的个数  s：边数
3  for(int i=1;i<=s;i++)   //输入各点关系
4  {
5      int x,y;             
6      cin>>x>>y>>a[x][y];  //从x到y的距离为a[x][y]
7      a[y][x]=a[x][y];       //因为是无向图，两点可以互相连通
8  }

二、邻接表

邻接表存储法，又叫链式存储法。如图：

大多数情况下，只需要用数组模拟链表即可。

代码如下：

 1 #include<algorithm>
 2 #include<cmath>
 3 #include<iostream>
 4 #include<cstdio>
 5 #include<string>
 6 #include<stack> 
 7 using namespace std;
 8 const int mn=1001,mm=100001;
 9 struct Eg{
10     int ne;     //下一条边的编号
11     int to;     //这条边到达的点
12     int dis;    //这条边的长度
13 }eg[mn];
14 int he[mn],num_eg,n,m,u,v,d;
15 void add_eg(int from,int to,int dis)  //加入一条从from 到to距离为dis的单向边
16 {
17     eg[++num_eg].ne=he[from];
18     eg[num_eg].to=to;
19     eg[num_eg].dis=dis;
20     he[from]=num_eg;
21 }
22 int main()
23 {
24     num_eg=0;
25     cin>>n>>m;   //读入一条单向边
26     for(int i=1;i<=m;i++)
27     {
28         cin>>u>>v>>d;      //u，v之间有一条长度为d的边
29         add_eg(u,v,d);
30     }
31     for(int i=he[1];i!=0;i=eg[i].ne)//从一开始遍历所有边
32     {
33             //----
34     }
35     return 0;
36 }

两种方法各有优劣，需按具体情况调用。

原文地址：http://www.cnblogs.com/xdzxmuchen/p/16755062.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性