算法笔记：邻接表

邻接表存图

图的存储一般有邻接表和邻接矩阵两种。若图是稠密的，则宜采用邻接矩阵；图是稀疏的，则应改用邻接表。因为在众多考试中数据范围并不允许我们采用邻接矩阵所以着重描述一下邻接表的存图方式

定义

边权：代表当前边上的数值
点权：代表当前点上的数值
Vis数组：当前点是否被访问过
head数组：当前起点所属的编号
ver数组：下一条边
to数组：上一条边的编号

这里的编号通指代码中的变量tot

学习方法

[对于静态]知道怎么用的即可..记住存图的那个函数和如何遍历图（如果实在不懂含义是可以这么搞的）
[对于动态]没必要去学..因为动态写的话还很容易MLE 所以看自己喜好选择了其他的和静态的一样

扔代码

对于有边无权的情况 ``` //#define fre yes

include

using namespace std;

const int maxn = 100005;
bool Vis[maxn];
int head[maxn];
int ver[maxn];
int to[maxn];

int n,m;

templateinline void read(T&x)
{
x = 0;char c;int lenp = 1;
do { c = getchar();if(c == '-') lenp = -1; } while(!isdigit(c));
do { x = x * 10 + c - '0';c = getchar(); } while(isdigit(c));
x *= lenp;
}

void addedge(int x,int y)
{
ver[tot] = y;
to[tot] = head[x];
head[x] = tot++;
}

void kre(int x)
{
for (int i=head[x];~i;i=to[i])
{
int y = ver[i];//下一条边
if(Vis[y]) kre(y);
}
}

int main()
{
memset(head,-1,sizeof(head));

read(n);read(m);
for (int i=1;i<=m;i++)
{
    int x,y;
    read(x);read(y);
    addedge(x,y);
}
//遍历每一条边
for (int i=1;i<=n;i++) { memset(Vis,0,sizeof(Vis));kre(i); }
return 0;

}

</br>
对于有边有权的情况

//#define fre yes

include

using namespace std;

const int maxn = 100005;
bool Vis[maxn];
int head[maxn];
int edge[maxn];
int ver[maxn];
int to[maxn];

int n,m;

templateinline void read(T&x)
{
x = 0;char c;int lenp = 1;
do { c = getchar();if(c == '-') lenp = -1; } while(!isdigit(c));
do { x = x * 10 + c - '0';c = getchar(); } while(isdigit(c));
x *= lenp;
}

void addedge(int x,int y,int z)
{
ver[tot] = y;
edge[tot] = z;
to[tot] = head[x];
head[x] = tot++;
}

void kre(int x)
{
for (int i=head[x];~i;i=to[i])
{
int y = ver[i];//下一条边
if(Vis[y]) kre(y);
}
}

int main()
{
memset(head,-1,sizeof(head));

read(n);read(m);
for (int i=1;i<=m;i++)
{
    int x,y,z;
    read(x);read(y);read(z);
    addedge(x,y);
}
//遍历每一条边
for (int i=1;i<=n;i++) { memset(Vis,0,sizeof(Vis));kre(i); }
return 0;

}


</br>
手痒 还写了一份动态的（emmm..）

扔代码

//#define fre yes

include

using namespace std;

int n,m;

const int maxn = 256+10;
struct Node{
int ver;
int edge;
Node *to;
Node():to(NULL){}
};

struct VNode{
int from;
Node *Start;
VNode():Start(NULL){}
};
VNode Nmap[maxn];

templateinline void read(T&x)
{
x = 0;char c;int lenp = 1;
do { c = getchar();if(c == '-') lenp = -1; } while(!isdigit(c));
do { x = x * 10 + c - '0';c = getchar(); } while(isdigit(c));
x *= lenp;
}

void addedge(int x,int y,int z)
{
Node *now = new Node();
now->ver = y;
now->edge = z;
now->to = Nmap[x].Start;
Nmap[x].Start = now;
}

int main()
{
read(n);read(m);
for (int i=1;i<=m;i++)
{
int x,y,z;
read(x);read(y);read(z);
addedge(x,y,z);
}
for (int i=1;i<=n;i++)
{
for (Node *w = Nmap[i].Start;w!=NULL;w=w->to)
{
printf("%d %d %d\n",i,w->ver,w->edge);
}
} return 0;
}