1． 邻接表的结点结构
边结点结构
邻接表中每个表结点均有两个域:
① 邻接点域adjvex
存放与vi相邻接的顶点vj的序号j。
② 链域next
将邻接表的所有表结点链在一起。
注意：
如果带权图，则在表结点中还应增加一个保存权值等相关信息info。
2．邻接表的表示
对于无向图，vi的邻接表中每个表结点都对应于与vi相关联的一条边。因此，将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。
注意：
n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。
对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。
注意：
n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。
4．有向图的逆邻接表
在有向图中，为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。
入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。
【例】
注意：
n个顶点e条边的有向图，它的接表表示中有n个顶点表结点和e个边表结点。
邻接链表表示的图类
const int MaxVertices=100;
typedef int VerT;
typedef int DistT;
struct Edge{ int dest; //邻接顶点下标
DistT weight; //边的权值，或更多
Edge *next; //指针
};
struct item { VerT data; //顶点数据
Edge *adj; //邻接边的指针
};
item Vertices[MaxVertices]; //顶点的数组
建立一个无向图的邻接链表:
void AdjTWGraph::CreatG(int n,int e)
{ int vi,vj; DistT w;
numE=e; numV=n;
cout<<"\n 输入顶点的信息（整型）：" ;
for (int i=1; i<=numV; i++ ) { cout<<"\n "<<i<<": ";
cin>>Vertices[i].data;
}
for ( int i=1; i<=numE; i++ )
{ cout<<"\n 输入边的信息（顶点号vi 顶点号vj 边的权值W）：";
cin>>vi>>vj>>w;
//---------------------- 在第vi条链表上，链入边（vi,vj）的结点
Edge *q=new Edge;
q->dest=vj; q->weight=w; q->next=NULL;
//vj是vi的邻接顶点，w是权值
if(Vertices[vi].adj==NULL) Vertices[vi].adj=q; //第一次插入
else //非第一次插入
{ Edge *curr=Vertices[vi].adj, *pre=NULL;
while (curr!=NULL && curr->dest<vj )
{ pre=curr; curr=curr->next; }
if ( pre==NULL ) //在第一个结点前插入
{ q->next=Vertices[vi].adj; Vertices[vi].adj=q; }
else {q->next=pre->next; //在其他位置插入
pre->next=q;
}
}
//-------------------在第vj条链表上，链入边（vj,vi）的结点
Edge *p=new Edge;
p->dest=vi; p->weight=w; p->next=NULL;
if(Vertices[vj].adj==NULL) Vertices[vj].adj=p; //第一次插入
else //非第一次插入
{ Edge *curr=Vertices[vj].adj, *pre=NULL;
while (curr!=NULL && curr->dest<vi )
{ pre=curr; curr=curr->next; }
if ( pre==NULL ) //在第一个结点前插入
{ p->next=Vertices[vj].adj; Vertices[vj].adj=p; }
else { p->next=pre->next; //在其他位置插入
pre->next=p;
}
}
} //for ( int i=1; i<=numE; i++ )
} //函数结束
该算法的时间复杂度是 O(n+2e) ，在上述算法中去掉黑体部分语句，就是有向图的建立算法，其时间复杂度为 O(n+e)
本文转自博客园知识天地的博客，原文链接：【转】图的邻接链表 adjacent list of graph，如需转载请自行联系原博主。
