1：图的构成：顶点和边（分有向无向）
2：图的基本定理： a)：欧拉定理（一笔画定理）
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（基本不用，此处略）
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
