成都网站建设设计

将想法与焦点和您一起共享

第六章图-创新互联

免责声明:

在塔什库尔干塔吉克等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供网站制作、成都网站建设 网站设计制作定制制作,公司网站建设,企业网站建设,成都品牌网站建设,成都全网营销,成都外贸网站建设公司,塔什库尔干塔吉克网站建设费用合理。
  • 笔记来源:本系列所有笔记均整理自 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; // 弧数
};

邻接表中:

  • 对于无向图,所需的存储空间为|V| + 2*|E|,|V|为顶点数,|E|为边数,因为一条边的信息会存储两次
  • 对于有向图,所需的存储空间为|V| + |E|,|V|为顶点数,|E|为边数
  • 图的邻接表的表示方式并不唯一

在这里插入图片描述

2.3 十字链表(有向图)

在这里插入图片描述

在这里插入图片描述

2.4 邻接多重表(无向图)

在这里插入图片描述

3 图的基本操作

图的基本操作独立于图的存储结构,不同的存储结构,同一操作算法的不同实现会有不同的性能。下面针对邻接矩阵和邻接表两种存储结构进行分析:

判断图中是否存在边(x,y)或者弧

在这里插入图片描述
在这里插入图片描述

求图中与顶点x邻接的边

在这里插入图片描述
在这里插入图片描述

4 图的遍历

图的遍历是指,从图的某一个顶点出发,按某种搜索方式,沿着图中的边对其他顶点访问一次(仅仅访问一次)。为避免同一顶点被访问多次,在遍历的过程中,需记下每个已经访问过的顶点,可以使用一个数组来存储这些已经访问过的顶点。

图的遍历算法主要有两种:广度优先和深度优先。

4.1 广度优先遍历 算法思想

广度优先搜索(Breadth-First-Search,BFS)。类似于二叉树的层序遍历。

算法思想:找到与一个顶点相邻的所有顶点,标记哪些顶点被访问过,借助一个辅助数组,为了实现逐层访问,还需要借助一个辅助队列,用来存储正在访问的顶点的下一层顶点。

算法实现

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

算法性能分析

在这里插入图片描述

广度优先生成树

在这里插入图片描述
在这里插入图片描述

广度优先生成森林

在这里插入图片描述

4.2 深度优先遍历 算法思想

深度优先(Depth-First-Search,DFS),类似于树的先序遍历。

基本思想:从一个顶点v1开始,访问与其邻接且未被访问的任意顶点w1,再访问与w1邻接且未被访问的任意顶点,重复直到不能继续向下访问时,依次退回到最近被访问的顶点,若其还有未被访问过的顶点,以同样的搜索方式继续,直到所有的顶点都被访问过为止。

算法实现

在这里插入图片描述
在这里插入图片描述

算法性能分析

在这里插入图片描述

在这里插入图片描述

5 图的应用 5.1 最小生成树 5.2 最短路径问题 BFS算法 Dijkstra算法 Floyd算法 5.3 有向无环图描述表达式 5.4 拓扑排序 5.5 关键路径

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


新闻名称:第六章图-创新互联
路径分享:http://chengdu.cdxwcx.cn/article/dphppo.html