数据结构七(图)

1.图的定义

图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其实,G表示一个图,V是图G中顶点的集合,E的图G中边的集合
线性表中我们把数据元素叫元素,树中将数据元素叫结点,在图中数据元素,我们则称为顶点

图1

2.各种图的定义

无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边,用无序偶对(Vi,Vj)来表示.如果图中所有的边都是无向边,则称该图为无向图,图1就是典型的无向图
有向边:若顶点Vi到Vj之间的边有方向,则称这条边为有向边,也称为弧.用有序偶对<Vi,Vj>来表示,如果图中所有的边都是有向边,则称该图为有向图**

有向图

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

无向完全图
在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图.含有n个顶点的有向完全图有n(n-1)*条边 有向完全图
与图的边或弧相关的数叫做权.这些权可以表示从一个顶点到另一个顶点的距离或耗费.这种带权的图通常称为网 权

假设有两个图G=(V,{E})和G2=(V2,{E2}),如果V2属于V,且E2属于E,我们称G2为G的子图

子图