189 8069 5689
图 (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]
}数组存图有大量空间冗余，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]
} 对边建立编号，按编号索引。
方式：
对于一个点，当一条边与这个点相连时，标记此边的编号，之后与此点相连的边与该边共同以链表形式存储。由此，我们可快速找到与某一点相连的边，进一步推出由此延伸出的点。
具体的：
用结构体存边，其包含：连接同一个点的下一条边编号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)