Генерация графа. Алгоритм Прима

[buk_bear]

Здравствуйте, помогите пожалуйста составить генерацию графа и алгоритм Прима в одном коде.
Вот мои наработки:

#include <iostream>
#include <conio.h>
#include <iomanip>
#include <stdlib.h>
 
int a, b, u, v, n, x, y;
int ne = 1;
int visited[10] = {0};
int min;
int mincost = 0;
int adj_matrix[10][10];
 
void gen_random_graph(int n)
{
    int adj_matrix[n][n];
    for(int u = 0; u < n; u++)
    {
        for (int v = 0; v < n; v++)
        {
            if(adj_matrix[u][v]==adj_matrix[v][u])
            {
                adj_matrix[u][v] = rand() % 10 + 1;
                std::cout << adj_matrix[u][v] << std::endl;
            }
        }
    }
 
}
 
int main()
{
    int N;
    std::cout << "Enter the number of vertices: ";
    std::cin >> N;
    gen_random_graph(N+1);
 
    int path[100] = {0}; //В этот массив будут записываться вершины, по которым составиться путь
    int path_index = 0;
 
    std::cout << "\nMatrix" << std::endl; //Введи матрицу
 
    for(int u = 0; u < N; u++)
    {
        for(int v = 0; v < N; v++)
        {
            std::cout << adj_matrix[u][v] << std::setw(5);
        }
        std::cout << "\n";
    }
 
    while(ne < N)
    {
        for(u = 1, min = 999; u <= N; u++)
        for(v = 1; v <= N; v++)
        if(adj_matrix[u][v] < min)
        if(visited[u] != 0)
        {
            min = adj_matrix[u][v];
            a = x = u;
            b = y = v;
        }
        if(visited[x] == 0 || visited[y] == 0)
        {
            path[path_index] = b;
            path_index++;
            //cout<<"\n "<<ne++<<"  "<<a<<"  "<<b<<min; //Можно вывести так
            ne++; //если строчку выше раскомментировать - эту закомментировать
            mincost += min;
            visited[b] = 1;
 
        }
        adj_matrix[a][b] = adj_matrix[b][a] = 999;
    }
 
    std::cout << "Minimum spanning tree\n"; //Минимальное остовное дерево
    std::cout << 1 << " --> ";
    for(int u = 0; u < N-1; u++)
    {
        std::cout << path[u];
        if(u < N-2)
        {
            std::cout<<" --> ";
        }
    }
    std::cout << "\nMinimum cost " << mincost; //Минимальная стоимость
    std::cin.get();
 
    return 0;
}

[buk_bear]

Я слегка доработал код:

#include <iostream>
#include <conio.h>
#include <iomanip>
#include <stdlib.h>
 
int a, b, u, v, n, x, y;
int ne = 1;
int visited[10] = {0};
int min;
int mincost = 0;
 
void gen_random_graph(int n)
{
    srand(time(0));
    int adj_matrix[n][n];
 
    for(int u = 0; u < n; u++)
    {
        for (int v = u; v < n; v++)
        { //Вам не нужно рассчитывать вес дважды, поэтому цикл начинается с u
            if(adj_matrix[u][v] == adj_matrix[v][u])
            {
                adj_matrix[u][v] = rand() % 10 + 1;
                std::cout << adj_matrix[u][v] << std::endl;
            }
        }
    }
}
 
int main()
{
    int N;
    int adj_matrix[n][n];
    std::cout << "Enter the number of vertices: ";
    std::cin >> N;
    gen_random_graph(N);
 
    int path[100] = {0}; //В этот массив будут записываться вершины, по которым составиться путь
    int path_index = 0;
 
    std::cout << "\nMatrix" << std::endl; //Введи матрицу
 
    for(int u = 0; u < N; u++)
    {
        for(int v = 0; v < N; v++)
        {
            std::cout << adj_matrix[u][v] << std::setw(5);
        }
        std::cout << "\n";
    }
 
    while(ne < N)
    {
        for(u = 1, min = 999; u <= N; u++)
        for(v = 1; v <= N; v++)
        if(adj_matrix[u][v] < min)
        if(visited[u] != 0)
        {
            min = adj_matrix[u][v];
            a = x = u;
            b = y = v;
        }
        if(visited[x] == 0 || visited[y] == 0)
        {
            path[path_index] = b;
            path_index++;
            //cout<<"\n "<<ne++<<"  "<<a<<"  "<<b<<min; //Можно вывести так
            ne++; //если строчку выше раскомментировать - эту закомментировать
            mincost += min;
            visited[b] = 1;
 
        }
        adj_matrix[a][b] = adj_matrix[b][a] = 999;
    }
        
    std::cout << "Minimum spanning tree\n"; //Минимальное остовное дерево
    std::cout << 1 << " --> ";
    for(int u = 0; u < N-1; u++)
    {
        std::cout << path[u];
        if(u < N-2)
        {
            std::cout<<" --> ";
        }
    }
    std::cout << "\nMinimum cost " << mincost; //Минимальная стоимость
    std::cin.get();
 
    return 0;
}

Но всё равно есть проблемы, они описанные на скриншотах

[ViktorR]

У вас часть кода:

...
while(ne < N)
    {
        for(u = 1, min = 999; u <= N; u++)
        for(v = 1; v <= N; v++)
        if(adj_matrix[u][v] < min)
        if(visited[u] != 0)
...

Тут со скобками всё в порядке??
Это в отношении к циклам for ...
Язык не знаю ...

[BDA]

Целиком код не смотрел. adj_matrix в main и в gen_random_graph это два совершенно разных локальных массива. Поэтому заполнение массива в функции gen_random_graph никак не повлияет на массив в main. Или заведите глобальный массив избыточного размера или динамически выделяйте память под массив и передавайте его в gen_random_graph для заполнения или используйте структуры, доступные в C++ (например, вектор). Если говорить о заполнении матрицы смежности, то делал бы так:

for (int u = 0; u < n; u++)
{
    adj_matrix[u][u] = 0;
    for (int v = u + 1; v < n; v++)
    {
        adj_matrix[u][v] = adj_matrix[v][u] = rand() % 10;
    }
}

А печатать матрицу отдельными циклами, так как эти циклы проходят только половину матрицы.