How to traverse a graph with algorihtm

Question

Need to find how many translators need for two persons to be able talking to each other.

Given values are

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

And the translators which we are looking for are as below

B > E Can translate directly, answer : 0
A > B Can't translate, answer : -1
C > F Need 2 translators C (5)> D(6)> E(8)> F(8), answer : 2
D > F need 1 translator D (6)> E(8)> F(8), answer : 1

And the code written is as below but I don't know how to traverse. Down is the graph picture which the nodes are basically A to F and matched them having same number.

#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;
}

Obligatory `graph = new vector[n+1];` This is not C++. [See](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard). ` — n. m. could be an AI, Jun 27 '22 at 15:30
@n.1.8e9-where's-my-sharem. not that I advocate such usage, but I think `graph = new vector[n+1];` is valid C++. It's not a VLA. It's an array of vectors allocated on the heap. Anyway it would be better to replace with `vector> graph`. — wohlstad, Jun 27 '22 at 15:56
@wohlstad I didn't see the edit when I started to write my comment. — n. m. could be an AI, Jun 27 '22 at 16:05
Generally, algorithms are not language-dependent. So, which part is giving you problems, the algorithm or the implementation? Please be specific with the problems (which are unclear) and for code, provide a [mcve] (looks like you got that point right). Also, please don't use images of text, just copy'n'paste the text. That said, concerning the traversal, there is depth-first and breadth-first, do you know these two? — Ulrich Eckhardt, Jun 27 '22 at 16:21
@Ulrich Eckhardt both and yes DFS with stack or recursive and BFS with queue vut I dont know which one is better used here as someone commented before I think it's a one dimensiomal traversing — Game_dev, Jun 27 '22 at 16:27
What does the path through the graph represent? Shortest way, all-node-roundtrip, minimum spanning tree etc? Using that abstract description, you can research different algorithms. This is crucial but that info is entirely missing from your question. Also, what does an edge represent? What does a node represent? What are additional properties of those entities? That's nowhere described in your question! — Ulrich Eckhardt, Jun 27 '22 at 16:50

score 1 · Accepted Answer · answered Jun 27 '22 at 16:08

1

I think your graph construction is wrong, it's not really a graph at all. You need to do some work to translate the input into a proper graph.

In your code you've created a mapping from language (1, 2, 3 etc) to translators (A, B, C etc) but really the problem is asking for a mapping from translators to translators (that speak the same language). So your graph should look like this

A -> 
B -> D E F
C -> D
D -> B C E
E -> B D F
F -> B E

Once you have a graph that connects translators I think you'll find it much easier to traverse. The languages themselves don't matter, all that matters is which translators speak a common language. That's what your graph should show.

answered Jun 27 '22 at 16:08

john

85,011
4
57
81

So basically I need to make it as an adjacent lists instead of double dimensional array? – Game_dev Jun 27 '22 at 16:20
@Game_dev Either adjacency lists or a 2D array is possible (they are equivalent after all). But the point with either data structure is that you are making a graph which connects translators, not a mapping from language to translator. – john Jun 27 '22 at 17:06

How to traverse a graph with algorihtm

1 Answers1