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://6mz.cn/article/dgpgcp.html