图的实现

(1) 邻接矩阵!

开一个二维数组 G。G[i][j]表示边(i,j)的权。如果边(i,j)不存在，就令 G[i][j]=INF（当然，(i,i)不是一条边，G[i][i]也等于INF）。

邻接矩阵最大的缺点就是内存空间占用太大，内存浪费严重。

(2) 边目录!

设置三个数组 u[M]、v[M]、w[M]，分别表示起点、终点和权。

一般情况下，从文件中读取的图都是用边目录来表示的。

(3) 邻接表（链表）!

用一个列表列出所有与现结点之间有边存在的结点名称。

struct edge {  int u,v,w;  edge *next; } mem[M];        // mem相当于动态内存分配。 int size=-1; #define NEW(p) p=&mem[++size]; p->next=NULL edge *adj[N];       // adj代表以i为起点的边。 …… memset(adj, 0, sizeof(adj)); for (int e=0; e<m; e++) {  edge *p;  NEW(p); cin>>(p->u)>>(p->v)>>(p->w);  p->next=adj[p->u];  adj[p->u]=p;

}

如果想检查从 a 出发的所有边，那么可以

for (edge *e=adj[a]; e!=NULL; e=e->next)

{

// e->u是起点，e->v是终点，e->w是权

}

(4) 邻接表（静态数组）! 注意，在这个“邻接表”里放置的元素是边的序号，不是点的序号。所以还要和边目录配合使用。

int first[N];       // first表示从u出发的第一条边的序号 int u[M],v[M],w[M], next[M];  // next[e]表示编号为e的下一条边的序号 ...... memset(first, -1, sizeof(first)); for (int e=0; e<m; e++) {  cin>>u[e]>>v[e]>>w[e];  next[e]=first[u[e]];   // 插入一条边  first[u[e]]=e; }

如果想检查从 a 出发的所有边，那么可以

for (int e=first[a]; e!=-1; e=next[e])

{

// u[e]是起点，v[e]是终点，w[e]是权

}

(5) 邻接表（STL）!

头文件：<vector>

这种邻接表也要和边目录配合使用。只需把(4)中的代码换成以下代码：

vector<int> g[N];		// g表示从u出发的第i条边的序号
int u[M],v[M],w[M];     ...... for (int e=0; e<m; e++) {  cin>>u[e]>>v[e]>>w[e];  g.push_back(e); }		// 同样要和边目录配合使用

如果想检查从 a 出发的所有边，那么可以

for (int i=0; i<g[a].size(); i++)

{

int &e=g[a];

// u[e]是起点，v[e]是终点，w[e]是权

}