图的存储方法有两种，首先就是邻接矩阵
那，什么是邻接矩阵呢，邻接矩阵就是用一个二维数组存储两个结点的邻接关系的一个矩阵
光说可能有的人不懂，我们在图上解释吧
如图，结点之间没有边的地方全部设为无穷大，1，2表示1到2有一个边，权值就是a[1][2]，无向图的话，a[1][2]存一个权值，a[2][1]要存相同的权值；
这就是邻接矩阵，把所有结点之间边的情况存在一个二维数组里，这个二维数组的大小应该是a[N][N] N表示结点个数
也就是空间复杂度为n²，n为结点个数，跟边数无关，适合存储边数多的图，也就是稠密图
#include <iostream>
using namespace std;
const int N = 1010;
int n,m;
int edges[N][N];
int main()
{int n,m;cin >> n >> m;//结点个数和边的个数 //刚开始的时候设置每个结点之间都没有边，嗯。。就设成负无穷好了memset(edges,-0x3f,sizeof edges);for(int i = 1;i<=m;i++){int a,b,c;cin >> a >> b >> c;//ab表示两个结点edges[a][b] = c;edges[b][a] = c;//如果是无向边，相反的情况也要存一下 } return 0;
}另一种存储方式就是邻接表了，这种存储方式就是开一个vector数组，然后每个结点都把他有边的结点存起来，但是，光存结点肯定是不行的，这时候我们可以用一个pair类型来存另一个结点以及边的权值
这个就很像我们之前学树的时候的孩子表示法
#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;
int n,m;
typedef pair<int,int> PII;
vector <PII> edges[N];
int main()
{int n,m;cin >> n >> m;//结点个数和边的个数 for(int i = 1;i<=m;i++){int a,b,c;cin >> a >> b >> c;//ab表示两个结点edges[a].push_back({b,c});edges[b].push_back({a,c});} return 0;
}当然啦，我们的邻接表除了这种形式存之外，还有别的存储方式，我们还可以用链式前向星来存储
#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;
int n,m;
int h[N],e[2*N],ne[2*N],w[N*2],id;
void add(int a,int b,int c) //把b结点头插到a结点后面的链表里
{id++;e[id] = b;ne[id] = h[a];h[a]=id;w[id] = c;}
int main()
{int n,m;cin >> n >> m;//结点个数和边的个数 for(int i = 1;i<=m;i++){int a,b,c;cin >> a >> b >> c;//ab表示两个结点add(a,b,c);//把b头插到a的结点里面 add(b,a,c);//把a头插到b的结点里面 } return 0;
}好的，这就是我们的几种存储方法，接下来我们还得继续介绍一下图是怎么遍历的
老样子，我们还是分为dfs和bfs遍历
我们先说一下dfs
一路走到黑我们先看邻接矩阵怎么遍历
#include <iostream>
using namespace std;const int N = 5001;
bool st[N];
int edges[N][N];
void dfs(int u)
{cout << u << " ";st[u] = true;for(int v = 1;v<=n;v++){if(edges[u][v]!=-1 && !st[v]){dfs(v);}}
}
int main()
{int n,m; cin >> n >> m;memset(edges,-1,sizeof(edges));for(int i = 1;i<=m;i++){int a,b,c;cin >> a >> b >> c;edges[a][b] = c;edges[b][a] = c;}return 0;
}接下来看看邻接表怎么遍历
#include <iostream>
#include <vector>
using namespace std;const int N = 5001;
typedef pair<int,int> PII;
bool st[N];
vector <PII> ret[N];
void dfs(int u)
{cout << u << " ";st[u] = true;for(auto &e : ret[u]){int x = e.first,y = e.second;//x就是连接u的一条边，y就是权值if(!st[x]){dfs(x);} }
}
int main()
{int n,m; cin >> n >> m;for(int i = 1;i<=m;i++){int a,b,c;cin >> a >> b >> c;ret[a].push_back({b,c});ret[b].push_back({a,c});}return 0;
}链式前向星的dfs
#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;
int n,m;
bool st[N];
int h[N],e[2*N],ne[2*N],w[N*2],id;
void add(int a,int b,int c) //把b结点头插到a结点后面的链表里
{id++;e[id] = b;ne[id] = h[a];h[a]=id;w[id] = c;} void dfs(int u){cout << u << " ";st[u] = true;for(int v = h[u];v;v=ne[v]){int x = e[v];if(!st[x]){dfs(x);}}}
int main()
{int n,m;cin >> n >> m;//结点个数和边的个数 for(int i = 1;i<=m;i++){int a,b,c;cin >> a >> b >> c;//ab表示两个结点add(a,b,c);//把b头插到a的结点里面 add(b,a,c);//把a头插到b的结点里面 } return 0;
}
