当前位置：文档之家 › 北航数据结构

北航数据结构

  • 格式：pdf
  • 大小：237.39 KB
  • 文档页数：6

下载文档原格式

  / 6

合集下载

北航考研991考试大纲

北航考研991考试大纲

991数据结构与C语言程序设计考试大纲（2013版）2013年《数据结构与C语言程序设计》考试内容包括“数据结构”与“C语言程序设计”两门课程的内容，各占比例50%，试卷满分为150分。

《数据结构》部分指定参考书：《数据结构教程（第二版）》唐发根编著北京航空航天大学出版社一、概述1．数据的逻辑结构与存储结构的基本概念；2．算法的定义、基本性质以及算法分析的基本概念，包括采用大 形式表示时间复杂度和空间复杂度。

二、线性表1．线性关系、线性表的定义，线性表的基本操作；2．线性表的顺序存储结构与链式存储结构(包括单(向)链表、循环链表和双向链表)的构造原理；3．在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计(含递归算法的设计)。

三、堆栈与队列1．堆栈与队列的基本概念与基本操作；2．堆栈与队列的顺序存储结构与链式存储结构的构造原理；3．在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计；4．堆栈和队列在解决实际问题中应用。

四、树与二叉树1．树与二叉树的基本概念，基本特征、名词术语；2．完全二叉树与满二叉树的基本概念，二叉树的基本性质；3．二叉树与树、树林之间的转换；4．二叉树的顺序存储结构与二叉链表存储结构；5．二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，以及在二叉链表基础上各种遍历算法(重点为非递归算法)的设计与应用；6．二叉排序树的基本概念、建立(插入)、查找与平均查找长度ASL的计算；7．哈夫曼(Huffman)树的基本概念，哈夫曼树的构造与带权路径长度(WPL)的计算。

五、图1．图的基本概念、名词术语；2．图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点；3．图的深度优先搜索与广度优先搜索；4．最小(代价)生成树、最短路径、AOV网与拓扑排序以及AOE网与关键路径的基本概念与求解过程。

北航数据结构试题及答案

北航数据结构试题及答案

北航数据结构试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用什么数据结构来实现？A. 链表B. 栈C. 数组D. 树答案：C2. 下列关于二叉树的描述中，错误的是：A. 二叉树的第i层最多有2^(i-1)个节点B. 任意非空二叉树的叶子节点数等于度为2的节点数加1C. 任意非空二叉树的叶子节点数等于度为2的节点数减1D. 任意非空二叉树的叶子节点数等于度为2的节点数答案：C3. 在图的遍历算法中，深度优先搜索（DFS）使用的数据结构是：A. 队列B. 栈C. 链表D. 数组答案：B4. 哈希表的冲突解决方法不包括以下哪种？A. 开放定址法B. 链地址法C. 再散列法D. 排序法答案：D5. 快速排序算法的时间复杂度最坏情况下为：A. O(nlogn)B. O(n^2)C. O(n)D. O(1)答案：B6. 以下排序算法中，时间复杂度为O(nlogn)的是：A. 冒泡排序B. 快速排序C. 选择排序D. 插入排序答案：B7. 以下关于堆的描述中，正确的是：A. 堆是一种特殊的二叉树B. 堆是一种完全二叉树C. 堆是一种平衡二叉树D. 堆是一种链表答案：A8. 在一个长度为n的有序数组中查找一个元素，使用二分查找算法的时间复杂度是：A. O(n)B. O(nlogn)C. O(logn)D. O(1)答案：C9. 以下算法中，不属于动态数据结构的是：A. 链表B. 栈C. 数组D. 哈希表答案：C10. 以下关于图的描述中，错误的是：A. 图是由顶点和边组成的B. 图的顶点可以有0个或多个C. 图的边可以有向或无向D. 图的顶点数一定大于边数答案：D二、多项选择题（每题3分，共15分）1. 下列哪些是线性表的存储结构？A. 顺序存储B. 链式存储C. 索引存储D. 散列存储答案：A, B2. 在图的表示方法中，以下哪些是正确的？A. 邻接矩阵B. 邻接表C. 边表D. 顶点表答案：A, B, C3. 下列哪些排序算法是稳定的？A. 冒泡排序B. 快速排序C. 插入排序D. 选择排序答案：A, C4. 在数据结构中，以下哪些是递归算法的特点？A. 问题可以分解为更小的子问题B. 每个子问题都是原问题的实例C. 存在递归终止条件D. 递归算法的时间复杂度一定比迭代算法高答案：A, B, C5. 在使用链表实现栈时，以下哪些操作是合法的？A. pushB. popC. peekD. clear答案：A, B, C三、简答题（每题5分，共30分）1. 请简述什么是递归，并给出一个递归算法的例子。

北航软件工程基础复习

北航软件工程基础复习

软件工程技术基础复习指南一．数据结构1.术语：1.数据；2.数据元素；3数据结构；4.结构2.数据结构定义：就是具有结构的数据元素的集合。

3.算法的定义：用来解决某个特定课题的指令的集合。

4.算法的性质：输入、输出、有穷性、确定性、有效性5.算法描述：自然语言、程序流程图、具体程序语言6.算法分析：指对算法质量优劣的评价。

（时间复杂度、空间复杂度、可读性、可移植性、易测试性）7.时间复杂度：依据算法编写的程序在计算机中运行时间多少的度量（关键语句之行的次数）O（n）；（O(log2n)（二分检索）<O(n)（比较两个具有n个字符串）<O(nlog2n)<O(n2)<O(n3)（常规矩阵乘）<O(2n)<O(n!)）；O（1）：访问数组中的元素是常数时间操作8.空间复杂度：依据算法编写的程序在计算机中占存储空间多少的度量9.频度统计法：以语句执行的次数的多少作为算法的时间量度的分析方法10.语句的频度：语句被执行的次数11.算法的频度：算法中所有语句的频度之和12.数组：下标与值组成的偶对的有穷集合13.二维数组的存储结构：行序为主序分配方式、列序为主序分配方式、14.特殊矩阵的压缩存储：对称矩阵、对角矩阵、15.线性表：数据元素之间具有的逻辑关系为线性关系的数据元素集合16.线性表的基本操作：创建、索引、存入、插入、删除、排序、17.线性表顺序存储结构：用一组地址连续的存储单元依次存储线性表的数据元素，数据元素之间的逻辑关系通过数据元素的存储位置直接反映18.顺序存储结构优点：原理简单、元素存储地址可用简单解析式计算、存储空间开销小19.顺序存储结构缺点：需事先分配连续地址、基本操作时间效率低20.线性链表：用一组地址任意的存储单元(连续的或不连续的)依次存储表中各个数据元素,数据元素之间的逻辑关系通过间接地反映出来21.链式存储结构优点：存储空间动态分布、地址不连续、插入删除操作效率高（O(1)）22.链式存储结构缺点：存储密度小、查找定位效率低O(n)23.堆栈定义：是一种只允许在表的一端进行插入操作和删除操作的线性表。

15秋北航《算法与数据结构》在线作业二100分答案

15秋北航《算法与数据结构》在线作业二100分答案

北航《算法与数据结构》在线作业二单选题一、单选题（共25 道试题，共100 分。

）1. 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作A. 条件判断B. 结点移动C. 算术表达式D. 赋值语句-----------------选择：B2. 在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。

A. HL=p;p->next=HL;B. p->next=HL;HL=p;C. p->next=HL;p=HL;D. p->next=HL->next;HL->next=p;-----------------选择：B3. 线性表是一个具有n个（）的有限序列。

A. 表元素B. 字符C. 数据元素D. 数据项-----------------选择：C4. 若给定的关键字集合为{20，15，14，18，21，36，40，10}，一趟快速排序结束时，键值的排列为( )。

A. 10，15，14，18，20，36，40，21B. 10，15，14，18，20，40，36，21C. 10，15，14，20，18，40，36，21D. 15，10，14，18，20，36，40，21-----------------选择：A5. 按照二叉树的定义，具有3个结点的二叉树有（）种。

A. 3B. 4C. 5D. 6-----------------选择：C6. 下列有关图遍历的说法中不正确的是（）。

A. 连通图的深度优先搜索是个递增过程B. 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C. 非连通图不能用深度优先搜索法D. 图的遍历要求每个顶点仅被访问一次-----------------选择：C7. Substr('DATA STRUCTURE'，5，9)=（）。

A. STRUCTURE'B. 'ASTUCTUR'C. 'DATA STRUCTRUE'。

数据结构北航软件技术基础课程ppt

数据结构北航软件技术基础课程ppt

eMail:gaoliansheng@
2020/9/23
liansheng_gao@
软件技术基础
• 第零章 编程的一些问题 • 第五章 二叉树和树
• 第一章 绪 论
• 第六章 图和广义表
• 第二章 线 性 表
• 第七章 排 序
• 第三章 栈和队列
• 第八章 查 找
试，通过测试用例保证每条源代码至少执行一次
2020/9/23
第零章 程序设计的一些问题
• 需求分析-Requ综 结i述 果re： ：m由 测e专 试n门 报t的 告A测n试a人ly员s对is软件进行测试
• 概要设计-Prim12ary测 测试 试D计e划sign
• 详细设计-Detaile条 wda件lDkt：her编osu译gihg、n链接成功，完成单元测试，
2020/9/23
第零章 程序设计的一些问题
• 软件和属性
– 计算机运行中不可缺少的 – 预先编好，能为他人使用 – 商品
• 盘和软件
– 盘是软件的载体
• 软件的分类
– 应用软件 – 系统软件
2020/9/23
第零章 程序设计的一些问题
• 程序设计的几个阶段(软件工程简介)
– 六、七十年代出现了软件危机
2020/9/23
数据元素
• 数据元素是数据的基本单位。 • 它也可以再由不可分割的数据项组成
2020/9/23
数据对象 性质相同的数据元素的集合 。
例：一个班级的成绩表可以看作一个数据对象。 一个图片、声音…..
数据对象是性质相同的数据元素集合。
2020/9/23
数据结构
• 数据元素集合（也可称数据对象） • 各元素之间的关系，即结构。

北航数据结构与程序设计真题2013年北航991真题及答案

北航数据结构与程序设计真题2013年北航991真题及答案

2013年''数据结构与C程序设计〃（代码991）试题一、单项选择题（本题共20分，每小题各2分）1.对于长度为n的线性表，建立其对应的収链表的时间复朵度为（）。

A.0（1）： B・ O（log2n）：・ O（n）： D・ O（n2）n2.一般情况下，在一个双向链表中插入一个新的链结点，（）。

A.需耍修改4个抬针域内的指针：B・需要修改3个指针域内的抬针：C.需要修改2个抬针域内的抬针：D.只需要修改1个指针域内的抬针。

3.假设用单个字母表示中缀表达式中的一个运算数（或称运算对彖）.并利用堆栈产生中缀表达式对应的后缀表达式。

对于中缀表达式A+B^C/D-E）,十从左至右扫描到运算数E时，堆栈中的运算符依次是（）。

（注：不包含表达式的分界符）A.+*/-：B. +*（/-： C・ +*-：・ +*（-o4.若某二叉排序树的前序遍历序列为50,20,40,30,80,60,70,则后序遍历序列为（）。

A. 30,40,20,50,70,60,80：B. 30,40,20,70,60,80,50：C. 70,60,80,50,30,40,20：D. 70,60,80,30,40,20,50.5.分别以6, 3, 8, 12, 5, 7对应叶结点的权值构造的哈夫曼（Huffman）树的深度为（）。

A. 6： B・ 5： C・ 4： D・ 3。

&下列关于图的叙述中，错误的是（）0A.根据图的定义，图中至少有一个顶点：B.根据图的定义.图中至少有一个顶点和一条边（弧）：C.具有n个顶点的无向图最多有n&#61620;（n-l）/2条边:D.具有n个顶点的有向图最多有n&#61620;（n-l）条边（弧）。

7.若在有向图G的拓扑序列中.顶点W在顶点vj之前，则下列4种情形中不可能岀现的是（）。

A.G 中有弧vvi,vj＞：B.G 中没有3ft＜vi r vj＞；c. G中有一条从顶点W到顶点vj的路径：D・G中有一条从顶点vj到顶点vi的路径。

北航数据结构课件 (10)


（ 1，4，6 ， 12 8，8 12 ， 6，11，… ）
例
49
temp
temp＞K[j] j=0 38 97 76 65 13 27 50
… (若干趟后)
K[j+1]=K[ j ]； j=j−1；
65
38
49
76 65
76 97
65 97
13
27
50
K[j+1]=temp;
38
49
65
76
97
核心思想
首先确定一个元素的间隔数gap。 将参加排序的元素按照gap分隔成若干个子序列 ( 即分别把那些位置相隔为gap的元素看作一个子序 列),然后对各个子序列采用 某一种排序方法 进行排 序；此后减小gap值，重复上述过程，直到gap<1。
一种减小gap的方法：
gap1 = n/2 gapi = gapi-1/2
1.时间性能 —— 排序过程中元素之间的比较次数与元素的
移动次数。 本章讨论各种排序方法的时间复杂度 时主要按照最差情况下所需要的比较次数 来进行。
2.空间性能 —— 除了存放参加排序的元素之外，排序过程
中所需要的其他辅助空间。
3.排序稳定性 —— 对于值相同的两个元素，排序前后的先后
次序不变，则称该方法为稳定性排序方法， 否则，称为非稳定性排序方法。
算 法
泡排序法的排序趟数与原始序列中数 据元素的排列有关，因此，排序的趟数为 一个范围，即[1..n-1]。
什么情况下至少排序一趟 什么情况下要排序n-1趟
O(n
2)
结论
泡排序方法比较适合于 参加排序的序列的原始状态 基本有序的情况
泡排序法是 稳定性排序方法。

北京航空航天大学991数据结构与C语言程序设计历年考研真题专业课考试试题


2017年北京航空航天大学991数据 结构与C语言程序设计考研真题
2018年北京航空航天大学991数据 结构与C语言程序设计考研真题
目 录
2010年北京航空航天大学993数据结构与C语言程序设计考研真题 2011年北京航空航天大学991数据结构与C语言程序设计考研真题 2012年北京航空航天大学991数据结构与C语言程序设计考研真题 2013年北京航空航天大学991数据结构与C语言程序设计考研真题 2014年北京航空航天大学991数据结构与C语言程序设计考研真题 2015年北京航空航天大学991数据结构与C语言程序设计考研真题 2016年北京航空航天大学991数据结构与C语言程序设计考研真题 2017年北京航空航天大学991数据结构与C语言程序设计考研真题 2018年北京航空航天大学991数据结构与C语言程序设计考研真题
2014年北京航空航天大学991数据 结构与C语言程序设计考研真题
2015年北京航空航天大学991数据 结构与C语言程序设计考研真题
2016年北京航空航天大学991数据 结构与C语言程序设计考研真题
2010年北京航空航天大学993数据 结构与C语言程序设计考研真题
2011年北京航空航天大学991数据 结构与C语言程序设数据 结构与C语言程序设计考研真题
2013年北京航空航天大学991数据 结构与C语言程序设计考研真题

北航数据结构课件第一章

祝同学们新学期愉快学习进步！课程名称：数据结构教材名称：《数据结构教程》唐发根刘又诚编著北京航空航天大学出版社1996《数据结构》唐发根编著科学出版社1998开设本课程的必要性以及课程的特点：1. 计算机专业重要的专业基础课之一.2. 需要有关“程序设计语言”和“离散数学”的知识作为课程的基础.3. 实践性较强.第一章绪论1.1 什么是数据结构描述客观事物的数字、字符以及一切能够输入到计算机中，并且能够被计算机程序处理的符号的集合。

数据这个集合中的一个一个元素。

具有相同特性的数据元素的集合。

数据元素之间具有的关系(联系)。

数据数据元素数据对象结构一. 名词术语二. 数据结构的定义1.数据元素之间的联系称之为结构，数据结构就是具有结构的数据元素的集合。

2. 数据结构是一个二元组Data-Structure=(D，R)其中，D是数据元素的有限集合，R是D上的关系的集合。

数据元素之间具有的逻辑关系(结构)。

线性关系(线性结构)如线性表、数组、堆栈、队列、串、文件等具有某种逻辑结构的数据在计算机存储器中的存储方式(存储映象)。

物理结构也被称为存储结构。

顺序存储结构链式存储结构用一组地址连续的存储单元依次存放数据元素，数据元素之间的逻辑关系通过元素的地址直接反映。

用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑关系通过指针间接地反映。

非线性关系(非线性结构)如树、二叉树、图等物理结构逻辑结构例刘晓光马广生王民…张玉华男男…女男汉回壮…汉161721…25……………姓名性别民族年龄其他逻辑结构：线性结构(线性表)a 1a 2a 3 a 30…d 1d 2 d 3d 4…d 30a 2a 1a 3a 4a 30存储结构:1. 顺序存储结构:2. 链式存储结构:…d 1d 2 d 3d 4a 1a 2a 3a 30∧list…a 2a 1a 4a 3d 4d 1d 5d31.研究数据元素之间的客观联系。

北航计算机考研科目

北航（北京航空航天大学）计算机考研科目包含以下内容，具体要求可能会有一定的变化，建议在报名前查阅北航的招生信息和考试大纲，以获取最新的考试科目和要求。

1.计算机组成原理：涉及计算机硬件系统的结构和功能，包括数字逻辑、处理器设计、存储器层次结构、输入输出系统等。

2.操作系统：重点学习操作系统的基本原理、进程管理、内存管理、文件系统、设备管理、死锁处理等。

3.数据结构与算法：包括常见数据结构（如数组、链表、栈、队列、树、图等）的基本概念、实现方式和常用算法（如排序、查找、图算法等）的设计与分析。

4.计算机网络：涵盖计算机网络的基本概念、协议体系结构、局域网与广域网技术、传输层协议（如TCP和UDP）、网络安全等。

5.数据库系统：学习数据库的基本概念、关系数据库理论、SQL语言、数据库设计与管理、事务处理与并发控制、数据仓库与数据挖掘等。

6.软件工程：重点涉及软件开发过程、需求分析与建模、软件设计原则与方法、软件测试与质量保证、软件项目管理等。

此外，北航计算机考研还可能包括一些选修科目，如人工智能、机器学习、图像处理、编译原理等。

在备考过程中，您可以参考相关教材和资料，系统学习每个科目的基本概念、原理和应用。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
在集合 U 中放入顶点 v0，v0 到 v0 的距离为 0。 对 V-U 里的每个顶点 v，如果（v0, v）在 E 中（即存在直接的边），则到 v 的已知最短 路径长度设为 w(v0, v), 否则令 v 的已知最短路径长度为 inf。这里的 w(v0, v)是从 v0 到 v 的 边的权值。 反复做： 从 V-U 中选出当时已知最短路径长度最小的顶点 v(min)加入 U，因为这时到 v(min)的 已知最短路径长度 cdis(v0, v(min))就是 v0 到 v(min)的距离。 由于 v(min)的加入，V-U 中某些顶点的已知最短路径可能改变。如果从 v0 经过 v(min) 到 v'的路径比原来已知的最短路径更短，就说明发现了到 v'的新的已知最短路径（及其长 度），该路径经过 v(min)到 v'。在这种情况下更新到 v'的已知最短路径及距离的记录，保证 下面能正确地继续从 V-U 中选择顶点。 反复选择顶点并更新到所有非 U 顶点的最短路径信息，知道从 v0 可达的所有顶点都在集合 U 中为止。如果这时还存在未加入 U 的顶点，就说明被处理的图不连通。
如果这样做不能得到一个包含 G 的所有顶点的连通分量，则原图不连通，没有最小 生成树。算法做出的是 G 的最小连通树林。 rim 算法 从图 G 的顶点集 V 中任取一顶点（例如 v0）放入集合 U 中，这时 U={v0}，令边集合 Er={}， 显然 T=（U，Er）是一棵树（只包含一个顶点且没有边）。
三、算法的设计与实现
Kruskal 算法
设 G=（V，E）是一个网络，其中 IVI=n。 1）初始时取包含 G 中所有 n 个顶点但没有任何边的孤立点子图 T=（V，{}），T 里的每个顶 点自成一个连通分量。下面将通过不断扩充 T 的方式构造 G 的最小生成树。 2）将边集 E 中的边按权值递增的顺序排序，在构造中的每一步顺序地检查这个边序列，找 到下一条（最短的）两端点位于 T 的两个不同连通分量的边 e，把 e 加入 T。这导致两个连 通分量由于边 e 的连接而变成了一个连通分量。 3）每次操作使 T 减少一个连通分量。不断重复这个动作加入新边，直到 T 中所有顶点都包 含在一个连通分量里为止，这个连通分量就是 G 的一棵最小生成树。
p=end l=0 while p>=1 and l<nodes:
road[l]=p p=nodepre[p] l+=1 l-=1 while l>=0: roads.append(road[l]) l-=1 return dis[end],roads def map():
map=[[inf,inf,inf,inf,inf,inf],[inf,inf,inf,6,3,inf,inf,inf],[inf,11, inf,4,inf,inf,7,inf],
return res def prim(self):
res=[] snode=[0] cnode=[i for i in range(1,self.nodenumber)] while len(cnode)>0:
begin,end,min=0,0,99 for i in snode:
for j in cnode: if self.map[i][j]<min: min=self.map[i][j] begin=i
四、结果
Dijkstra
代码 1： class Graph():
def __init__(self,map): self.map=map self.nodenumber=self.nodenumber()
self.edgenumber=self.edgenumber() def nodenumber(self):
一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值 之和小于或者等于其它生成树的边的权值之和。广义上而言，对于非连通无向图来说，它的 每一连通分量同样有最小生成树，它们的并被称为最小生成森林。
二、数据结构-图
在数学上，一个图（Graph）是表示物件与物件之间的关系的方法，是图论的基本研究 对象。一个图看起来是由一些小圆点（称为顶点或结点）和连结这些圆点的直线或曲线（称 为边）组成的。如果给图的每条边规定一个方向，那么得到的图称为有向图，其边也称为有 向边。在有向图中，与一个节点相关联的边有出边和入边之分，而与一个有向边关联的两个 点也有始点和终点之分。相反，边没有方向的图称为无向图。
检查所有一个端点在集合 U 里而另一个端点在集合 V-U 的边，找出其中权最小的边 e=(u,v) （假设 u 在 U 中，v 在 V-U 中），将顶点 v 加入顶点集合 U，并将 e 加入边集合 Er。易见， 扩充之后的 T=（U，Er）仍是一棵树。 重复上面步骤直到 U=V（所构造的树已经包含了所有顶点）。这时集合 Er 里有 n-1 条边， 子图 T=（U，Er）就是 G 的一棵最小生成树。 Dijkstra 算法 初始：
if nodedis[j]==0 and dis[j]<minn: t=j minn=dis[j]
nodedis[t]=1 #找到最短的一条路径 ,标记 for j in range(nodes+1):
if nodedis[j]==0 and dis[j]>dis[t]+map[t][j]: dis[j]=dis[t]+map[t][j] nodepre[j]=t
实验报告-最小生成树
一、问题描述
最小生成树是一副连通加权无向图中一棵权值最小的生成树。在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即 ），而 w(u, v) 代表此边的权重，若存 在 T 为 E 的子集（即 ）且 (V, T) 为树，使的 w(T) 最小，则此 T 为 G 的最小生成树。 最小生成树其实是最小权重生成树的简称。
end=j res.append([begin,end,min]) snode.append(end) cnode.remove(end) for j in res: j[0]=chr(j[0]+97) j[1]=chr(j[1]+97) return res max=99 row1=[0,5,11,5,max,max,max] row2=[5,0,max,3,9,max,7] row3=[11,max,0,7,max,6,max] row4=[5,3,7,0,max,max,20] row5=[max,9,max,max,0,max,8] row6=[max,max,6,max,max,0,8] row7=[max,7,max,20,8,8,0] map=[row1,row2,row3,row4,row5,row6,row7] graph=Graph(map) print("kruskal") print(graph.kruskal()) print("prim") print(graph.prim()) 代码二： inf=float('inf') def Dijkstra(nodes,edges,graph,start,end): nodepre=[0]*(nodes+1) #记录前驱 nodedis=[0]*(nodes+1) #记录节点遍历状态 dis=[inf for i in range(nodes+1)] #保存最短距离 road=[0]*(nodes+1) #保存最短路径 roads=[] map=graph for i in range(nodes+1):#初始化起点到其他点的距离 if i==start: dis[i]=0 else: dis[i]=map[start][i] if map[start][i]!=inf: nodepre[i]=start else: nodepre[i]=-1 nodedis[start]=1 for i in range(nodes+1):#每循环一次确定一条最短路 minn=inf for j in range(nodes+1):#寻找当前最短路
一个不带权图中若两点不相邻，邻接矩阵相应位置为 0，对带权图（网），相应位置为 ∞。一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。在邻接表中，对图中每个顶 点建立一个单链表（并按建立的次序编号），第 i 个单链表中的结点表示依附于顶点 vi 的边 （对于有向图是以顶点 vi 为尾的弧）。每个结点由两个域组成：邻接点域（Adjvex），用以指 示与 vi 邻接的点在图中的位置，链域（Nextarc）用以指向依附于顶点 vi 的下一条边所对应 的结点。如果用邻接表存放网（带权图）的信息，则还需要在结点中增加一个存放权值的域 （Info）。每个顶点的单链表中结点的个数即为该顶点的出度（与该顶点连接的边的总数）。 无论是存储图或网，都需要在每个单链表前设一表头结点，这些表头结点的第一个域 data 用于存放结点 vi 的编号 i，第二个域 firstarc 用于指向链表中第一个结点。
return len(self.map) def edgenumber(self):
cnt=0 for i in range(self.nodenumber):
for j in range(i): if self.map[i][j]>0 and self.map[i][j]<99: cnt+=1
return cnt def kruskal(self):
for i in range(len(gp)): if edge[0] in gp[i]: m=i if edge[1] in gp[i]: n=i
if m!=n: res.append(edge) gp[m]=gp[m]+gp[n] gp[n] =[]
for j in res: j[0]=chr(j[0]+97) j[1]=chr(j[1]+97)