自己之前一直使用邻接矩阵存图，很容易理解，一直听说过邻接表的存图法，但一直没有用过，后来才用了，这里简单说一下。
为什么要使用邻接矩阵，我个人的理解就是对于稀疏图，使用邻接矩阵太浪费空间，遍历也浪费时间，所以就要使用邻接表。这里就说一下我个人的一些理解。
邻接表的存的是边，对边进行编号，1号边，2号边，3号边.....再在每条边上记录边的顶点以及权值等信息。以下图为例
默认各个边权值均为1，添加顺序为 1 2，1 4，1 3，3 4，2 4。依次为1号边，2号边，以此类推。我们记录下了边，还要记录下顶点等信息。
首先我们需要一个head数组，来记录由某一个顶点发出的任意一条边的编号，其次需要一个结构体来记录终点，权值等信息。
struct Node{
int v=0; //终点
int val=0; //权值
int next=0; //下一条边的编号
Node(){v=0;val=0;next=0;}
}node[200100];然后我们看一下添加操作。
void addage(int u,int v,int val){ //起点u 终点v 权值 val
node[++top].v=v;
node[top].val=val;
node[top].next=head[u];
head[u]=top;
}top可以从一开始，或者0开始，都可以，表示第一条边的编号。然后每次进来一个起点，终点，权值。就意味着有一条新的边加入，所以首先top++，然后记录权值，然后第四行的代码node[top].next表示该条边的下一条边（两条边均由一个顶点发出），而head[u]在上一次添加以u为起点的边时，head[u]就记录下了该条边的编号，所以node[top].next=head[u];就记录下了下一条边的编号。
以我们上边的图为例，首先加入点1 2，即1号边，此时：
node[1].v=2;
node[1].val=1;
node[1].next=head[1]; //此时head[1]=0
head[1]=1; //这里的1为1号顶点，与上边的1号边注意区分然后我们加入点1 4，即2号边，此时：
node[2].v=4;
node[2].val=1;
node[2].next=head[1]; //此时head[1]=1
head[1]=2; //这里的1为1号顶点，上边的2是2号边然后我们加入点1 3，即3号边，此时：
node[3].v=3;
node[3].val=1;
node[3].next=head[1]; //此时head[1]=2
head[1]=3; //这里的1为1号顶点，上边的3是3号边讲到这里应该差不多明白加入边时的操作了，下面看一下遍历，无论是bfs还是dfs，都有一个起点，然后遍历这个起点能到达的所有的边，在这里，我们对于任意一个起点u，可以采用如下方法遍历：
for(int i=head[u];i;i=node[i].next){ //遍历某个顶点的所有边
int d=node[i].v; //该条边的终点
if(){
...... //其他操作
}
}
京公网安备 11010502036488号