图的基本概念及特性:

  • 在图形结构中,结点之间的关系可以是任意的,图中任意个数据元素之间都可能相关。
  • 任何复杂的图都是由顶点和边(弧)构成的。
  • 采用形式化的定义,图G(Graph)由两个集合V(Vertex)和E(Edge)组成,记为G=(V,E),其中V是顶点的有限集合,记为V(G),E是连接V中两个不同顶点的边(弧)的有限集合,记为E(G)。
  • 对于含有n个顶点的图,通常用字母或自然数来唯一标识图中顶点(顶点的编号)。顶点可以使用字符vi表示,也可用数字i(0≤i≤n-1)表示第i个顶点vi的编号。

无向图:对于一个图G,若边集E(G)为无向边的集合,则称该图为无向图。

邻接点:在一个无向图中,若存在一条边(i,j),则称顶点i、j为该边的两个端点,并称它们互为邻接点(或者相邻点)。端点和邻接点是相对一条边的。

无向图

有向图:对于一个图G,若边集E(G)为有向边的集合,则称该图为有向图。

顶点:在一个有向图中,若存在一条边(弧),则称此边(弧)是顶点(弧尾)i的一条出边,同时也是顶点(弧头)j的一条入边,称顶点i和j分别为此边的起始顶点(简称为起点)和终止顶点(简称终点)。

有向图

度、入度和出度:

  • 对于无向图,每个顶点v的度定义为和v顶点相关联的边的数目。
  • 对于有向图,顶点v的度分为入度和出度,入度是以该顶点为弧头(终点)的入边数目;出度是以该顶点为弧尾(起点)的出边数目,该顶点的度等于其入度和出度之和。
  • 一个图中所有顶点的度之和等于边数的两倍。因为图中每条边分别作为两个相邻点的度各计一次。

子图:设有两个图G=(V,E)和G’=(V’,E’),若V’是V的子集,即V’ ∈ V,且E’
是E的子集,即E’ ∈ E,则称G’是G的子图。由V的子集和E的子集并非一定构成G的子图。

完全无向图:对于无向图,若具有n(n-1)/2条边,则称之为完全无向图。

完全有向图:对于有向图,若具有n(n-1)条边,则称之为完全有向图。

稀疏图和稠密图:边数较少(边数e<<nlog2n,其中n为顶点数)的图称为稀疏图。边数较多的图称为稠密图。

路径和路径长度:

  • 在一个图G中,从顶点i到顶点j的一条路径是一个顶点序列i=i0、i1、…、im=j。若是无向图,则(ik-1,ik)∈E(G),(1≤k≤m);若该图是有向图,则∈E(G),(1≤k≤m),其中顶点i称为该路径的开始点,顶点j称为该路径的结束点。
  • 路径长度是指一条路径上经过的边(弧)的数目。

简单路径:若一条路径的顶点序列中顶点不重复出现,称该路径为简单路径。

回路(环):若一条路径上的开始点和结束点为同一个顶点,则称该路径为回
路(环)。除开始点与结束点相同外,其余顶点不重复出现的回路称为简单回路(简单环)。

连通、连通图和连通分量:在无向图G中,若从顶点i到顶点j有路径,则称顶点i和j是连通的。若图G中任意两个顶点都是连通的,则称G为连通图,否则为非连通图。无向图G中极大连通子图称为G的连通分量。

强连通图和强连通分量:在有向图G中,若任意两个顶点i和j都是连通的,即从顶点i到j和从顶点j到i都存在路径,则称该图是强连通图。有向图G中极大强连通子图称为G的强连通分量。

权和网:在一个图中,每条边可以标上具有某种含义的数值,该数值称为该边的权。边上带权的图称为带权图,也称为网。一般规定所有边的权均为非负数。

图的存储结构

邻接矩阵存储:邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图,顶点编号依次为0、1、…、n-1,则G的邻接矩阵是具有如下定义的n阶方阵。

若G是不带权的图:

若G是带权图或网:

特性:

  • 对于n个顶点e条边的图采用邻接矩阵存储时占用存储空间为O(n2),与边数e无关(不考虑压缩存储),特别适合存储稠密图。
  • 任何图的邻接矩阵表示是唯一的。
  • 图采用邻接矩阵存储时判断两个顶点i、j之间是否有边十分容易。

邻接表:在邻接表中,对图中每个顶点建立一个单链表,把该顶点的所有相邻点串起来。所有的头指针构成一个数组,称为表头结点数组,用adjlist表示,第i个单链表adjlist[i]中的结点表示依附于顶点i的边,也就是说头指针数组元素的下标与顶点编号一致。

单链表中的每个结点由3个域组成:

  • 顶点域adjvex(用以指示该相邻点在头结点数组中的下标)
  • 权值域weight(存放对应边的权值)对于不带权的图,weight域可以不设置;对于带权图,weight域置为相应边的权值。
  • 指针域nextarc(用以指向依附于顶点i的下一条边所对应的结点)

有向图的逆邻接表:为了便于确定顶点的入度或以顶点vi为头的弧。

十字链表表示法:将有向图的正邻接表和逆邻接表结合起来得到的一种链表。每条弧的弧头结点和弧尾结点都存放在链表中,并将弧结点分别组织到以弧尾结点为头(顶点)结点和以弧头结点为头(顶点)结点的链表中。

邻接多重表表示法:无向图的另一种链式存储结构。邻接多重表的结构和十字链表类似,每条边用一个结点表示;邻接多重表中的顶点结点结构与邻接表中的完全相同,而表结点包括六个域。

图的遍历

深度优先遍历(DFS):

  1. 访问顶点v;
  2. 选择一个与顶点v相邻且没被访问过的顶点w,从w出发深度优先遍历。
  3. 直到图中与v相邻的所有顶点都被访问过为止。

代码实现:

visited[MAXVEX]={0}; //全局变量
void DFS(AdjGraph *G,int v)
{
	int w;
	ArcNode *p;
	printf("%d ",v); //访问v顶点
	visited[v]=1;
	p=G->adjlist[v].firstarc; //找v的第一个邻接点
	while (p!=NULL) //找v的所有邻接点
	{ 
		w= p->adjvex; //顶点v的邻接点w
		if (visited[w]==0) //顶点w未访问过
		DFS(G,w); //从w出发深度优先遍历
		p=p->nextarc; //找v的下一个邻接点
	}
}

广度优先遍历(BFS):

  • 访问顶点v;
  • 访问顶点v的所有未被访问过的邻接点,假设访问次序是vi1,vi2,…,vit 。
  • 按vi1,vi2,…,vit 的次序,访问每个顶点的所有未被访问过的邻接点,直到图中所有和初始点v有路径相通的顶点都被访问过为止。
  • (用队列实现)

代码实现:

void BFS(ALGraph *G,int vi)
{
	int i,v,visited[MAXVEX]; ArcNode *p;
	int Q[MAXVEX],front=0,rear=0; //定义一个循环队列Q
	for (i=0;i<G->n;i++) visited[i]=0; //visited数组置初值0
	printf("%d ",vi); //访问初始顶点
	visited[vi]=1;
	rear=(rear+1)%MAXVEX;Q[rear]=vi; //初始顶点进队
	while (front!=rear) //队不为空时循环
	{ 
		front=(front+1) % MAXVEX;
		v=Q[front]; //出队顶点v
		p=G->adjlist[v].firstarc; //查找v的第一个邻接点
		while (p!=NULL) //查找v的所有邻接点
		{ 
			if (visited[p->adjvex]==0) //未访问过则访问之
			{ 
				printf("%d ",p->adjvex); //访问该点并进队
				visited[p->adjvex]=1;
				rear=(rear+1) % MAXVEX;
				Q[rear]=p->adjvex;
			}
		p=p->nextarc; //查找v的下一个邻接点
		}
	}
}

用途:深度优先遍历适合目标比较明确,以找到目标为主要情况。广度优先遍历更适合在不断扩大范围时找到最优解。

生成树:若边集E(G’)中的边既将图G中的所有顶点连通又不形成回路,则称子图G’是原图G的一棵生成树。

  • 通过深度优先遍历产生的生成树称为深度优先生成树。
  • 通过广度优先遍历产生的生成树称为广度优先生成树。

生成森林:非连通图每个连通分量的生成树一起组成非连通图的生成森林。

连通图:仅需要从图中任一顶点出发,进行深度优先遍历或广度优先遍历便可以访问到图中所有顶点,因此连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树。

非连通图:它由多个连通分量构成的,则需要从每个连通分量的任一顶点出发进行遍历,每次从一个新起点出发进行遍历过程得到的顶点访问序列恰为各个连通分量中的顶点集。每个连通分量产生的生成树合起来构成整个非连通图的生成森林。

最小生成树:由一个带权无向图可能产生多棵生成树, 把具有权之和最小的生成树称为图的最小生成树。构造一个图的最小生成树主要有两个算法,即普里姆算法和克鲁斯卡尔算法。

普里姆(Prim)算法:

  1. 若从顶点v0出发构造,U={v0},TE={};
  2. 先找权值最小的边(u,v),其中u∈U且v∈V-U,并且子图不构成环,则U= U∪{v},TE=TE∪{(u,v)} ;
  3. 重复⑵ ,直到U=V为止。则TE中必有n-1条边,T=(U,TE)就是最小生成树。

克鲁斯卡尔(Kruskal)算法:是一种按权值的递增次序选择合适的边来构造最小生成树的方法。初值:U=V,TE={} 。对G中的边按权值大小从小到大依次选取。

  • 选取权值最小的边(vi,vj),若边(vi,vj)加入到TE后形成回路,则舍弃该边(边(vi,vj) ;否则,将该边并入到TE中,即TE=TE∪{(vi,vj)} 。
  • 重复⑴ ,直到TE中包含有n-1条边为止。

普里姆算法和克鲁斯卡尔算法的比较:

算法普里姆算法克鲁斯卡尔算法
时间复杂度O(n2)O(e loge)
特点只与顶点个数 n 有关与边的数目 e无关适用于稠密图只与边的数目 e 有关与顶点个数 n无关适用于稀疏图

有向无环图:无环的有向图称为有向无环图, 简称DAG图(DirectedAcyclic Graph),它可以表示一个工程或系统的流程图。

AOV网:假设以有向图表示一个工程的施工图或程序的数据流图, 每个顶点代表一个活动, 弧表示活动i 必须先于活动j 进行, 称为AOV-网(Activity On Vertex), 图中不允许出现回路。

拓扑排序:由某个集合上的 一个偏序得到该集合上的一个全序,把 AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫拓扑排序,检查有向图中是否存在回路的方法之一,是对有向图进行拓扑排序。

拓扑排序步骤:

  • 从AOV网中选择一个没有前驱(即入度为0)的顶点并且输出它。
  • 从AOV网中删去该顶点,并且删去从该顶点发出的全部有向边。
  • 重复上述两步,直到剩余的网中不再存在没有前驱的顶点为止。

对任一有向图进行拓扑排序有两种结果:

  • 图中全部顶点都包含在拓扑序列中,这说明该图中不存在有向回路;
  • 图中部分顶点未被包含在拓扑序列中,这说明该图中存在有向回路。
  • 所以可以采用拓扑排序判断一个有向图中是否存在回路。

代码实现:

typedef struct //表头结点类型
{ 
	Vertex data; //顶点信息
	int count; //存放顶点入度
	ArcNode *firstarc; //指向第一条边
} VNode;
void TopSort(ALGraph *G) //拓扑排序算法
{
	int i,j;
	int S[MAXV],top=-1; //栈S的指针为top
	ArcNode *p;
	for (i=0;i<G->n;i++) //入度置初值0
	G->adjlist[i].count=0;
	for (i=0;i<G->n;i++) //求所有顶点的入度
	{ 
		p=G->adjlist[i].firstarc;
		while (p!=NULL)
		{ 
			G->adjlist[p->adjvex].count++;
			p=p->nextarc;
		}
	}
	for (i=0;i<G->n;i++) //将入度为0的顶点进栈
		if (G->adjlist[i].count==0)
			S[++top]=i;
	while (top>-1) //栈不空循环
	{
		i=S[top--]; //出栈一个顶点i
		printf("%d ", i); //输出该顶点
		p=G->adjlist[i].firstarc; //找第一个邻接点
		while (p!=NULL) //将顶点i的出边邻接点的入度减1
		{ 
			j=p->adjvex;
			G->adjlist[j].count--;
			if (G->adjlist[j].count==0) //将入度为0的邻接点进栈
				S[++top]=j;
			p=p->nextarc; //找下一个邻接点
		}
	}
}

AOE网:用带权有向图(DAG)描述工程的预计进度,以顶点表示事件,有向边表示活动,边弧上的权值w(ai)表示完成活动ai所需的时间(比如天数),或者说活动ai持续时间。图中入度为0的顶点表示工程的开始事件(如开工仪式),称为源点;出度为0的顶点表示工程结束事件,称为汇点。则称这样的有向图为AOE网(Activity OnEdge)。

关键路径:整个工程完成的时间为:从有向图的源点到汇点的最长路径,具有最大长度的路径叫关键路径。(在一个AOE网中,可以有不止一条的关键路径。)

事件v的最早开始时间:规定源点事件的最早开始时间为0。定义图中任一事件v的最早开始时间(early)ve(v)等于x、y、z到v所有路径长度的最大值,即:它是从源点v0到顶点v的最长路径长度。当v为源点时,ve(v)=0。否则,ve(v)=MAX{ve(x)+a,ve(y)+b,ve(z)+c}。

事件v的最迟开始时间:定义在保证汇点vn-1在ve(n-1)时刻完成的前提下,事件v的允许的最迟开始时间,记作vl(v)。vl(v)的求解应从vl(n-1)=ve(n-1)开始,反向递推。当v为汇点时,vl(v)=ve(v)。否则,vl(v)=MIN{vl(x)-a,vl(y)-b,vl(z)-c}。

活动ai的最早开始时间e(i):指该活动起点x事件的最早开
始时间,即:e(i)=ve(x)。

活动ai的最迟开始时间l(i):指该活动终点y事件的最迟开始时间与该活动所需时间之差,即:l(i)=vl(y) – dut<x,y>。

关键活动:对于每个活动ai,求出:d(i)=l(i)-e(i)。若d(i)为0,则称活动ai为关键活动。

最短路径:从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径是沿此路径上各边上的权值总和最小的。

  • 求从一个顶点到其他各顶点的最短路径,称之为单源最短路径问题;
  • 求每对顶点之间的最短路径,称之为多源最短路径问题。

迪杰斯特拉(Dijkstra)算法:(单源最短路径算法)

  1. 初始时,顶点集S只包含源点v,即S={v},顶点v到自已的距离为0。顶点集U=V-S包含除v外的其他顶点,源点v到U中顶点i的距离为边(弧)上的权(若v与i有边)或∞(若顶点i不是v的出边相邻点)。
  2. 从U中选取一个顶点u,它是源点v到U中距离最小的一个顶点,然后把顶点u加入S中(该选定的距离就是源点v到顶点u的最短路径长度)。
  3. 以顶点u为新考虑的中间点,修改源点v到U中各顶点j(j∈U)的距离。
  4. 重复步骤2和3直到S包含所有的顶点,即U为空。

弗洛伊德(Floyd)算法:(多源最短路径算法)

  • 初始时设置一个n 阶方阵,令其对角线元素为0,若存在弧<vi,vj>,则对应元素为权值;否则为∝,逐步试着在原直接路径中增加中间顶点,若加入中间点后路径变短,则修改之;否则,维持原值,所有顶点试探完毕,算法结束。
  • D-1[i][j]=g.edges[i][j]
  • Dk[i][j]=MIN{Dk-1[i][j], Dk-1[i][k]+Dk-1[k][j]} 0≤k≤n-1
最后修改日期:2020年3月20日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据