这篇文章主要来讲一下邻接矩阵 邻接表 链式前向星（本篇需要具备一定图的基础知识，至少邻接矩阵之前要会，这里主要讲解邻接表和链式前向星）
我不大喜欢说废话，所以直接上图
邻接矩阵：用二维数组存储点与点之间的关系，也就是这样
但是仔细想想，有很多不必要的空间浪费，比如说（2，5）这个空间就没有必要，那我们可以像一个办法来去掉这些多余的空间，邻接矩阵我们用的是二维数组，那这里我们想一下，根据每一个点到另一个点不同，如果要去掉那些无用点的话，每一个起点所对终点的数量不同，所以我们要用到动态数组。
而动态数组，在C语言里面我们用链表，如果是C++的话，用vector。最后就成这样
所以说我们这里每一层都是一个动态数组，然后动态数组里面存的是终点的标号，比如说1连了2和3，那就把2 3放到1的后面（注意，插入顺序不同，那遍历时的顺序也不同，如果是用的vector那遍历的顺序就是插入的顺序，如果是用的链表，那遍历的顺序就会倒过来，因为链表的插入通常使用头插法，当然，你使用尾插法也可以）
下面直接上代码
先来一个链表的
zhetypedef struct edgeNode{
int index;//当前结点所对应的元素在头节点数组中的下标
int value;
edgeNode *next;//下一个兄弟
}edgeNode;
typedef struct vertexnode{
int data;
edgeNode *firstedge=NULL;
}vertexnode;
vector<vertexnode> V;下面是用的vector
typedef struct edge{
Bindex index;
Value value;
}edge;
typedef struct vertex{
int index;//可有可无，根据你设定的下标来，如果你把1存在V[0]的话就需要
vector<edge>edge;
}vertex;
vector<vertex> V;其中value代表的是权值，这个地方还可以简化（注意下标），直接用一个结构体，然后套个二维的vector就行了
vector<vector<edge> > V;
所以仔细一看，这不就是一个二维数组吗？没错，所以在一定程度上，我认为邻接表其实就是邻接矩阵把那些没必要的点给扣掉。
这里我就直接放深搜和广搜的源代码了
vector<bool>book;
void bfs(vector<vertex>V){
queue<vertex>Que;
Que.push(V[1]);
book[Que.front().index]= true;
while(!Que.empty()){
//将当前标号的所有连接点入队
int i=0;
cout<<Que.front().index<<" ";
while(i<Que.front().edge.size()){
if (book[Que.front().edge[i].index]!=true) {
Que.push(V[Que.front().edge[i].index]);
book[Que.front().edge[i].index]=true;
}
i++;
}
Que.pop();
}
}
void dfs(vector<vertex>V,int i){
if (book[i]==true)return;
cout<<V[i].index<<" ";
book[V[i].index]=true;
for (int j = 0; j < V[i].edge.size(); ++j) {
if(book[V[i].edge[j].index]!=true){
dfs(V,V[i].edge[j].index);
// book[V[i].edge[j].index]=true;
}
}
}边集数组
在讲链式前向星之前提一嘴这个，其实这个就是BellMan-Ford算法的存图方法，废话不说，直接上代码，顺便把BellMan-Ford也丢上来
#include <bits/stdc++.h>
using namespace std;
typedef struct edge{
int u,v,w;
}edge;
int main(){
int n,m;
cin>>n>>m;
edge e[m];
//边集数组存储方式
for (int i = 0; i < m; ++i) {
int u,v,w;
cin>>u>>v>>w;
e[i]={u,v,w};
}
int dis[n+1];
fill(dis,dis+n+1,0x3f3f3f);
dis[1]=0;
for (int i = 1; i <= n-1; ++i) {
for (int j = 0; j < m; ++j) {
if(dis[e[j].v]>dis[e[j].u]+e[j].w){
dis[e[j].v]=dis[e[j].u]+e[j].w;
}
}
}
//检查负权回路
int flag=0;
for (int j = 0; j < m; ++j)
if (dis[e[j].v] > dis[e[j].u] + e[j].w) {
flag = 1;
break;
}
cout<<(dis[n]==0x3f3f3f?-1:dis[n]);
}链式前向星
这里先放下代码，大家可以踩一下怎么搞
typedef struct edge{
int to;//终点
int w;//权重
int next;//兄弟结点在e数组中的下标
}edge;
//这里使用动态数组，使用普通数组也是可以的
vector<edge>e;
vector<int>head;//建议从1开始存，其值是指向一个e的下标其实链式前向星，我个人觉得，可以简单理解为邻接表的降为
细看操作
首先来看边的结构
假如，我们有一个无向图
假如说，我们输入一条边： 1 2 5
那这个时候，我们把e[0]的to设置为2，w设置为5。（在此之前head数组要初始化，建议值赋值为-1）
然后因为2 5我们存在e[0]里面的，又表示的是1->2这一条边，我们把它连接在head[1]的后面，本来head[1]=-1的，我们把-1赋值给e[0]的next；后面同理，如果又要插入一条边为1 4 3的话，那e[1]的话，存储的值就是:4 3 0（0是head[1]插入当前结点之前的值），这样我们就有把它像邻接表一样给连起来了。
当然如果你要弄成无向图的话，再反过来添加就可以了
如果是无向图的话，插入第一个点是这样的
然后，我们把1 4 3插入（这个图因为是无向图，所以这个地方，e的下标是2）
所以说这个插入顺序和链接顺序有点像栈，我们head存储的一定是最后一个插入的边的下标，下面我直接上代码
#include <bits/stdc++.h>
using namespace std;
typedef struct edge{
int to;
int w;
int next;
}edge;
//这里使用动态数组，使用普通数组也是可以的
vector<edge>e;
vector<int>head;
vector<bool>book;
void bfs(vector<int> head){
queue<int>Q;
Q.push(1);
book[1]=true;
int j=e[head[1]].to;
while(!Q.empty()){
int next=head[Q.front()];
while(next!=-1){
//这里做个处理，如果遇到走过了的，就跳过
if(book[e[next].to]==true){
next=e[next].next;
continue;
}
j=e[next].to;
Q.push(j);
book[j]=true;
next=e[next].next;
}
cout<<Q.front();
Q.pop();
}
}
int main(){
int n,m;
cin>>n>>m;
for (int i = 0; i <= n; ++i) {
head.push_back(-1);
book.push_back(false);
}
// int cnt = 0;用普通数组的做法
for (int i = 0; i < m; ++i) {
int u,v,w;
cin>>u>>v>>w;
e.push_back({v,w,head[u]});
head[u]=e.size()-1;
e.push_back({u,w,head[v]});
head[v]=e.size()-1;
// e[cnt]={v,w,head[u]};用普通数组的做法
// head[u]=cnt++;用普通数组的做法
// e[cnt]={u,w,head[v]};用普通数组的做法
// head[v]=cnt++;用普通数组的做法
}
bfs(head);
return 0;
}本文部分图片采集于CSDN博客链式前向星——最完美图解_rainchxy的博客-CSDN博客_链式前向星