邻接表

邻接表必要性：由于邻接矩阵无法存储带自身环和重边的图，所以有时不得不采用邻接表来存储图。

所谓邻接表：就是把从同一个顶点发出的边连接在同一个称为边链表的单链表中。边链表的每个结点代表一条边，成为边结点。每个边结点有两个域：该边终点的序号以及指向下一个边结点的指针。

存储顶点信息的数组称为顶点数组，在顶点数组中，每个元素有两个成员：一个成员用来存储顶点信息；另一个成员为该顶点的边链表的表头指针。

邻接表又称为出边表

逆邻接表又称为入边表；

例题：用邻接表存储有向图，并输出各顶点的出度和入度。

输入表述：包含多个测试数据，每个测试数据包含一个无权有向图，第一行为顶点数和边数，接下来m行，每行两个正整数，表示边的起点和终点。

 

#include<cstdio> #include<iostream> #include<cstring> using namespace std; #define MAXN 100 struct ArcNode///边结点 { int adjvex;///有向边的另一个邻接点的序号 ArcNode *nextarc;///用来构造边链表的边结点指针 }; struct VNode///顶点 { int data; ArcNode *head1;///出边表的表头指针 ArcNode *head2;///入边表的表头指针 }; struct LGraph///图的邻接表存储结构 { VNode vertexs[MAXN];///顶点数组 int vexnum,arcnum;///顶点数和边数 }; LGraph lg; void CreateLG() { ArcNode *pi; int v1,v2; for(int i=0;i<lg.vexnum;i++) { lg.vertexs[i].head1=NULL; lg.vertexs[i].head2=NULL; } for(int i=0;i<lg.arcnum;i++) { scanf("%d%d",&v1,&v2); v1--; v2--; pi=new ArcNode;///插入链表（邻接表） pi->adjvex=v2; pi->nextarc=lg.vertexs[v1].head1; lg.vertexs[v1].head1=pi; pi=new ArcNode;///插入链表（逆邻接表） pi->adjvex=v1; pi->nextarc=lg.vertexs[v2].head2; lg.vertexs[v2].head2=pi; } } void DeleteLG()///释放图G邻接表各顶点的边链表中所有边结点所占的空间 { ArcNode *pi; for(int i=0;i<lg.vexnum;i++) { pi=lg.vertexs[i].head1; while(pi!=NULL)///释放空间 { lg.vertexs[i].head1=pi->nextarc; delete pi; pi=lg.vertexs[i].head1; } pi=lg.vertexs[i].head2; while(pi!=NULL) { lg.vertexs[i].head2=pi->nextarc; delete pi; pi=lg.vertexs[i].head2; } } } int main() { int id,od; ArcNode *pi; while(scanf("%d%d",&lg.vexnum,&lg.arcnum)!=EOF) { if(lg.vexnum==0) break; CreateLG(); for(int i=0;i<lg.vexnum;i++) { od=0; pi=lg.vertexs[i].head1; while(pi!=NULL) { od++; pi=pi->nextarc; } if(i==0) printf("%d",od); else printf(" %d",od); } printf("\n"); for(int i=0;i<lg.vexnum;i++) { id=0; pi=lg.vertexs[i].head2; while(pi!=NULL) { id++; pi=pi->nextarc; } if(i==0) printf("%d",id); else printf(" %d",id); } printf("\n"); DeleteLG();///释放 } return 0; }