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
一、图的相关概念图（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，称作有向边或者弧，
目录DAG求食物链数DAG求路径长度和路经总和题目：最大食物链解法一： 解法二：记忆化题目：游走思路： 题目：最大食物链 解法一：topo排序 我们标记f[i]是被f[x]捕食的点对应的类食物链数不难得出：f[x]=∑(f[i]) 首先从生产者开始，每去掉一个被捕食的点，那么相邻捕食者就要加上去掉点的类食物链数，但是我们还需要找到出度为0的消费者。所以这道题，我们要同时记录入度，还有出度（其实单纯的topo排序就用不上出度，记录出度是为了找食物链结尾的个数） #includeusingn
概论图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年,凯莱在计数烷CnH2n+2的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈、近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、运筹学，生物遗传学、心理学、经济学、社会学等学科中。图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直
