图论1——基础
1：图的构成：顶点和边（分有向无向）
2：图的基本定理： a)：欧拉定理（一笔画定理）
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。b): 握手引理：各顶点度的和等于边的数量和的两倍
推论1：各顶点的度和和一定为偶数
推论2：奇数度顶点一定有偶数个
3：正则图：每个顶点的度均为k则称为k正则图
4：图的存储：
a):邻接矩阵
#include<iostream>#include<cstring> int a[5001][5001]; int main() { int n,m,i,u,v,w; cin>>n>>m; for (i=1;i<=m;i++) { cin>u>>v>>w; a[u][v]=w; a[v][u]=w; //若非简单图则要判断是否更新 } return 0; }
b): 邻接表
for (i=0;i<=n;i++) { end[i]=0; } for (i=1;i<=m;i++) { scanf("%lld%lld",&u,&v); if (end[u]==0) { end[u]=i*2-1; edge[i*2-1]=v; next[i*2-1]=0; } else { next[i*2-1]=end[u]; edge[i*2-1]=v; end[u]=i*2-1; } if (end[v]==0) { end[v]=i*2; edge[i*2]=u; next[i*2]=0; } else { next[i*2]=end[v]; edge[i*2]=u; end[v]=i*2; } }5：图的搜索——dfs/bfs（基本不用，此处略）
更多精彩
