图的存储
-
邻接矩阵
它是利用矩阵的二维结构，使其中的一维代表其中一个端点，另一维代表另一个端点。
scanf("%d",&m); memset(G,0,sizeof(G)); for(int i=1;i<=m;++i) {scanf("%d%d",&x,&y);G[x][y]=G[y][x]=1;//无向图 }
缺点：空间占用太大，空间利用率不高，容易内存爆
-
权矩阵
若边有权，则用A(i,j)存储边的权；若没有边，则默认为无穷大。
-
邻接表
对于图中的每个顶点，邻接表把与其相连的所有边依次连成一条链。并建立一个新的元素在顶点与这条链的开端建立一个联系。
在二维数组vector中，两个维度可以满足上面的需求；
链式前向星需要一个结构体，用来赋值同时规定好next指针来连接好一条链表，同时还需要一个head数组来代表那条链表的开端，即头指针。
vector：G[ u ][ v ]第一个维度表示某个顶点可以连接到的所有其他点（代表边），第二个维度枚举所有点
vector<int> G[maxn]; for (int i = 1; i <= m; i ++) {int u, v;cin >> u >> v;G[u].push_back(v);}
链式前向星
int head[maxn];//每个顶点(从i出发)的第一条边(相当于头指针,指向首元结点) struct px {int next;//指针int to;int w; }T[maxm*3];//注意T存的是所有边数(边的连接信息,终点,权值,下条边都在这里),无向图是2倍void Add(int x,int y,int z)//插在前面 {T[++cnt].next=head[x];//相当于链表前插法,新结点指向了头指针指的结点T[cnt].to=y;T[cnt].w=z;head[x]=cnt;//前插完成,头指针已经指向了新结点 }for(int i=head[x];i;i=T[i].next)//遍历(与某个点x连接的所有边和点) {cout<<x<<' '<<T[i].to<<endl;//输出这条边的两个端点(x一直是一端,存的就是所有与它连接的点)cout<<T[i].w<<endl;//输出这条边的权值 }
例题引入： 图的遍历
题意：给出 N 个点，M 条边的有向图，对于每个点 v，求 A(v) 表示从点 v 出发，能到达的编号最大的点。
- vector存图
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 20; vector<int> G[maxn]; int A[maxn]; int n, m;void dfs(int x, int d) {if (A[x]) return ;A[x] = d;for (int i = 0; i < G[x].size(); i ++) {dfs(G[x][i], d);} } int main() {cin >> n >> m;for (int i = 1; i <= m; i ++) {int u, v;cin >> u >> v;// reverse G[v].push_back(u);}for (int i = n; i >= 1; i --) {dfs(i, i);}for (int i = 1; i <= n; i ++) {cout << A[i] << " ";}return 0; }
2.链式前向星
