【数据结构】图的基本概念

1. 图的定义

图G由顶点集V和边集E组成，即为G=(V, E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系（边）集合。若V={v1,v2,……vn}，则用|V|表示图G中顶点的个数，也称图G的阶，E={(u,v) | u∈V,v∈V}，用|E|表示图中G中边的条数。

2. 有向图与无向图

若E是无向边（简称边）的有限集合时，则图G为无向图。边是顶点的无序对，即为(v,w)或(w,v)，因为(v,w)=(w,v)，其中v,w是顶点。可以说顶点w和顶点v互为邻接点。边(v,w)依附于点w和v，或者说边(v,w)和顶点v,w相关联。

G2=(V2,E2)

V2={A,B,C,D,E}

E2={(A,B),(B,D),(B,E),(C,D),(C,E),(D,E)}

若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v,w>，v称为弧尾，w称为弧头，<v,w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。<v,w>≠<w,v>。

G1=(V1,E1)

V1={A,B,C,D,E}

E1={<A,B>,<A,C>,<A,D>,<A,E>,<B,A>,<B,C>,<B,E>,<C,D>}

无向图实际应用：微信好友

有向图实际应用：微博粉丝

3. 顶点的度、入度、出度

对于无向图：顶点v的度是指依附于该顶点的边的条数，记为TD(v)。在具有n个顶点、e条边的无向图中

即无向图的全部顶点的度的和等于边数的2倍。

对于有向图：入度是以顶点v为终点的有向边的数目，记为ID(v)。出度是以顶点v为起点的有向边的数目，记为OD(v)。顶点v的度等于其入度和出度之和，即TD(v)=ID(v)+OD(v)。

在具有n个顶点、e条边的有向图中：

4. 顶点-顶点的关系描述

路径：顶点vp到顶点vq之间的一条路径是指顶点序列。
回路：第一个顶点和最后一个顶点相同的路径称为回路或环。
简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。
简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
点到点的距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若u到v根本不存在路径，则记该距离为无穷。
无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。
有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。