Graph

#include <iostream>
using namespace std;

const int MAX_SIZE = 20; // Максимален брой върхове в графа

// Структура за представяне на граф
struct Graph {
    int key; // Матрица на съседство
    Graph* next; // Брой върхове в графа
} *graphArray[MAX_SIZE];

// Функция за инициализация на графа
void initializeGraph() {

    for (int i = 0; i < MAX_SIZE; i++)
    {
        graphArray[i] = NULL;
    }
}

// Функция за добавяне на ребро в графа
void addEdge(int u, int v) {

    for (int i = 0; i < MAX_SIZE; i++)
    {
        if (graphArray[i]->key == u)
        {

            Graph* p = new Graph;

            p->key = v;

            p->next = graphArray[i]->next;

            graphArray[i]->next = p;

            break;
        }
    }
}

int isVisited(int key)
{
    for (int i = 0; i < MAX_SIZE; i++)
    {
        if (graphArray[i])
        {
            if (graphArray[i]->key == key)
            {

                return i;


            }


        }
    }

}

// Функция за показване на графа
void display() {

    int viseted[MAX_SIZE] = { 0 };

    for (int i = 0; i < MAX_SIZE; i++)
    {
        if (graphArray[i] && viseted[i] == 0)
        {

            cout << graphArray[i]->key << " ";

            Graph* p = graphArray[i];

            if (p->next)
            {
                p = p->next;

                while (p)
                {

                    int index = isVisited(p->key);


                    if (viseted[index] == 0 && index != i)
                    {
                        cout << graphArray[index]->key << " ";

                        viseted[index] = 1;

                        viseted[i] = 1;
                    }


                    p = p->next;

                }
            }

            viseted[i] = 1;


        }
    }


}


bool searchNode(int key)
{

    for (int i = 0; i < MAX_SIZE; i++)
    {
        if (graphArray[i])
        {

            if (graphArray[i]->key == key)
            {
                return true;
            }
        }
    }


    return false;
}

bool searchEdge(int u, int v)
{
    unsigned int fEmpty = 0;

    for (int i = 0; i < MAX_SIZE; i++)
    {
        if (graphArray[i])
        {


            if (graphArray[i]->key == u)
            {
                Graph* p = graphArray[i];

                p = p->next;

                while (p)
                {
                    if (p->key == v)
                    {
                        return true;
                    }
                    p = p->next;

                }
            }
        }
    }

    return false;
}

void addNode(int key)
{
    unsigned int fEmpty = 0;

    for (int i = 0; i < MAX_SIZE; i++)
    {
        if (graphArray[i] == NULL)
        {
            fEmpty = i;
            break;
        }
    }

    Graph* newNode = new Graph;


    newNode->key = key;

    newNode->next = NULL;

    graphArray[fEmpty] = newNode;


}


// Функция за намиране на изолирани върхове в графа
void findIsolatedVertices() {

    bool isFound = false;

    for (int i = 0; i < MAX_SIZE; i++)
    {
        bool isInput = false;

        if (graphArray[i])
        {
            if (!graphArray[i]->next)
            {
                for (int j = 0; j < MAX_SIZE; j++)
                {
                    if (graphArray[j] && j != i)
                    {
                        Graph* p = graphArray[j];

                        p = p->next;

                        while (p)
                        {
                            if (p->key == graphArray[i]->key)
                            {
                                isInput = true;
                                break;
                            }

                            p = p->next;
                        }
                    }
                }

                if (!isInput)
                {
                    isFound = true;

                    cout << "Isolated Vertice found: " << graphArray[i]->key << endl;

                }
            }
        }


    }

    if (!isFound)
    {
        cout << "No isolated vertices found\n";
    }

}

void mainMenu() {
    cout << "\nMenu:\n";
    cout << "1. Add node\n";
    cout << "2. Add edge\n";
    cout << "3. Print all elements\n";
    cout << "4. Find Isolated Vertices\n";
    cout << "5. Exit\n";
}

int main() {


    initializeGraph(); // Инициализира графа с въведения брой върхове

    int choice, u, v, counter = 0;


    while (true) {
        mainMenu(); // Показва менюто
        cout << "Choose option: ";
        cin >> choice;

        switch (choice) {

        case 1:
            // Въвежда връх
            cout << "Enter node: ";
            cin >> u;

            if (!searchNode(u) && counter < MAX_SIZE)
            {
                addNode(u);

                counter++;

            }
            else if (counter >= MAX_SIZE)
            {
                cout << "Graph is full\n";
            }
            else
            {
                cout << "Node already exist\n";
            }

            break;

        case 2:
            // Въвежда ребро между два върха
            cout << "Enter start node: ";
            cin >> u;
            cout << "Enter end node: ";
            cin >> v;


            if (searchEdge(u, v))
            {
                cout << "Rainbow already exist\n";
            }
            else
            {
                bool isInvalid = false;

                if (!searchNode(u) && counter < MAX_SIZE)
                {
                    addNode(u);
                }
                else {
                    cout << "No space";

                    isInvalid = true;
                }

                if (!searchNode(v) && counter < MAX_SIZE)
                {
                    addNode(v);

                }
                else {
                    cout << "No space";

                    isInvalid = true;
                }

                if (!isInvalid)
                {
                    addEdge(u, v);
                }


            }

            break;
        case 3:
            // Показва графа
            display();
            break;
        case 4:
            // Намира и показва изолираните върхове
            findIsolatedVertices();
            break;
        case 5:
            // Излиза от програмата
            cout << "Exit.\n";
            return 0;
        default:
            // Показва съобщение за невалидна опция
            cout << "Invalid option. Try again.\n";
            break;
        }
    }

    return 0;
}