数据结构-图-概念

数据结构-图-概念

图的概念

图的定义和术语

图的定义

图是由顶点的有穷非空集合和顶点之间的边的集合组成的,通常表示为G=(V,E),其中,G表示一个图,V表示G中顶点的集合,E表示G中边的集合

无向边

若顶点Vi 到Vj 的边没有方向,则称这条边为无向边,用无序偶对

(Vi ,Vj)来表示

有向边

若从顶点Vi 到Vj的边有方向,则称这条边为有向边,也称为弧(Arc)。用有序偶对<Vi ,Vj>来表示。Vi称为弧尾(Tail)或初始点,Vj称为弧头(Head)或终端点。

(v1,v2)和(v2,v1)是两个不同的有向边

无向图

如果图中任意两个顶点之间的边都是无向边,则称该图为无向图。

数据结构-图-概念

 

 

有向图

如果图中任意顶点之间的边都是有向边,则称该图为有向图

数据结构-图-概念

 

 

无向完全图

在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边。

数据结构-图-概念

 

 

有向完全图

在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。含有n个顶点的有向完全图有n(n-1)条边。

数据结构-图-概念

 

 

图的顶点数n和边数e的关系

1 如果是无向图

0<=e<=n*(n-1)/2

刚好为n*(n-1)/2为无向完全图

2 如果是有向图

0<=e<=n*(n-1)

刚好为n*(n-1)就是完全有向图

连通图

在无向图G=(V,E)中,如果从顶点v到顶点w有路径,则称v和w是相通的。如果对图中任意两个顶点Vi和Vj 属于E,则两个顶点是连通的,则称G是连通图。

连通图生成树

连通图的生成树是一个极小的连通子图,它含有图中全部的n个顶点,但只有足以构成一棵树的n-1条边。

 

术语

稀疏图: 有很少条边或弧的图。

稠密图: 有很多条边或弧的图。

: 有时图的边或弧具有与它相关的数,这种与图的边或弧相关的数叫做权。

:带权的图通常称为网。

:顶点的度是指和该顶点关联的边的数目。

入度:有向图中以顶点(v)为头的弧的数目,称为(v)的入度。

出度:有向图中以顶点(v)为尾的弧的数目,称为(v)的出度。

邻接点:对于无向图,同一边上的两个顶点称为邻接点。

子图: 假设两个图G=(V,E)和G1=(V1,E1),如果V1⊆V且E1⊆E则G1为G的子图

路径的长度: 路径上的边或弧的数目。

 

上一篇:如何理解迪杰斯特拉算法


下一篇:20210114 - VJ 题解