图论——存储

图论存储

有两种方法

1°

：

邻接矩阵

 1 #include<iostream>
 2 using namespace std;
 3 int i,j,k,e,n;
 4 double g[101][101];
 5 double w;
 6 int main()
 7 {
 8     int i,j;
 9     for(i=1;i<=n;i++)
10         for(j=1;j<=n;j++)
11             g[i][j]=0xfffffff;
12     cin>>e;
13     for(k=1;k<=e;k++)
14     {
15         cin>>i>>j>>w;
16         g[i][j]=w;
17         g[i][j]=w;
18     }
19     ……
20 }

g[i][j]={表示从i到j的权值}

0x7f表示一个很大的数

0xaf表示一个很小的数

如果是double数组

memset(g,127,sizeof(g))清零为1.38*10^306

2°

链式前向星

：

链式前向星

理论上来说是采用链表模拟的

但大多数情况下使用数组模拟

当图的点数过大

且边较稀疏的情况下

为了防止爆空间

 1 #include<cstdio>
 2 using namespace std;
 3 const int maxn=1001,maxm=100001;
 4 struct Edge{
 5     int next;
 6     int to;
 7     int dis;
 8 }edge[maxm];
 9 
10 int head[maxn],num,n,m,u,v,d;
11 
12 inline add_edge(int from,int to,int dis)//加入一条从from到to权值为dis的单向边
13 {
14     edge[++num].next=head[from];
15     edge[num].to=to;
16     edge[num].dis=dis;
17     head[from]=num;
18 }
19 
20 int main()
21 {
22     num=0;
23     scanf("%d%d",&n,&m);//读入点数与边数
24     for(int i=1;i<=m;i++)
25     {
26         scanf("%d%d%d",&n,&v,&d);//u、v之间有一条权值为d的边
27         add_edge(u,v,d);
28     }
29     for(int i=head[i];i!=0;i=edge[i].next)//遍历从1开始的所有边
30     {
31         ……
32     }
33     return 0;
34 }

理论上来说

两种方法各有用武之地

按情况处理