图论の基础

发布于:2023-01-22 ⋅ 阅读:(9) ⋅ 点赞:(0) ⋅ 评论:(0)

基本概念

  • =(顶点集,边集),即G=(V,E)
  • 结点/顶点
  • 边/弧:如果两个顶点U、V之间有一条边相连,则称U、V这两个顶点是关联的。有向图中的边又称为弧,有弧头弧尾(从弧尾指向弧头)。
  • 有向图、无向图:取决于边有没有方向
  • :图中顶点的个数
  • :点的度数是与它关联的边的数目,有奇点和偶点之分。有向图有出度和入度之分。无向图中所有顶点的度之和等于边数的2倍。有向图中所有顶点的入度之和等于所有顶点的出度之和。任意一个无向图一定有偶数个(或0个)奇点。
  • 加权图:权的含义,不加权的图也可以认为权为1。
  • 简单图:任意两个顶点最多只有一条边(多条边称为重边),且每个点都没有连接到它自身的边(无自环)的图叫简单图。
  • 完全图:也称简单完全图。如果任意两个顶点间都有边的话,该图就称为完全图。一个n阶的完全无向图含有n*(n-1)/2条边;一个n阶的完全有向图含有n*(n-1)条边。
  • 稠密图:一个图的边数接近完全图时;稀疏图:当一个图的边数远远少于完全图时。
  • 子图:从一个图中取出若干顶点、若干边构成的一个新的图;边的子集和相关联的点集。
  • 路径:路径是由顶点和相邻顶点序偶构成的边所形成的序列,是一些相连的顶点及其边
  • 路径长度:非带权图的路径长度是指路径上边的条数;带权图的路径长度是指路径上各边的权之和。
  • 简单路径:如果一条路径上的顶点除了起点和终点可以相同外,其它顶点均不相同,则称此路径为一条简单路径。
  • 回路/环:起点和终点相同的路径称为回路(环)。
  • 简单回路/简单环:起点和终点相同的简单路径称为简单回路(简单环)。
  • 连通性:在一个图中,若从顶点V到顶点U有路径,则称顶点V与U是连通的。
  • 连通图:如果一个无向图中,任意两个顶点之间是连通的,则称该无向图为连通图;否则称为非连通图。
  • 连通分量:一个无向图的连通分支定义为该图的极大连通子图。
  • 强连通图:在一个有向图中,对于任意两个顶点U和V,都存在一条从U到V和从V到U的的有向路径,则称该有向图为强连通图。
  • 强连通分量:一个有向图的强连通分支定义为该图的极大强连通子图。

还有一些图的基本概念,如极大强连通子图等,贴在这里

举几个栗子
例1:无向图
无向图例
1-5-2是一条长度为2的简单路径,1-5-2-1-4非简单路径;1-2-4-1是简单回路/简单环。
它是连通图,连通分支就是它本身。

例2:有向图
有向图例
1-4-5是一条回路。它不是强连通图。强连通分支有三个:子图1→4→5,子图2→3,子图6。

存储结构

邻接矩阵

设图G=(V,E)有n个顶点,g为一个二维数组,则当(i,j)为图中的边时有g[i][j]=1,否则g[i][j]=0。如果需要存储带权图,则把g[i][j]的保值改为对应权w(i,j)的大小。带权的邻接矩阵无法存重边。
空间复杂度为O(N^2),添加边和查询边的时间复杂度均为O(1)。

for(int i=1;i<=n;i++)
	     for(int j=1;j<=n;j++)
		   g[i][j]=0;
cin>>e; //边的数目 
for(int i,j,k=1;k<=e;k++){
	         cin>>i>>j;
  	g[i][j]=g[j][i]=1;
}

该存储结构适合于结点数较少稠密图。如果用来表示稀疏图,则会造成很大的空间浪费。
在这里插入图片描述
在这里插入图片描述

边集数组

边集数组是利用一维数组存储图中所有边的一种图的表示方法。
每个数组元素存储一条边的起点、终点和权值(如果有的话)。
在边集数组中查找一条边需要扫描整个数组,所以其时间复杂度为O(e),e为边数。

//对于n个顶点、e条边的图G,用 边集数组 描述的数据结构如下:
struct aty{
	int fromv,endv;
	int weight;	
} edgelist[e];

这种表示方法适合那些对边依次进行处理的操作,而不适合对顶点的运算和对任意一条边的运算。
边集数组空间复杂度为 O (e) 。从空间复杂度上考虑,边集数组适合于存储稀疏图。
在这里插入图片描述
在这里插入图片描述

邻接表

对图中的每个顶点vi(1≤i≤n)建立一个邻接关系的单链表。将同一个顶点出发的边链接在同一个边链表中,链表的每一个结点代表一条边,叫做边结点。
空间复杂度O(M+N),查询边的时间复杂度O(Mi),Mi为与vi相连的边的数目,添加边的时间复杂为O(1)
由于邻接表的空间复杂度比较低,通常适用于稀疏图。

const int nn=100;
struct edge{ //边节点
	int y,value;
	edge *next;
};
struct vex{
	int data;
	edge *link;
}head[nn];  //表头
int n,m,x,y,d;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) head[i]=(vex){i,NULL}; //初始化表头
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&d);
		edge* e=new edge;
		*e=(edge){y,d,head[x].link};
		head[x].link=e;
	}

在这里插入图片描述在这里插入图片描述