图的定义

图G由顶点集V和边集E组成，记为G=(V,E),其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系(边)集合。若V={$v_{1}$,$v_{2}$,…,$v_{n}$},则用|V|表述图G中顶点的个数，也称图G的阶，$E={(u,,v)|u\in V,v\in V }$,用|E|表示图G中边的条数
注意：线性表可以是空表，树可以是空树，但是图不可以是空，即V一定是非空集，但一个图的边集可以为空集

有向图、无向图

无向图

若E是无向边(简称边)的有限集合时，则图G为无向图。边是顶点的无序对，记为$(v,w)$或$(w,v)$,因为$(v,w)$=$(w,v)$，其中v、w是顶点。可以说顶点v、w互为邻接点。边$(v,w)$依附于顶点w和v，或者说边$(v,w)$和顶点v、w相关联
$G_{2}=(V_{2},E_{2})$
$V_{2}$={$A,B,C,D,E$}
$E_{2}$={$(A,B),(B,D),(B,E),(C,D)(C,E),(D,E)$}

有向图

若E是有向边(也称弧)的有限集合时，则图G为有向图。弧是顶点的有序对，记为$<v,w>$,其中v、w是顶点，v称为弧尾，w成为弧头，$<v,w>$称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。$<v,w>$≠$<w,v>$
$G_{1}=(V_{1},E_{1})$
$V$={$A,B,C,D,E$}
$E$={$<A,B>,<A,C>,<A,D>,<A,E>,<B,A>,<B,C>,<B,E>,<C,D>$}

简单图、多重图

简单图

1. 不存在重复边
2. 不存在顶点到自身的边
   

多重图

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

数据结构课程中只涉及简单图

顶点的度、入度、出度

• 对于无向图：
  • 顶点v的度是指依附于顶点v的边的条数，记为TD(v)
  • 在具有n个顶点，e个边的无向图中$\sum_{i=1}^{n}TD(v_{i})$=$2e$
  • 即无向图所有顶点的度之和等于边的个数的2倍
• 对于有向图：
  • 入度是以顶点v为终点的有向边的数目，记为ID(v)
  • 出度是以顶点v为起点的有向边的数目，记为OD(v)
  • 顶点的度等于其入度和出度的和，即TD(v)=ID(v)+OD(v)
  • 在具有n个顶点，e个边的有向图中$\sum_{i=1}^{n}ID(v_{i})=\sum_{i=1}^{n}OD(v_{i})$=$e$

顶点-顶点关系的描述

• 路径——顶点$v_{p}$到顶点$v_{q}$之间的路径是指顶点序列，$v_{p},v_{i1},v_{i2},..,v_{im},v_{q}$(有向图的路径也是有向的，无向图之间也有可能不存在路径)
• 回路——第一个顶点和最后一个顶点相同的路径称为回路或环
• 简单路径——在路径序列中，顶点不重复出现的路径称为简单路径
• 简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路
• 路径长度：路径上边的数目
• 点到点的距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若u和v根本不存在路径，则记该距离为无穷($\infty$)
• 无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的
• 有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的

连通图、强连通图

• 若无向图图G中任意两个顶点都是联通的，则称图G为联通图，否则称为非连通图
  • 常见考点：
  • 对于n个顶点的无向图G，若G是连通图，则最少有$n-1$条边
  • 若G是非连通图，则最多可能有$C_{n-1}^{2}$条边
• 若有向图中任何一对顶点都是强连通的，则称此图为强连通图
  • 常见考点：
  • 对于n个顶点的有向图G，若G是强连通图，则最少有n条边(形成回路)

研究图的局部——子图

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

连通分量

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

强连通分量

有向图中的极大强连通子图称为有向图的强连通分量

生成树

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

生成森林

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

边的权、带权图/网

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

几种特殊的图

1. 无向完全图——无向图中任意两个顶点之间都存在边
   若无向图的顶点$|V|=n$,则$|E|\in[0,C_{n}^{2}]=[0,n(n-1)/2]$
2. 有向完全图——有向图中任意两个顶点之间都存在方向相反的两个弧
   若有向图的顶点$|V|=n$,则$|E|\in[0,2C_{n}^{2}]=[0,n(n-1)]$
   
3. 稀疏图——边数很少的图称为稀疏图
4. 稠密图——反之
   没有绝对的界限，一般来说$|E|<|V|\log_{2}{|V|}$时，就可以将G视为稀疏图
   
5. 树——不存在回路，且连通的无向图
   n个顶点的树，必有n-1条边
   常见考点：n个顶点的图，若$|E|>n-1$,则一定有回路
6. 有向树——一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树
   

知识回顾与重要考点

图的存储

邻接矩阵法

1
2
3
4
5
6

#define MaxVerTexNum 100
typedef struct{
    char Vex[MaxVerTexNum];//定点表
    int Edge[MaxVerTexNum][MaxVerTexNum];//邻接矩阵，边表
    int vexnum,arcnum;//图的当前顶点数和边数/弧数
}MGrapph;

结点数为n的图G=(V,E)的邻接矩阵A是n*n的，将G的顶点编号为$v_{1},v_{2},…,v_{n}$则

如何求顶点的度、入度、出度

• 无向图
  第i个结点的度=第i行(或第i列)的非零元素个数
• 有向图
  • 第i个结点的出度=第i行的非零元素个数
  • 第i个结点的入度=第i列的非零元素个数
  • 第i个结点的度=第i行、第i列的非零元素个数之和

邻接矩阵法存储带权图(网)

1
2
3
4
5
6
7
8
9
10

#define MaxVertexNum 100
#define INFINITY 2147483647
//宏定义无穷，也可使用<limits.h>中的INT_MAX
typedef char VertexType;//顶点的数据类型
typedef int EdgeType;//带权图中边上的权值的数据类型
typedef struct{
    VertexType Vex[MaxVertexNum];//顶点
    EdgeType Edge[MaxVertexNum][MaxVertexNum];//边的权
    int vexnum,arcnum;//图当前的顶点数和弧数
}MGraph;

邻接矩阵法的性能分析

空间复杂度：$O(|V|^2)$——只和顶点数有关，和实际的边数无关
适合存储稠密图
无向图的邻接矩阵是对称矩阵，可以压缩存储(只存储上三角区/下三角区)
回顾特殊矩阵的压缩存储

邻接矩阵法的性质

设图G的邻接矩阵为A(矩阵元素为0/1)，则$A^n$的元素$A^n[i][j]$等于由顶点$i$到顶点$j$的长度为$n$的路径的数目

知识回顾与重要考点

• 如何计算指定顶点的度、入度、出度（分无向图、有向图来考虑）？时间复杂度如何？
• 如何找到与顶点相邻的边（入边、出边）？时间复杂度如何？
• 如何存储带权图？
• 空间复杂度——$O(|V|^2)$，适合存储稠密图
• 无向图的邻接矩阵为对称矩阵，如何压缩存储？
• 设图G的邻接矩阵为A（矩阵元素为0/1），则$A^n$的元素$A^n$[i][j]等于由顶点i到顶点j的长度为n的路径的数目

邻接表法(顺序+链式存储)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//顶点
tyoedef struct VNode{
    Vertextype data;//顶点信息
    ArcNode *first;//第一条边/弧
}VNode,AdjList[MaxVertexNum]；
//用邻接表存储的图
typedef struct{
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph;
//边/弧
typedef struct ArcNode{
    int adjver;
    struct ArcNode *next;
    //InfoType info //边权值;
}ArcNode;

对比树的孩子表示法

知识回顾与重要考点

十字链表法(存储有向图)