邻接表
创建邻接表的代码如下。//双向图数据*2int n,m,i;int u[6],v[6],w[6];//u、v,w和next的数组比边数的最大值要大
int first[5],next[5]; //first的数组比点数的最大值要大
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)//初始化first数组下标1~n的值为-1，表示1~n顶点暂时都没有边
first[i]=-1;
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&u[i],&v[i],&w[i]);//读入每一条边
next[i]=first[u[i]];
first[u[i]]=i;
}
遍历1号顶点所有边的代码如下。
k=first[1];// 1号顶点其中的一条边的编号（其实也是最后读入的边）
while(k!=-1) //其余的边都可以在next数组中依次找到
{
printf("%d %d %d\n",u[k],v[k],w[k]);
k=next[k];
}
遍历每个顶点的所有边的代码如下。
for(i=1;i<=n;i++)
{
k=first[i];
while(k!=-1)
{
printf("%d %d %d\n",u[k],v[k],w[k]);
k=next[k];
}}
时间空间复杂度是O(M)，遍历每一条边的时间复杂度是也是O(M)。
如果一个图是稀疏图的话，M要远小于N2。
因此稀疏图选用邻接表来存储要比邻接矩阵来存储要好很多。
www.99jianzhu.com/包含内容：建筑图纸、PDF/word/ppt 流程，表格，案例，最新,免费下载,施工方案、工程书籍、建筑论文、合同表格、标准规范、CAD图纸等内容。