基于图遍历算法计算两人交流所需翻译人数的C++实现问题

计算规则 #

需求为计算两人实现正常交流所需配备的翻译人员数量，规则如下：

• 若两人掌握共同语言则可直接交流，否则需通过掌握共同语言的翻译中转
• 连通路径中除对话双方外的节点数即为所需翻译人数
• 无连通路径时返回-1

人员-语言对应关系 #

A : 1 2
B : 7 8
C : 4 5
D : 5 6 7
E : 6 7 8
F : 8 9

预期计算结果 #

B > E 可直接翻译，结果 : 0
A > B 无法连通翻译，结果 : -1
C > F 需要2名翻译，路径为C (5)> D(6)> E(8)> F(8)，结果 : 2
D > F 需要1名翻译，路径为D (6)> E(8)> F(8)，结果 : 1

现有实现说明 #

• 已完成逻辑：基于共同语言关联人员节点的图初始化
• 待补全逻辑：正确的图遍历实现，用于计算两点间最短路径长度
• 图结构规则：以A-F为人员节点，共同掌握同一种语言的节点间存在连通关系
• 连通关系示意图：
  

未完成的C++代码 #

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

#define SIZE 1000
vector<char>* graph;
vector<int> v;
bool vis[SIZE]{ 0 };
int n = 9;

int Search(int start, char ch1, char ch2)
{
    int count = 0;
    queue<char> v1, v2;
    v1.push(ch1); v2.push(ch2);
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < graph[i].size(); j++)
        {
            auto begin = graph[i].begin(), end = graph[i].end();
            auto iter1 = find(begin, end, v1.front()); 
            auto iter2 = find(begin, end, v2.front());
            auto lang = graph[i][j];
            if (iter1 != end &&
                lang != v1.front())
                v1.push(lang);

            if (iter2 != end &&
                lang != v2.front())
                v2.push(lang);

            
        }
    }
    fill(vis, vis + SIZE, false);
    return count;
}

int main()
{
    graph = new vector<char>[n+1];
    vector<string> people{ { "A 1 2" }, { "B 7 8" }, { "C 4 5" }, { "D 5 6 7" }, { "E 6 7 8" }, { "F 8 9" } };
    vector<string> pairs{ {"B E"}, {"A B"}, {"C F"}, {"D F"} };
    vector<int> res;
    for (int i = 1; i <= n; i++)
    {
        for (auto item : people)
        {
            item.erase(remove(item.begin(), item.end(), ' '), item.end());
            for (int j = 1; j < item.size(); j++)
            {
                int idx = item[j] - '0';
                if(i==idx)
                    graph[i].push_back(item[0]);
            }
        }
    }
    for (auto item : pairs)
    {
        item.erase(remove(item.begin(), item.end(), ' '), item.end());
        int count = Search(1, item[0], item[1]);
        cout << count << endl;
    }
    delete[] graph;
}

内容的提问来源于stack exchange，提问作者Game_dev