A5856bd0dd687e2a8f887dfe9ba84d3c
数据结构与算法——图论基础

1 引言

  是数据结构中重要内容。相比于线性表与树,图的结构更为复杂。在线性表的存储结构中,数据直接按照前驱后继的线性组织形式排列。在树的结构中,数据节点以层的方式排列,节点与节点之间是一种层次关系。但是,在图的结构中数据之间可以有任意关系,这就使得图的数据结构相对复杂。

2 图

2.1 定义

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

例如:图2.1所示图
图2.1

图2.1

图2.1中,共有V0,V1,V2,V3 4个顶点,4个顶点之间共有5条边。
注:

当线性表没有数据节点时,线性表为空表。
树中没有节点时,树为空树。
但是,在图中不允许没有顶点,但是可以没有边。

2.2 无向边

  无向边:若顶点 x 和 y 之间的边没有方向,则称该边为无向边(x,y),(x,y) 与 (y,x) 意义相同,表示x和y之间有连接。
  图2.2所示图中的边均为无向边。
图2.2

图2.2

2.3 有向边

  有向边:若顶点 x 和 y 之间的边有方向,则称该边为有向边<x, y>,<x,y> 与 <y,x> 表示的意义是不同的,<x, y>表示从x连接到y,x称为尾,y称为头。<y,x>表示从y连接到x,y称为尾,x称为头。
  图2.3所示图中的边为有向边。
图2.3

图2.3

2.4 无向图

  无向图:若图中任意两个顶点之间的边均是无向边,则称该图为无向图。
图2.2所示图为无向图。

2.5 有向图

  有向图:若图中任意两个顶点之间的边均是有向边,则称该图为有向图。
图2.3所示的图为有向图。

2.6 顶点与顶点的度

图2.6

图2.6

顶点的度:顶点V的度是和V相关联的边的数目,记为TD(V)。
图2.6所示图中,V0顶点的度为3。
入度:以顶点v为头的边的数目,记为ID(V)。
图2.6所示图中,V0的入度为1。
出度:以顶点v为尾的边的数目,记为OD(V)。
图2.6所示图中,V0的出度为2。
顶点的度 = 入度 + 出度。即TD(V) = ID(V) + OD(V)。

top Created with Sketch.