成都创新互联网站制作重庆分公司

Week5存图-创新互联

一、图的概念 1、基本概念

图 (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#includeusing 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#includeusing namespace std;
vectorg[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
#includeusing 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元起,快前往官网查看详情吧


当前名称:Week5存图-创新互联
分享地址:http://cxhlcq.com/article/dgpgcp.html

其他资讯

在线咨询

微信咨询

电话咨询

028-86922220(工作日)

18980820575(7×24)

提交需求

返回顶部