数据结构中的“图”是一种非常重要的非线性数据结构，它由节点（也称为顶点）和边组成。图可以用来表示实体之间的关系，如社交网络、交通网络、互联网等。下面是关于图的一些基本概念和性质：
基本概念
顶点（Vertex）：图中的节点，通常表示为V。
边（Edge）：连接两个顶点的线段，通常表示为E。
有向图（Directed Graph）：边具有方向的图，也称为有向网络。
无向图（Undirected Graph）：边没有方向的图，也称为无向网络。
权重（Weight）：与边相关联的数值，表示边的某种属性，如距离、成本等。
路径（Path）：从一个顶点到另一个顶点的一系列边。
圈（Cycle）：从一个顶点出发，经过若干边后回到该顶点的路径。
连通图（Connected Graph）：任意两个顶点之间都存在路径的图。
强连通图（Strongly Connected Graph）：有向图中任意两个顶点之间都存在双向路径的图。
图的表示方法
邻接矩阵（Adjacency Matrix）：使用二维数组表示图，其中每个元素表示对应顶点之间是否存在边。
邻接表（Adjacency List）：使用链表或数组列表表示图，其中每个顶点都有一个与之关联的链表或数组列表，存储与其相邻的顶点。
边列表（Edge List）：使用链表或数组列表表示图，其中每个元素表示一条边及其相关信息。
图的遍历算法
深度优先搜索（Depth-First Search, DFS）：从某个顶点出发，沿着一条路径尽可能深入搜索，直到无法继续为止，然后回溯并尝试其他路径。
广度优先搜索（Breadth-First Search, BFS）：从某个顶点出发，逐层访问其相邻顶点，直到所有可达顶点都被访问过。
图的应用
最短路径问题：寻找两个顶点之间的最短路径，如Dijkstra算法、Floyd-Warshall算法等。
最小生成树问题：在一个连通图中找到一棵包含所有顶点的树，使得树的所有边的权值之和最小，如Kruskal算法、Prim算法等。
拓扑排序：对有向无环图进行排序，使得对于每一条有向边(u, v)，u都在v之前。
网络流问题：研究网络中流量分配的问题，如最大流算法、最小费用最大流算法等。
洛谷 P5318
https://www.luogu.com.cn/problem/P5318
#include<bits/stdc++.h>
using namespace std;
struct edge{//存边结构体int u,v;//开始结束点 u为开始 v为结束
};
vector <int> e[100001];
vector <edge> s;
bool vis1[100001]={0},vis2[100001]={0};//标记数组
bool cmp(edge e1,edge e2){//排序规则if(e1.v==e2.v)return e1.u<e2.u;else return e1.v<e2.v;
}
void dfs(int x){//深度优先遍历vis1[x]=1;cout<<x<<" ";for(int i=0;i<e[x].size();i++){int point=s[e[x][i]].v;if(!vis1[point]){dfs(point);}}
}
void bfs(int x){ //广度优先遍历queue <int> q;q.push(x);cout<<x<<" ";vis2[x]=1;while(!q.empty()){int fro=q.front();for(int i=0;i<e[fro].size();i++){int point=s[e[fro][i]].v;if(!vis2[point]){q.push(point); cout<<point<<" ";vis2[point]=1;}}q.pop();}
}
int main(){int n,m; //输入，存边cin>>n>>m; for(int i=0;i<m;i++){int uu,vv;cin>>uu>>vv;s.push_back((edge){uu,vv}); }sort(s.begin(),s.end(),cmp); //排序for(int i=0;i<m;i++) e[s[i].u].push_back(i); dfs(1); //从1号顶点开始深搜cout<<endl;bfs(1); //广搜亦同理
}
洛谷 P1113
https://www.luogu.com.cn/problem/P1113
#include<bits/stdc++.h>
#define MAXN 10010
using namespace std;int n,x,y,t,ans,len[MAXN],vis[MAXN];
vector<int> linker[MAXN];int dfs(int x){if(vis[x]) return vis[x];for(int i=0;i<linker[x].size();i++){vis[x]=max(vis[x],dfs(linker[x][i]));}vis[x] += len[x];return vis[x];
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>x>>len[i];while(cin>>y){if(!y){break;}else{linker[y].push_back(x);}}}for(int i=1;i<=n;i++){ans = max(ans,dfs(i));}cout<<ans<<endl;return 0;
}
洛谷 P4017
https://www.luogu.com.cn/problem/P4017
#include<bits/stdc++.h>
using namespace std;#define MAXN 5005
#define MAXM 500005
#define MOD 80112002
int n,m,ans;
vector <int> p[MAXN];
queue <int> q;
int f[MAXN],ind[MAXN],outd[MAXN];
int main(){cin>>n>>m;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;outd[x]++;ind[y]++;p[x].push_back(y);} memset(f,0,sizeof(f));for(int i=1;i<=n;i++){if(ind[i]==0){q.push(i);f[i]=1;}}while(!q.empty()){int x = q.front();q.pop();for(int i=0,sz=p[x].size();i<sz;i++){int y=p[x][i];f[y]=(f[x]+f[y])%MOD;ind[y]--;if(ind[y]==0){q.push(y);}}}for(int i=1;i<=n;i++){if(outd[i]==0){ans=(ans+f[i])%MOD;}}cout<<ans<<endl;
}