北邮复试_2019_树的某两个节点的最短路径（广度优先算法）_求解树两个叶子节点最短路径

广度优先算法

最短路径

3 浏览量更新于2023-05-04 收藏 27KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

北邮复试北邮复试_2019_树的某两个节点的最短路径（广度优先算法）树的某两个节点的最短路径（广度优先算法）

题目描述题目描述

题目描述

对二叉树，计算任意两个结点的最短路径长度。

输入

第一行输入测试数据组数T

第二行输入n,m 。n代表结点的个数，m代表要查询的数据组数

接下来n行，每行输入两个数，代表1~n结点的孩子结点，如果没有孩子结点则输入-1.根节点为1.

接下来m行，每行输入两个数，代表要查询的两个结点

输出

每组测试数据输出m行，代表查询的两个结点之间的最短路径长度

测试样例

输入

8 4

2 3

4 5

6 -1

-1 -1

-1 7

-1 -1

8 -1

-1 -1

1 6

4 6

4 5

8 1

输出

void short_tree_path() //最短路径（广度优先遍历）

{

int n;

cin >> n;

for (int i = 0; i > vernums;

cin >> testnums;

vector visit(vernums, false);

vector<vector> edge(vernums, vector(vernums, -1));

int left, right;

for (int i = 0; i > left;

cin >> right;

if (left != -1)

{

edge[i][left - 1] = 1;

edge[left-1][i] = 1;

}

if (right != -1)

{

edge[i][right - 1] = 1;

edge[right - 1][i] = 1;

}

vector<vector> test(testnums,vector(2,0));

for (int i = 0; i > left;

cin >> right;

test[i][0] = left - 1;

test[i][1] = right - 1;

}

vectorres(testnums,0);

for (int i = 0; i < testnums; i++)

{

visit = vector(vernums, false);

vector pathlong(vernums, 0);

int start = test[i][0];

int end = test[i][1];

visit[start] = true;

queue m_queue;

m_queue.push(start);

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

weixin_38723691

粉丝: 3
资源: 941

会员权益专享

北邮复试_2019_树的某两个节点的最短路径（广度优先算法）

寻找树中两叶子节点之间的最长路径

Dijkstra最短路径与二叉树算法

北邮复试三道上机题

北邮复试（机试题目和笔试题库）.zip

北邮2019复试课件.rar

北邮复试笔试题目集合.rar

计算机考研复试面试常问问题 数据结构篇.pdf

数据结构与算法复试面试题

数据结构与算法 复试免试提问

有关svm算法机器学习复试问题

研究生复试会问哪些算法分析的问题及其清晰回答

华南理工2018考研复试c++上机

研究生复试算法分析会问到的问题及回答

考研复试，数据结构常见问题

研究生复试会问的算法分析问题及回答

中科大复试c上机回忆版

大连理工887数据结构考研复试提问

江苏科技大学计算机科学与技术专业，考研复试科目数据库系统概论2019年真题

csdn数据结构复试

会员权益专享

最新资源

计算机考研复试面试常问问题数据结构篇.pdf

数据结构与算法复试免试提问