第六章图-创新互联

免责声明：
在塔什库尔干塔吉克等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供网站制作、成都网站建设网站设计制作定制制作,公司网站建设,企业网站建设,成都品牌网站建设,成都全网营销,成都外贸网站建设公司,塔什库尔干塔吉克网站建设费用合理。
笔记来源：本系列所有笔记均整理自 B站·王道考研·数据结构视频教程。
参考书籍：《2021年数据结构考研复习指导》，王道论坛所著，电子工业出版社出版，ISBN ：9787121379819。

1 图的概念

图G，由顶点集V和边集E组成，记作G(V,E)

顶点集V 不能为空，一个图至少得有一个顶点，图不可以是空图；图中的顶点个数称为图的阶。
边集E可以为空

顶点就好比火车站，边就好比火车站间的铁路。

有向图与无向图

在这里插入图片描述

简单图与多重图

在这里插入图片描述

图的逻辑结构应用

在这里插入图片描述

顶点的度

在这里插入图片描述

顶点与钉钉之间的关系

在这里插入图片描述

连通图与强连通图

在这里插入图片描述

子图

在这里插入图片描述

无向图的连通分量

在这里插入图片描述

有向图的强连通分量

在这里插入图片描述

连通图的生成树

在这里插入图片描述

边的权值与带权图

在这里插入图片描述

完全图

在这里插入图片描述
顶点为 n 的无向完全图，边数为 n * (n-1) / 2
顶点为 n 的有向完全图，边数为 n * (n-1)

树与有向树

在这里插入图片描述

2 图的存储结构 2.1 领接矩阵

领接矩阵：使用一个一维数组存储顶点信息，使用一个二维数组存储边的信息（顶点间的邻接关系），这个二维数组称为邻接矩阵。
在这里插入图片描述

#define MAX_V_NUM 100
typedef char V; // 顶点的数据类型
typedef int E; // 边上权值的数据类型
// 邻接矩阵结构
struct MGraph{V vertex[MAX_V_NUM]; // 顶点
	E edge[MAX_V_NUM][MAX_V_NUM]; // 邻接矩阵，边表
	int v_num; // 图的当前定点数
	int arc_num; // 图的当前边数/弧数
};

当邻接矩阵中的元素只表示对应的边是否存在时，可以将其定义为0表示边不存在，1表示边存在。

无向图的邻接矩阵是一个对称矩阵，对于规模较大的对称矩阵可以采用压缩存储。

顶点数为n的图，邻接矩阵表示法的空间复杂度为O(n^2)

2.2 邻接表

邻接表：对每个顶点建立一个单链表，单链表中存储依附于这个顶点的边，结合顺序存储和链式存储。

#define MAX_V_NUM 100

typedef char V; // 顶点数据类型

// 边表结点
struct ArcNode{int adjvex; // 这条弧所指向的顶点位置
	ArcNode* next; // 指向下一条弧的指针
};

// 顶点表结点
struct VNode {V data; // 顶点信息
	ArcNode* first; // 指向依附于该顶点的第一条弧的指针
};
// 邻接表
typedef VNode AdjList[MAX_V_NUM] ;

struct ALGraph{AdjList vertices; // 邻接表
	int vexnum; // 顶点数
	int arcnum; // 弧数
};

邻接表中：