问题描述 n个村庄间架设通信线路，每个村庄间的距离不同，如何架设最节省开销？...这就是一个最小代价生成树的问题，可以用Prim算法或kruskal算法解决。 PS1：无向连通图的生成树是一个极小连通子图。 PS2：生成树是图的一个子图，包括所有的顶点和最少的边（n-1条边）。...PS3：最小代价生成树就是所有生成树中权值之和最小的那个。 算法思路 算法的目标很明确，就是要在n个节点的图中，找出n-1个节点，并且节点之间连线的权值是最小的。...，其中选边方式（贪心准则）的不同，就产生不同的最小代价生成树算法。...key表示指定节点的编号； value表示在最小代价生成树中，该节点的前驱节点的编号。
（程序设计） 2.2 计算机通信产生的背景 待处理的数据量急剧增加，而且要进行远距离传输 信息产业 单机的速度与容量的提高已经不能满足社会的需要，因此计算机与通信的结合是必然的结果 2.3 计算机通信...高效率通信的联机系统 改进后的联机系统 高效率通信的联机系统 2.3.3 交换技术 传统的电话网络（PSTN）的交换系统不适合计算机的数据传输 计算机的数据传输具有间歇性 计算机通信具有突发性...这与电话系统的交换局一样，因为任意一对用户都是用公共的网络，转接是必然的，转接技术直接影响了通信质量和线路利用率。它与信道共享问题密切相关 3.10 流量控制 流量是计算机通信过程在网络中的通信量。...在某一段时间里，如果对网络资源的需求超过了网络所能提供的，则产生了拥塞，解决网络拥塞的办法是流量控制 3.11 寻址与路由选择 在互联网中，两台计算机可能位于不同的子网上，此时的寻址问题最为复杂。...寻址是计算机通信中最基本的问题 在网络中两台计算机通信时，它们之间可能经过许多转接点和链路，也可能经过许多通信子网，有许多路由，如何选择其中一条，这就是路由选择要解决的问题 4 数据通信系统的体系结构
例如：3 2 1，交换1 3后为递增排序，总的交换代价为4。 给出N台机器的重量，求将所有机器变为有序的最小代价（机器的重量均为正整数）。 输入 第1行：1个数N，表示机器及房间的数量。...(1 <= Wi <= 10^9) 输出 最小代价 样例1输入 51 8 976 样例1输出 41 二、思路 以样例1例，先进行排序 下标 1 2 3 4 5 排序前 1 8 9 7 6 排序后 1 6...剩下一个环不用交换，那么当前的最小值就是42，但是这不一定是最优解。...这种策略的解可表示为ans1 = sum + min * (cnt - 1)，这里min是当前环中的最小值，cnt是min与别的元素交换的次数。 策略二: ?...，min表示当前环中的最小值。
第二章 应用层 仅个人学习总结，不具有普适性与正确性 知识点 DNS运行在UDP上，使用53端口 HTTP/1.1 默认使用persistent connection with pipelining：通过使用
第三章 传输层 仅个人学习总结，不具有普适性与正确性 知识点 TCP不提供Delay guarantees 和 bandwidth guarantees服务 TCP提供可靠数据传输、流量控制、拥塞控制、...对于当今的高性能web服务器通常使用一个进程，但是为每个新的客户链接创建一个具有新套接字的新线程与之通信。...而UDP报文如果源IP或者源端口号不同，但是目的IP和端口相同，就能被定向到同一个套接字 0~1023 周知端口号 UDP报文首部仅包含源端口号，目的端口号，长度（首部加数据）与校验和。...每个字段由两个字节组成 最大传输单元：用来通知对方所能接受数据服务单元的最大尺寸 最大报文长度：用于在TCP连接建立时，收发双方协商通信时每一个报文段所能承载的最大数据长度，不包括首部。...协议允许窗口最大K-1，SR协议允许窗口最大为K/2 一旦收到三个冗余ACK，发送发执行快速重传 流量控制（flow control）用于适应接收方读取速率，拥塞控制（congestion control）用于适应网络传输的速率
第一章 计算机网络和因特网 仅个人学习总结，不具有普适性与正确性 知识点 TCP为面向连接的服务，能提供可靠的数据传输服务。...P2P应用程序相互交换数据 各层的协议称为协议栈（protocol stack） 应用层、传输层、网络层、数据链路层、物理层 在计算机网络体系结构的每个层次中，每个报文都被分为两部分...这是按照《计算机网络自顶向下方法》书中的定义，因特网文献（如RFC文档）将TCP的运输层分组称为报文段（segment），而UDP与网络层的分组都称为数据报（datagram）。...数据报网络与虚电路网络 在电路交换网络中，端系统通信会话期间，预留了端系统之间沿路径通信所需的资源，而在分组交换当中这些资源不会被预留。...等效概念 copper wire 铜线 coaxial cable 同轴电缆 communication links 通信链路 fiber optics 光纤 communication
MAC地址表，并把数据交付到与目标计算机物理地址所匹配的端口，所以数据包只会发送到那台计算机。...、“交通警察” 路由器的缺点是适用于大规模的网络，可以适应复杂的网络拓扑结构，是负载共享的最优路径，而且路由器的安全性高，隔离不需要的通信量，节省局域网的频宽，减少主机负担。...因为需要广播请求报文，因此RARP只能用于具有广播能力的网络 使用与ARP相同的报头结构 作用与ARP相反，用于将MAC地址转换为IP地址 后来被BOOTP、DHCP所取代 3.ICMP协议 ICMP...IP协议在OSI参考模型中应用于网络层，以“数据包”为单位。 特点 IP协议是一种无连接、不可靠的分组传送服务协议 IP协议是点-点线路的网络层通信协议。...地址由2部分组成：网络标识(网络ID)、主机标识(主机ID)，通过子网掩码(subnet mask)可以得知网络ID、主机ID 主机所在的网段 = 子网掩码 & IP地址 计算机和其他计算机通信前，会先判断目标主机和主机是否在同一网段
输入一个数组，返回分割的最小代价。...实际上这里等同于如何把数组里三个值花费最小代价拼成60 这里仿照建树规则,新建立的结点值加在一起即是花费的钱数 具体方法,每次从数组中拿两个最小值建树,新得到的值再加入树中,依次类推,直到树得到根.
第四、五章网络层 知识点 ipv4为32位，ipv6为128位 有限广播地址：有限广播地址也称为本地广播地址，TCP/IP协议规定32位全为1的IP地址（255.255.255.255）用于本网广播 直接广播地址...：当广播地址包含一个有效的网络号和主机号，技术上就称为直接广播地址 有限广播的数据包里不包含自己的ip地址，而直接广播地址里包含自身的ip地址 一个IP的广播地址可以通过将该IP地址的网络地址部分保持不变...因此，判断一个IP地址是A、B还是C类地址，只需要查看它的第一段数字即可 网络层具有三个主要组件： IP协议、因特网控制报文协议（ICMP，Internet Control Message Protocol...179来传输路由信息，路由器之间通过TCP协议的会话来交换路由信息 拥塞的路由器向一台主机发送ICMP源抑制报文，以强制该主机减少发送速率 ARP协议根据IP地址查询MAC物理地址 在RIP协议中，到达网络的距离为
计算机协议就是计算机之间的约定，是为了减少通信成本、沟通成本等。 计算机之间的传输媒介是光信号和电信号. 通过 "频率" 和 "强弱" 来表示 0 和 1 这样的信息。...但是实际的网络通信协议，设计的会更加复杂, 需要分更多的层。...局域网（Local Area Network，LAN）是一种覆盖有限地理范围（如办公室、建筑物或校园）的计算机网络。 我们需要明确两台计算机在一个局域网中，是可以进行直接通信的。...3.跨网络通信 如果要进行跨网络通信，就需要IP地址来进行标识！ 3.1.IP地址 IP 协议有两个版本, IPv4 和 IPv6，默认都是指 IPv4。...3.4.跨网络通信总结 网络层(就是IP层)向上（包括网络层）看到的所有的报文的都是一样的，至少是IP报文。 IP可以屏蔽底层网络的差异 所以的网络都是IP网络，所以手机，电脑和平板都可以互相通信！
总感觉这个概念，和研发有点脱节； 一、基础概念 不同设备之间通过网络进行数据传输，并且基于通用的网络协议作为多种设备的兼容标准，称为网络通信； 以C/S架构来看，在一次请求当中，客户端和服务端进行数据传输的交互时...，在不同阶段和层次中需要遵守的网络通信协议也不一样； 应用层：HTTP超文本传输协议，基于TCP/IP通信协议来传递数据； 传输层：TCP传输控制协议，采用三次握手的方式建立连接，形成数据传输通道；...网络层：IP协议，作用是把各种传输的数据包发送给请求的接收方； 通信双方进行交互时，发送方数据在各层传输时，每通过一层就会添加该层的首部信息；接收方与之相反，每通过一次就会删除该层的首部信息； 二、JDK...源码 在java.net源码包中，提供了与网络编程相关的基础API； 1、InetAddress 封装了对IP地址的相关操作，在使用该API之前可以先查看本机的hosts的映射，Linux系统中在/etc...，当连接处于建立的状态，就可以进行正常的通信，即数据传输；四次挥手：关闭连接的过程，调用close方法，即连接使用结束，在这个过程中进行了四次网络通信； 四、Http组件 在服务通信时依赖网络，而对于编程来说
文章目录 一、HTTPS 简介 二、HTTP 通信过程 一、HTTPS 简介 ---- HTTPS 协议就是在 HTTP 协议的基础上 , 增加了一个 SSL 外壳 , 对 HTTP 协议进行加密 ;...HTTP 协议传输数据时 , 传输的就是 明文 , 如果抓包或者截获后 , 可以直接看到传输的数据内容 ; HTTPS 协议在网络传输时 , 传输的内容是 加密后的内容 , 不是明文 , 更不容易被截获...无法确保数据完整性 ; ④ 快速 , 灵活 , 高效 ; HTTPS 特点 : ① 安全性强 : 传输数据加密 , 中间截获 , 无法进行解密 ; ② 身份验证 : 通过 SSL 认证证书 , 确认通信的...客户端 与 服务器 双方的身份 ; ③ 数据完整性 : 加密后的数据能防止被截获修改 ; 二、HTTP 通信过程 ---- 发送 HTTP 请求 , HTTP 基于 TCP , 因此需要先建立 TCP
路由选择算法的分类 1. 带权无向图 将网络抽象为一个带权无向图G=(N,E)， N表示结点集合， E是边的集合。 网络中的路由器抽象为图G的结点， 连接两个路由器的网络链路抽象为G的边。...算法概念 链路状态路由选择算法是一种全局式路由算法， 需要构建出整个网络的拓扑图。 链路状态路由选择算法： 利用 Dijkstra算法 求最短路径。 ?...层次化路由选择 在合理的网络规模范围内： LS算法和DV算法。 大规模网络：层次化路由选择（最有效可行的解决方案）。 层次化路由选择组成： 1....Internet路由选择协议 Internet层次化路由选择分为内部网关协议与外部网关协议。 1....OPEN（ 打开） 报文， 用来与BGP对等方建立BGP会话。 (2). UPDATE（ 更新） 报文， 用来通告某一路由可达性信息， 或者撤销已有路由。 (3).
Ⅱ、Kruskal算法 任给一个有 n 个顶点的连通网络 N={V,E}， 首先构造一个由这 n 个顶点组成、不含任何边的图 G={V,NULL}，其中每个顶点自成一个连通分量， 其次不断从 E 中取出权值最小的一条边...除了 Kruskal 算法以外，普里姆算法（Prim 算法）也是常用的最小生成树算法。...除此之外，我们还 需要判断一下加入的边会不会构成环，考虑到 Prim 算法与 Kruskal 算法不同的点也在于 Prim 算法是以点为对象的，所以我们时时刻刻都知道哪些点是已经确定的，所以我们可以用一个...srci = GetVertexIndex(src); // 初始化图，与Kruskal算法一样 size_t n = _vertexs.size(); minTree....总的来说，Prim 算法是 以点为对象，挑选与点相连的最短边来构成最小生成树。而 Kruskal 算法是以边为对象，不断地加入新的不构成环路的最短边来构成最小生成树。
最小生成树： 构造连通图的最小代价生成树称为最小生成树，也就是说，所有的边加权后和最小的树。 Prim算法 Prim算法计算最小生成树的方法从一个结点开始使树一点点的成长。...每次选择一个顶点，使得它和上一个顶点之间的代价最小，并把这条边加入到最小生成树中，把顶点加入到集合中。...下面通过图示来描述Prim算法的思想：首先选择一个顶点作为起始，比如A，第一轮发现AC代价最小，那么就把AC边加入最小生成树，把A加入顶点集合； 后面依次寻找最小代价边，直到全部顶点都加入到顶点集合。...在程序中，通过一个最小代价标记，并一行一行的扫描来搜索最小代价边，下面来看具体代码。首先我们定义一个图的数据类型，该数据类型包含图的顶点集合、邻接矩阵，顶点数和边数。...= m) /* 假如n与m不等，说明此边没有与现有的生成树形成环路 */ { parent[n] = m; /* 将此边的结尾顶点放入下标为起点的parent中
报文 报文是网络交换与传输的数据单元，它具有一定的内在格式，并通常都具有头部+数据载荷+尾部的基本结构。在传输过程中，报文的格式和内容可能会发生改变。...补充解释： 物理层实现了逻辑上的数据与可以感知和测量的光/电信号之间的转换。物理层功能是通信过程的基础。物理层关注的是单个“0”和“1”的发送、传输和接收。...计算机接收数据时，数据会从底层向高层逐层传递，在传递过程中进行相应的解封装。 4.TCP/IP协议簇 TCP/IP模型与OSI模型的主要差别在二者使用的具体协议的不同。...并行通信中，每一条数据通道上的阐述原理都与串行通信类似。通常，并行通信是以字节为单位来进行传输的。例：计算机与数字投影仪之间的通信方式就是一种并行通信方式。...卫星与地面接收终端之间的通信方式 半双工方式 信息的流向可以从A到B，也可以从B到A，但信息不能同时在两个方向上进行传递。如果A和B同时发送数据，则通信双方都不能成功接收到对方发送的数据。
计算机与网络(一) 写了几个月的学习笔记（虽然是每周一篇），发现了新世界，以前只觉得花时间写学习笔记效率不是很高，一直没有写过学习笔记之类的，但是实际上，写学习笔记的过程实际上又是重新复习了一下。...它采用 TCP/IP 协议族作为通信规则，是一个覆盖全球的、实现全球范围内连通性和资源共享的计算机网络。...指当前全球最大的、开放的、由众多网络相互连接而成的特定计算机网络，它采用 TCP/IP 协议族作为通信规则，其前身是美国的 ARPANET。（1990 年正式宣布关闭)。...：使用通信的时候占用的所有通信资源 计算机数据具有突发性，导致在传送计算机数据时，通信线路的利用率很低（传数据的时间不到 10%，甚至不到 1%） 分组交换 主要特点： 采用存储转发技术...当信道的利用率增大时，引起的时延也会随之增加 时延与利用率的关系 6.2 计算机网络的非性能指标 费用 质量 标准化 可靠性 可扩展性和可升级性 易于管理与维护
Prim算法：此算法可以称为加点法，使用贪心思想进行求解，Vnew Vold-new 之间，代价最小的边对应的点，加入到Vnew之中；算法从任意一节点开始，知道Vnew中包含所有的点； 图中所有顶点集合...V, 初始结合Vnew = {s}, Vold-new = V-Vnew; 在两个集合Vnew和Vold-new 组成的边中，选择代价最小的边（vnew, vold-new）,加入到生成树；并把vold-new...，这时权值最小的边在最小生成树中，与原有假设构成矛盾，所以权值最小的边一定在最小生成树中；所以prim每次选入权值最小的边的点加入的策略是正确的。...Kruskal算法：此算法可称为加边法；初始生成树边数为0，每次就选择一条满足条件的最小代价的边，加入到生成树的边集合中； 把图中的所有边按代价从小到大排序； 把图中的n个顶点，看成独立的n棵树组成的森林...; 参考链接： https://www.cnblogs.com/zhchoutai/p/8687614.html 极大连通子图与极小连通子图 最小生成树（Kruskal和Prim算法） 图论——最小生成树
以下为深度优先算法的规则 规则1、：访问一个邻接的未访问的节点，标记它，并把它放入栈中 规则2、当不能执行规则1是，从栈弹出一个顶点 规则3、如果不能完成规则1 规则2则完成搜索 对于最小生成树，和深度优先算法相似...*/ package com.xzg.heap; /** * @author hasee * @TIME 2017年5月2日 * 1、图的表示，使用临接表或邻接矩阵 * 2、深度优先搜索算法...}//重置标志位 for(int j=0;j<nVert;j++){ vertxList[j].wasVisited = false; } } /** * 深度优先算法实现最小生成树...theaStack.pop(); }else{ vertxList[v].wasVisited = true; theaStack.push(v); //这里是最小生成树保存...;i++) vertxList[i].wasVisited = true; } } /** * @param v * @return * 深度优先算法关键是找到邻接且没有被访问过的点
通信协议综述 概述 一、为什么学习网络协议 1.1 常见的网络协议 二、网络分层的真正含义 2.1 为什么网络要分层？...---- 概述 本文也是根据专栏里的板块，对通信网络协议做一个综述，共分为四节去进行介绍； 为什么学习网络协议？...城关与城关之间的沟通协议叫做路由协议，常用的由OSPF和BGP； 城关与城关之间是一个国家，网络包知道了要去哪个城关的时候，还是要使用国家内部的MAC地址，通过下一个城关的MAC地址，找到下一个城关，然后在问下一步该怎么走...把这一连串说完，相信你的面试官也会觉得你学的很扎实； 二、网络分层的真正含义 计算机网络知识点需要背诵，但是更是要理解透彻； 2.1 为什么网络要分层？...总结 ---- 本文是对通信协议综述的总结，共分为四节去介绍： 为什么学习网络协议？
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
即时通信 IM
腾讯会议
