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

Elsa ·

更新时间:2024-09-21

· 784 次阅读

题目描述

题目描述
对二叉树，计算任意两个结点的最短路径长度。
输入
第一行输入测试数据组数T
第二行输入n,m 。n代表结点的个数，m代表要查询的数据组数
接下来n行，每行输入两个数，代表1~n结点的孩子结点，如果没有孩子结点则输入-1.根节点为1.
接下来m行，每行输入两个数，代表要查询的两个结点
输出
每组测试数据输出m行，代表查询的两个结点之间的最短路径长度

测试样例
输入
1
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
输出
2
4
2
4

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);
                bool flag = false;
                while (!m_queue.empty()&&!flag)
                {
                    int p = m_queue.front();
                    m_queue.pop();         
                    for (int i = 0; i < vernums; i++)
                    {
                        if (edge[p][i] == 1 && visit[i] == false)
                        {
                            m_queue.push(i);
                            visit[i] = true;
                            pathlong[i] = pathlong[p] + 1;
                            if (i == end)
                            {
                                flag = true;
                            }
                        }
                    }
                }
                res[i] = pathlong[end];
            }
            for (int i = 0; i < testnums; i++)
            {
                cout << res[i] << endl;
            }
        }
    }

作者：luncy_yuan

广度优先算法最短路径算法

1024 个赞