第八章：图

基本概念

定义

无向图和有向图

简单图和多重图

无向完全图和有向完全图

• 无向完全图n个顶点有边
• 有向完全图n个顶点有边

子图

• 设有两个图和，若是的子集，是的子集，则称是的子图，且若则称是的生成子图

连通和强连通

连通图和强连通图

• 连通图：任意两个结点之间都是连通的
• 强连通图：任意两个结点之间都是强连通的
• n个顶点的连通图最少有n-1条边
• n个顶点的强连通图最少有n条边

生成树和生成森林

• 生成树：连通图包含全部顶点的一个极小连通子图

• 生成森林：非连通图所有连通分量的生成树组成生成森林

  

顶点的度

• 度：以该顶点为一个端点的边的数目

• 对于无向图：n顶点，e条边的无向图的度的总数为2e

• 对于有向图：顶点的度为出度和入度之和，n顶点，e条边的有向图的度的总数为e

有向树

• 一个顶点的入度为0，其余顶点的入度为1的有向图

路径和路径长度

• 路径：图中顶点v到顶点w的顶点序列，序列中顶点不重复的路径称为简单路径
• 路径长度：路径上边的数据，若该路径的路径长度最短，则成为距离

回路

• 回路：第一个顶点和最后一个顶点相同的路径

邻接矩阵法

有向图存储方法

• 对角线上都是0

无向图存储方法

• 是对称矩阵

定义

• 邻接矩阵法的空间复杂度为O()

#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct {
    VertexType Vex[MaxVertexNum];
    EdgeType Edge[MaxVertexNum][MaxVertexNum];
    int vexnum, arcnum;
}MGraph;

#