邻接表

《邻接表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构在信息学竞赛中的应用图形结构——邻接表引出：在介绍完邻接矩阵之后，我们发现，邻接矩阵还是无法储存过大的图，例如一旦图的顶点数超过6000，就可能有内存溢出的危险。所以，我们需要找到一种新的方式来满足我们的需求。定义：邻接表，实际上就是一种由链表组成的图形数据结构，对于其每一个顶点，都用链表来记录它的出边。我们需要记录以下信息来储存图：1、对于每一个顶点，需要记录从该顶点连出的最后一条边。2、对于每一条边，需要记录由同一顶点连出的上一条边，以及该边所连向的顶点。例如，在像下面这样的图中：baBAO像这样一张图，

2、我们就可以这样来储存：1、O点连出的最后一条边记为b，而A和B都没有连出边，所以记为0。2、a是O连出的第一条边，连向A，所以上一条边记为0，连向的点记为A；而b的上一条变记为a，连向的点记为B。这就是这个邻接表的信息，如果我们需要加入一条由O连向C的边c，只需要：1、记录边c的信息：指向的点为C，上一条边为原本O点连出的最后一条边b。2、更新O点的最后一边为c。这样我们就可以完整维护邻接表。C++代码如下：structAdjlist{intprev;//上一条边intnode;//连向的点}adjlist[E];/

3、/定义邻接表的边intlast[N];//记录顶点连出的最后一条边intnum;//记录边的数量voidaddline(intp1,intp2){++num;adjlist[num].node=p2;//更新边adjlist[num].prev=last[p1];last[p1]=num;//维护顶点连出的最后一条边}PS：如果边带权值只需要加入权值元素就好了。分析：空间上，一个邻接表只需要占用的单元数目为N+2E。时间上，在结合了深度、广度优先算法之后，实际上，每访问一条边的时间复杂度只有O(1)。应用：总结：