/*
    Stewart, Garrett
    Benjamin, Michael
    Kakar, David

    February 12, 2020

    Lab 2
    CS A200
*/
#include <iostream>
#include <queue>
using namespace std;


void bfs(const string n[], const int matrix[][10], const string& name, const int numOfElem)
{
    queue<int> nameQueue;
    string traversal = "";

    int startVal;
    int nameLen = numOfElem;
    int visited[7] = { 0 };
    int i = 0;
    bool found = false;

    while (i < nameLen && !found)
    {
        if (name == n[i])
        {
            found = true;
            startVal = i;
            visited[i] = 2;
            traversal += n[i] + ", ";
        }
        i++;
    }

    if (!found)
        cout << "Name not found" << endl;
    else
    {
        do
        {
            for (int i = 0; i < nameLen; i++)
            {
                if (matrix[startVal][i] == 1 && visited[i] == 0)
                {
                    nameQueue.push(i);
                    visited[i] = 1;
                }
            }

            traversal += n[nameQueue.front()] + ", ";
            visited[nameQueue.front()] = 2;
            startVal = nameQueue.front();
            nameQueue.pop();

        } while (!nameQueue.empty());
    }
    cout << traversal;
}

int main()
{
    int numOfElem = 7;
    string names[10] = {"Bill", "Cinderella", "Jane", "Jill", "Martha", "Sean", "Susan"};
    int adjMatrix[10][10] = {0};

    //for (int i = 0; i < numOfElem; i++)
    //  cout << names[i] << " ";
    //Bill
    adjMatrix[0][2] = 1;
    adjMatrix[0][3] = 1;
    adjMatrix[0][5] = 1;
    //Cinderella
    adjMatrix[1][3] = 1;
    adjMatrix[1][4] = 1;
    adjMatrix[1][5] = 1;
    adjMatrix[1][6] = 1;
    //Jane
    adjMatrix[2][0] = 1;
    adjMatrix[2][4] = 1;
    adjMatrix[2][6] = 1;
    //Jill
    adjMatrix[3][0] = 1;
    adjMatrix[3][1] = 1;
    //Martha
    adjMatrix[4][1] = 1;
    adjMatrix[4][2] = 1;
    //Sean
    adjMatrix[5][0] = 1;
    adjMatrix[5][1] = 1;
    //Sean
    adjMatrix[6][1] = 1;
    adjMatrix[6][2] = 1;

    bfs(names, adjMatrix, "Susan", numOfElem);
    cout << endl;
    bfs(names, adjMatrix, "Bill", numOfElem);
    cout << endl;
    bfs(names, adjMatrix, "Cinderella", numOfElem);
    cout << endl;

}