数据结构(六)——图

六、图

6.1 图的基本概念

图的定义

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

注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集

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

有向图：若E是有向边（也称弧）的有限集合时，则图G为有向图。 弧是顶点的有序对，记为<v,w>，其中v、w是顶点，v称为弧尾，w称为弧头，<v,w>称为从顶点v到顶点w的弧，也称 v邻接到w，或w邻接自v。<v,w> ≠<w,v>
                            
简单图——① 不存在重复边； ② 不存在顶点到自身的边  （数据结构课程只探讨 “简单图”）

多重图——图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联

顶点的度、入度、出度

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

有向图：入度是以顶点v为终点的有向边的数目，记为ID(v)；
出度是以顶点v为起点的有向边的数目，记为OD(v)。
顶点v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。
在具有n个顶点、e条边的有向图中，，即入度和出度的数量相等且等于e

顶点的关系描述

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

图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。

若图中任何一对顶点都是强连通的，则称此图为强连通图。

研究图的局部—子图、生成子图

设有两个图G = (V, E)和G ′ = (V ′ , E ′ )，若V ′ 是V的子集，且 E ′ 是 E的子集，则称G ′ 是G的子图
若有满足V(G ′ ) = V(G)的子图G ′ ，则称其为G的生成子图

有向图的子图和生成子图也是一样的

无向图中的极大连通子图称为连通分量
       子图必须连通，且包含尽可能多的顶点和边

有向图中的极大强连通子图称为有向图的强连通分量
        子图必须强连通，同时 保留尽可能多的边

生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图。
若图中顶点数为n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通 图，若加上一条边则会形成一个回路。(因此边要尽可能的少，但要保持连通)

生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林

边的权、带权图/网

边的权——在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
带权图/网——边上带有权值的图称为带权图，也称网。
带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

特殊形态的图

无向完全图——无向图中任意两个顶点之间都存在边
若无向图的顶点数|V|=n，则

有向完全图——有向图中任意两个顶点 之间都存在方向相反的两条弧
若有向图的顶点数|V|=n，则

稀疏图：边数很少的图称为稀疏图  反之称为稠密图
         
树——不存在回路，且连通的无向图
n个顶点的树，必有n-1条边。
常见考点：n个顶点的图，若 |E|>n-1，则一定有回路

有向树——一个顶点的入度为0、其余顶点的 入度均为1的有向图，称为有向树