图

发表于2024-08-04|更新于2026-06-10|Computer Basics

|浏览量:

图

概念

图：由顶点集合和顶点间的关系集合组成的一种数据结构
有向图与无向图：在有向图中，顶点对(x,y)是有序的；无向图是无序的
完全图：在有n个顶点的图有n(n-1)/2条边，即为完全无向图；有n(n-1)条边，即为完全有向图
顶点的度：某一个顶点与其相关联的边的条数，有向图度是入度和出度之和
生成树：一个连通图的生成树是其极小连通子图，包括图中所有顶点，包含n-1条边

图的存储结构－邻接矩阵

在图的邻接矩阵表示中，有一个记录仪各个顶点信息的顶点表，还要一个表示各个顶点之间关系的邻接矩阵
网络的邻接矩阵

邻接表

邻接表是邻接矩阵的改进形式，需要把邻接矩阵的各行分别组织为一个单链表、
无向图的邻接表：
有向图的邻接表和逆邻接表：
网络邻接表：

图的遍历与连通性

DFS（深度优先搜索）
BFS（广度优先搜索）

连通分量和生成树

极小连通子图（一棵生成树）
广度优先生成树、深度优先生成树
非连通无向图生成的生成树组将组成非连通图的森林
最小生成树（MST）
- 网络带权重的最小和的生成树
Prim算法：从顶点开始依次找最短边，然后相连
Kruskal算法：将权重最短的不构成环的两点依次相连

TODO这里比较简略有机会可以考虑重新复习

AOV网络

有先后顺序的网络关系
构造AOV网络全部顶点的拓扑有序序列的运算叫拓扑排序

AOE网络

关键路径：完成整个工程所需的时间取决于从源点到汇点的最长路径长度。这条路径最长的路径叫关键路径
最短路径：两个地点之间的带权路径之和最短的路径
- Dijkstra算法
- Bellman和Ford算法
- Floyd算法

文章作者: xhj

文章链接: https://hzhzxfs.github.io/2024/08/04/%E5%9B%BE/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 xhj的博客！

Computer Basics

相关推荐

树与二叉树

树与二叉树树定义：树是n个结点的有限集合，在任何一个非空的树中有且只有一个根节点子女：结点的子树非空，结点子树的根即为结点的子女双亲：结点有子女，该结点是子女的双亲兄弟：某一结点的所有子女，互为兄弟度：结点的子女个数分支结点：非终端结点叶：终端结点祖先：沿着双亲的路径返回均为祖先子孙：下属所有结点结点的层次：规定根节点在第一层，子女依次加1 深度：层次的最大值树的高度：根节点的高度->所有子女高度+1 有序树：树的结点的各棵子树是从左到右有顺序的无序树：无序，各棵子树之间的次序可以呼唤森林：m棵互不相交的树组成二叉树二叉树中不存在度大于2的结点满二叉树完全二叉树：k层二叉树除了第k层有从有向左的连续缺失的结点二叉树的顺序表示按照满二叉树的顺序，有数则填，无数则留空极端情况下，资源利用率特别低二叉树的链式表示二叉链表三叉链表二叉树遍历前序遍历（VLR）【-+a*b-cd/ef】中序遍历（LVR）【a+b*c-d-e/f】后序遍历（LRV）【abcd-*+ef/-】 ...

数据通信原理

数据通信原理通信系统的基本组成通信三要素：信源：信息的发送者，是发出各种信息（文字、图片或者数据）的信息源信宿：信息的接受者载体：传送信息的媒体（信道）噪声的存在对通信产生不利影响通信系统的基本组成变换器：将信源发出的信息变为载体上看传输的格式反变换器：将载体上传输的信息变换成信宿可识别格式信道：信息可以单向传输的途径按传输类型分类：有线信道无线信道按传输方式分类：模拟信道数字信道信道带宽：信道可以不失真地传输信号的频率范围信道容量：信道在单位时间内可以传输的最大信号量数据传输速率（bps）：信道在单位时间内可以传输的最大比特数。差错率、误码率：出错/总数、与传输距离成正比由于噪声的影响和信道带宽的限制，信号可能发生失真调制/解调：利用模拟信道支持数据信息传输的技术调制：将数据信息变换成适合于模拟信道上传输的电磁波信号（数字->模拟）解调：将从模拟信道上收取的载波信号还原成数据信息（模拟->数字）调制解调器：具有调制、解调功能的通信设备调制方法调制依据：模拟信号的三...

数组与广义表

数组与广义表一维数组数组是相同类型的数据元素的集合，而一维数组的每个数组元素是一个序对，由index和value组成一维数组一般会被看成向量vector，二维数组一般被看成向量组多维数组特殊矩阵的压缩存储特殊矩阵是指非零元素和零元素的分布有一定规律的矩阵特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵,为了节省存储空间,对可以不存储的元素,如零元素或者对称元素,不再存储对称矩阵沿着主对角线只需要一半的空间三对角矩阵沿着主对角线形成一个列表稀疏矩阵如果矩阵中很多数量是0，只需要存储对应的坐标和value的值即可在稀疏矩阵的三元组表中，非零矩阵元素按照行存放，行号相同的时候，按照列号递增存放十字链表对于稀疏矩阵，当非0元素的个数和位置在操作过程中变化较大时（如相加），采用练市存储结构比较方便广义表列表里面的元素自定义，也可以是一个类型，可以类比Python中的list Samples： A()：深度1，长度0 B(6,2)：深度1，长度2 C(‘a’,(5,2))：深度2，长度2 D(B, C)：深度3，长度2 F(4, F)：深度...

计算机网络概述

计算机网络概述网络的发展计算机网络 = 计算机 + 通信 + 用户需求计算机发展过程：单机：单个用户独占系统资源（主机）分时系统：分时多用户系统：多个用户利用多台终端共享单台计算机的资源远程访问系统：利用通信线路将远程终端连接到主机，不受地域限制地使用计算机资源网络：将多台计算机连接在一起，相互共享资源计算机网络以共享资源（硬件、软件和数据资源等）为目的而连接起来的、在协议控制下，由一台或多台计算机、若干台终端设备、数据传输设备等组成的系统的集合。这些计算机系统应当具有能独立自治能力的操作系统。计算机联网的主要目的：资源共享：硬件共享：大型计算机的处理能力，昂贵的外设软件共享：应用软件、系统软件等数据共享：用户数据等数据传输：支持用户之间的数据传输（如 smtp、ftp、ip 等），计算机网络可以使得分布于全球的计算机协作起来，形成一个巨大、虚拟的计算机。网络的类型：根据网络覆盖范围 Wide Area Network (WAN) 广域网 Local Area Network (LAN) 局域网...

绪论O记号问题：随着问题规模的增长，计算成本是如何变化的？考虑的是计算成本的增长趋势分析：在问题规模足够大的情况下，计算成本如何变化：需要执行的基本操作次数T(n) 需要占用的存储单元数量S(n)，一般不考虑空间占用对于T(n)转为O(f(n)) 常系数可以忽略，低次项可以忽略 O复杂度计算基于悲观的角度判断代码的复杂度常数复杂度O(1)：不含转向（循环、调用、递归等），部分特例虽然含有循环、调用、递归等，但是需要考虑到实际情况才能确定。对数复杂度O(log n)：高效，复杂度无限接近常数多项式复杂度O(n^c)：界定为多项式的最高次项线性复杂度O(n) 指数复杂度O(c^n)：计算成本高 1234567void func(int n){ // n是正整数 int i = 1; while(i<=n)i*=2;}// 被嵌套的深层语句是i*=2；频率由i<=n决定，显然时间复杂度为O(log n) 冒泡排序观察：有序序列中，任意一对相邻元素顺序 / 无序序列中，存在一对相邻元素逆序 ...

线性表线性表定义：由n个数据元素组成的有限序列；原则上数据类型可以不一致，但存储类型可能会做出一定的限制特性: 除第一个元素外,其他元素只有一个直接前驱;除了最后一个元素,其他元素只有一个直接后继. 表示方式:顺序存储方式/链表存储方式顺序表定义:将线性表中的元素相继存放在一个连续的存储空间中,可以利用一维数组描述数据结构特性:所有元素的逻辑先后顺序和物理存放顺序一致 123456789101112131415161718192021const MAX_SIZE = 100// SQListA 顺序表的静态存储表示type SQListA struct{ data [MAX_SIZE]int64 length int}// SQListB 顺序表的动态存储表示type SQListB struct{ data *int64 length int}// Init_SQ 初始化顺序表func Init_SQ(list *SQListA) bool{ list.d...