图 (Graph) 是一个二元组 G =( V(G), E(G) ) 。其中V(G)是非空集,称为 点集 (Vertex set) ,对于 V 中的每个元素,我们称其为 顶点 (Vertex) 或 节点 (Node) ,简称 点 ;E(G) 为 V(G) 各结点之间边的集合,称为 边集 (Edge set) 。图的节点数也被称作图的阶。
只为您设计更接底气、较有营销力的好网站,将营销策划与网页设计互相结合的专业机构,营销型网站公司中较早掌握HTML5技术的机构。一个好的品牌网站制作,不能只是一张名片,茫茫网海,想要快速吸引到您客户的眼球,必须全方位的展现出企业突出的优势,以求达到主动营销的效果,最终促成成交!常用 G=(V,E) 表示图。
有限图:V, E 都是有限集合
无限图:V 或 E 是无限集合
无向图:边的两点u,v 是无序二元组。即 u 可以到 v,v 也可以到 u;
边称为无向边;u,v 称为边 e 的端点。
有向图:边的两点u,v 是有序二元组。即 u 可以到 v,v 却不能到 u;
边称为有向边;u 称为边的起点,v称为边的终点,共称端点。
并称 u 是 v 的直接前驱,v 是 u 的直接后驱。
混合图:既有无向边,又有有向边。
赋权图:边带有权值。如果权都为正实数,则程图为正权图。
形象地说,图是由若干点以及连接点与点的边构成的。
二、图的三类储存及遍历方式 1、数组存图另有 概念:点与点邻接(邻域)
点与边关联
顶点的度(入度,出度)
自环,重边
路径,迹,回路,环
连通性(强联通与弱联通)
及图种类:简单图,多重图,稀疏图,稠密图
特殊的图:完全图,链,树
当图中两点相连时,用二维数组 a [ i ] [ j ] 表示 i 连向 j 点。无向图 a [ i ] [ j ]、 a [ j ] [ i ]各存一次即可。数组存图空间占用较多。
m条边的存图:
for(int i=1;i<=m;++i)
{
int x,y,val;
scanf("%d%d%d",&x,&y,&val);// x与 y相连,边权值为val
a[x][y]=val;//有向图存一次即可
a[y][x]=val;
}
遍历和每个点相连的所有边:
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
if(a[i][j])
printf("%d->%d:%d\n",i,j,a[i][j]);
// i 连 j ,且权值为 a[i][j]
}
2.vector 存图数组存图有大量空间冗余,vector 可减少空间的浪费。
m条边的存图:
vectorg[100],w[100];//g存点 w存边权值
for(int i=1;i<=m;++i)
{
int x,y,val;
scanf("%d%d%d",&x,&y,&val);// x连 y 边权为val
g[x].push_back(y);w[x].push_back(val);
g[y].push_back(x);w[y].push_back(val);
//有向图,存一条即可
}
遍历和每个点相连的所有边:
for(int i=1;i<=n;++i)
{
for(int j=0;j%d:%d\n",i,g[i][j],w[i][j]);
// i连 g[i][j],且边权为 w[i][j]
}
3、链式前向星对边建立编号,按编号索引。
方式:
对于一个点,当一条边与这个点相连时,标记此边的编号,之后与此点相连的边与该边共同以链表形式存储。由此,我们可快速找到与某一点相连的边,进一步推出由此延伸出的点。
具体的:
用结构体存边,其包含:连接同一个点的下一条边编号next,指向的另一个点to,边权值val。
用 h [ u ] 表示与点 u 相连的第一条边的编号。
存边:
struct node
{
int next,to,val;
}edg[10010];// 存边
int cnt;//边的编号
int h[10010];//h[u]:指向和 u点相连的第一条边编号
void add(int u,int v,int val)
{
++cnt;//对该边进行编号
edg[cnt].next=h[u];//新边的下一条边是上一个"第一条边"
edg[cnt].to=v;//该边相连的另一个点
edg[cnt].val=val;
h[u]=cnt;//新边成为"第一条边"
}
int main()
{
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&x,&y,&val);
add(x,y,val);
add(y,x,val);//有向边读一次
}
}
遍历和每个点相连的所有边:
for(int i=1;i<=n;++i)
{
if(h[i])//h[i]=0,说明该点没有任何边相连
{
for(int j=h[i];j;j=edg[i].next)
{
int v=edg[j].to,val=edg[j].val;
}
}
}
三、例题再次注意:edg存的是边本身,h [ u ] 存的是与 u 点相连的第一条边的编号,edg[ ].next存的是下一条边的编号,edg[ ].to存的是此边连接的另一个点。
边的链表是不断在链表前方而不是后方插入,注意首边 h[ ]的更新。
1.P8604 [蓝桥杯 2013 国 C] 危险系数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
此题范围较小,在此用矩阵存图
解析:由题意得,关键点即为从 u 到 v 必须经过的点。
将图存在数组中,用 dfs 找出从 u 到 v 的路径,对经过的点进行标记。当找出所有路径后,关键点每次都会被标记,被标记次数等于 u,v 两点被标记的次数,统计有多少个这样的点即可。
代码:
#include
#include using namespace std; const int N=1005; int a[N][N];//矩阵存图 int vis[N]; int cnt[N];//用于统计每个点被标记的次数 int ans; int st,ed; int n,m; int tot;//统计有多少种路径 void dfs(int k) { if(k==ed)//已经找到终点 { ++tot;//路径数+1 for(int i=1;i<=n;++i) if(vis[i]) ++cnt[i];//经过的点 return; } for(int i=1;i<=n;++i)//查找与 i相连的点 { if(a[k][i]==1&&vis[i]==0) { vis[i]=1;dfs(i);vis[i]=0; } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) { int x,y; scanf("%d%d",&x,&y); a[x][y]=1; a[y][x]=1; }//矩阵存图 scanf("%d%d",&st,&ed); vis[st]=1; dfs(st); for(int i=1;i<=n;++i) { if(tot==cnt[i]) ++ans; } printf("%d",ans-2); return 0; }
2.P3916 图的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
采用vector存图
解析:此题难点在于如何找出能到达的编号大的点。
如果按常规方法一一遍历,那要进行n次搜索,时间复杂度高。
我们注意到当此点是编号大的点时,在该点前的所有点(即能到达该点的点)能到达的大编号就是这个点,这样之前的点便不用再次遍历,可以直接求得结果。
所以当存储这个有向图时,我们倒着存储,把a[ u ][ v ] 的含义由 u 指向 v 变为 u 的上一个电是 v 。
代码:
#include
#include #include #include using namespace std; vector g[100010];// vector存图 int n,m; bool vis[100010]; int ans[100010]; void dfs(int a,int big) { if(ans[a]) return;//a可以到达更大的点,已被记录 ans[a]=big; vis[a]=1; for(int i=0;i =1;--i)//倒序遍历 { if(ans[i]==0) dfs(i,i);//dfs(当前点,大点) //当该点没有被记录时,表明此点不能通向更大的点了,则以此点为大点遍历 } for(int i=1;i<=n;++i) printf("%d ",ans[i]); return 0; }
3.P1330 封锁阳光大学 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
采用链式前向星存图。
解析:
对于一个点,只有有河蟹和没有河蟹两种情况。
对于一条边,要想被封锁,两个端点必须有一个是河蟹,且根据题意,两边不能都是河蟹,即两端点的状态不同。
目标是封锁所有边,那就设所有边已被封锁,由于点有两种状态,我们可以将所有点分为状态1和状态2,有河蟹但不确定哪一点是河蟹,只需满足一边的两点状态不同即可。
具体的,对于未确定状态的点,先确定一个状态,再将它连接的其他所有点确定为另一个状态;对于确定状态的点,直接将连接的点确认为另一状态,若在此过程中,另一点状态已被确定且与此点相同,那么构建失败,输出Impossible。此过程用dfs完成,一次dfs可以将相连的所有未确定状态的点确定。确定状态时统计每个状态的个数,河蟹取较小的那个。
代码:
#include
#include #include #include #include using namespace std; struct node { int nex,to; }edg[200010]; int vis[10010];//存点状态 int cnt; int h[10010]; int n,m; int ans; int cnt1,cnt2;//用于统计每次dfs两种状态的点的个数 int f; void add(int u,int v) { ++cnt; edg[cnt].nex=h[u]; edg[cnt].to=v; h[u]=cnt; }//链式前向星存图 void dfs(int u) { for(int i=h[u];i;i=edg[i].nex) { int v=edg[i].to;//与 u相连的点 if(vis[v]==vis[u]) {f=1;return;}//已确定且状态相同 if(vis[v]!=0) continue; if(vis[u]==1)//状态翻转 { ++cnt2;vis[v]=2;dfs(v); } if(vis[u]==2) { ++cnt1;vis[v]=1;dfs(v); } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) { int x,y; scanf("%d%d",&x,&y); add(x,y);add(y,x); } for(int i=1;i<=n;++i) { if(vis[i]==0) { ++cnt1;vis[i]=1; dfs(i); if(f==1) { printf("Impossible"); return 0; } ans+=min(cnt1,cnt2); cnt1=cnt2=0;//清空 } } printf("%d",ans); return 0; }
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧