目录第1关：图的概念任务描述相关知识图的概念习题参考第2关：图的表示任务描述相关知识图的表示编程要求测试说明习题参考第3关：单源最短通路问题任务描述相关知识单源最短通路Dijkstra算法编程要求测试说明习题参考第1关：图的概念任务描述本关任务：学习图的基本概念，完成相关练习。相关知识为了完成本关任务，你需要掌握：图的概念。图的概念1.一个图G是一个有序三元组G=，其中V是非空顶点集合，E是边的集合，ϕ是E到uv∣u,v∈V的映射，称为关联函数（当E为空集时，允许ϕ不存在）。例如，设G=,其中：V={v1,v2,v3}E={e1,e2,e3,e4,e5}ϕ(e1)=v1v3
typedefpairPII;boolst[1100];inth[11000000],ne[11000000],w[11000000],e[11000000],idx;intdist[50][50];classSolution{public:voidadd(inta,intb,intc){e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;}voidheap_dijkstra(intindex,intstart){dist[index][start]=0;priority_queue,greater>heap;heap.push({0,start});while
第一章知识点图的定义、关联、相邻、重边、环、孤立点、简单图同顶点的度d(v),deg(v)、出度、入度、最大度D、最小度d、奇点、偶点、邻域、悬挂点、悬挂边独立集偶图/二部图/二分图、多部图、完全偶图、完全图、正则图度序列、图序列（简单图的度序列）握手定理子图、极大子图、极小子图、生成子图、导出子图、边导出子图补图、自补图联图、线图途径、迹、路、最短路、最长路、Hamilton路、距离、半径、直径连通、连通图、连通分支、分支数边割/割集赋权图可达、双向连通/强连通、单向连通、弱连通、双向分支/强连通分支竞赛图闭途径、闭迹、圈、奇圈、偶圈、k-圈、最长圈、Hamilton圈围长、周长关联矩阵、邻
2023/12/14日修改：①Graph类的addEdge函数中存在BUG，在Insert的时候会传入了vertices，这会导致在查找哈希表中的节点时，会返回和数组连接的链表的第一个元素的地址②Graph类的deleteEdge函数中存在BUG，在Delete的时候传入了vertices，这会导致删除和数组连接的链表的第一个元素的地址③在HashTable::Delete函数中存在BUG，当判定时第一个节点时，少加了一个return，这会导致当找到的是第一个节点时，还会循环遍历到结尾，并且输出删除失败 在实现图的增加，删除和打印的过程中，寻找当前顶点的索引会花费大量的时
《图论与网络优化》学习笔记（第1-5章）上课时间：2023年10月——2024年1月上课地点：国防科技大学授课老师：戴丽教材：戴丽.《图论与网络优化》注：部分笔记根据自己的理解进行改动，可能不是很严谨，但便于理解。第一章图论发展历史1.1图论的起源与发展1736年，Euler研究并解决了konigsberg七桥问题（格林森堡七桥问题）。20世纪图论经历了一场爆炸性的发展，1936年第一本图论著作《有限图和无限图理论》诞生。电网络中的图论有机化学中的图论四色问题1.2图论的现状与应用图论具有很高的实用价值，例如：地图导航、人物关系图、蛋白质网络图、无人机集群网络图等。第二章基本概念与运算2.1图
图的基本概念点（顶点）图上的一些点，每个点代表一个位置边连接两个点的线权重代表边的重要性，比如从家到学校和家到超市走的路的时间不同，这个时间就是权重邻接若两个点之间有一条边直接连接，则称这两个点邻接路径经过一系列点和边的路线连通在一个图中，能从任意一个点到达其他任意一个点若要形成连通图，n个顶点最少需要n-1条边邻接矩阵表示法若有n个点，则矩阵为n行n列若a到b有直接连接的边，则矩阵第a行第b列为1否则为0邻接表表示法在图中的每个点都有一个列表，列表里记录了该点能直接相连的所有点比邻接矩阵更省空间图的储存特点空间效率：邻接矩阵：如果图中的点很多，但每个点的连接不多，那么邻接矩阵会占用很多空间，
拓扑序列算法主要内容一、基本思路1、概念定义入度：对一个节点而言，有多少条边指向自己。出度：对一个节点而言，有多少条边指向外面。二、拓扑序列模板三、例题题解一、基本思路1、概念定义拓扑序列定义：若一个由图中所有点构成的序列A满足：对于图中的每条边(x,y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。人话：始终满足每条边的起点在终点前面，从前指向后。注意：如果在有向图中构成一个环，则必定无法构成拓扑结构，也可以证明有向无环图一定存在拓扑序列，即有向无环图=拓扑图入度：对一个节点而言，有多少条边指向自己。出度：对一个节点而言，有多少条边指向外面。二、拓扑序列模板因为拓扑序列都是从前指向后
第1关：图的概念5阶无向完全图的边数为：10设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是：n(k+1)-2m若一个图有5个顶点，8条边，则该图所有顶点的度数和为多少？16第2关：图的表示他让输出关联矩阵和邻接矩阵这不简单么？#coding=utf-8importsympyassym#使用关联矩阵A1表示图1。#*****Begin*****#A1=sym.Matrix([[1,0,0,1,0],[1,1,0,0,1],[0,1,1,0,0],[0,0,1,1,1]])print("""⎡10010⎤⎢⎥⎢11001⎥⎢⎥⎢01100⎥⎢⎥⎣0011
替换子串得到平衡字符串题目描述有一个只含有‘Q’,‘W’,‘E’,‘R’四种字符，且长度为n的字符串。假如在该字符串中，这四个字符都恰好出现n/4次，那么它就是一个「平衡字符串」。给你一个这样的字符串s，请通过「替换一个子串」的方式，使原字符串s变成一个「平衡字符串」。你可以用和「待替换子串」长度相同的任何其他字符串来完成替换。请返回待替换子串的最小可能长度。如果原字符串自身就是一个平衡字符串，则返回0。样例样例输入s=“QWER”s=“QQWE”s=“QQQW”s=“QQQQ”样例输出0s已经是平衡的了。1我们需要把一个‘Q’替换成‘R’，这样得到的“RQWE”(或“QRWE”)是平衡的。2
一、图的相关概念图（graph）是一个二元组G=（V（G），E（G））。其中V（G）是非空集，称为点集；对于V中的每个元素可称其为顶点或节点，简称点。E（G）为V（G）各节点之间边的集合，称为边集。图是由若干点以及连接点与点的边构成的，常用G=（V，E）表示图。当V，E都是有限集合时，称G为有限图当V或者E是无限集合时，称G为无限图图有很多种，包括无向图，有向图，混合图等。若G为无向图，则E中的每个元素为一个无序二元组（u，v）u，v∈V，称作无向边，简称边。设e=（u，v），则u和v成为e的断点。若G为有向图，则E中的每一个元素为一个有序二元组（u，v），有时也写作u→v，称作有向边或者弧，
