Алгоритм Прима, использующий список смежности в c ++ - PullRequest
Новая
       42

Алгоритм Прима, использующий список смежности в c ++

0 голосов
/ 30 марта 2020

Я реализую простую версию алгоритма Прима, используя список смежности , используя базовую c идею реализации графа. Вот мой подход к этому алгоритму -

1. Выберите индекс.

2. Внутри функции Prims пометьте индекс как посещенный.

3.Если какая-либо смежная вершина не посещена и стоимость этой вершины меньше чем mi (которая инициализируется как INF в начало функции) затем mi сохраняет стоимость, а родительский хранит индекс.

4. В последней смежной вершине mi хранится наименьшая стоимость, а родительский хранит наименьший индекс стоимости.

5 . Снова вызовите простые числа для родительской вершины.

6. При последнем возврате итоговой стоимости.

Но проблема в моем подходе состоит в том, что когда я сравниваю стоимость [v] с ми, то это дает мне ошибка, потому что я сравниваю int с вектором. Я пытался использовать mi в качестве вектора, но затем он дает мне ошибку в разделе результатов. Мой код приведен ниже - 

#include<bits/stdc++.h>
using namespace std;
#define mx 10005
#define INF 1000000007
vector<int>graph[mx],cost[mx];
int visited[mx]={0};
int result=0,parent;
int n,e,x,y,w,mi;

int prims(int u)
{
    mi=INF;
    visited[u]=1;
    for(int i=0;i<graph[u].size();++i)
    {
        int v=graph[u][i];
        if(visited[v]==0 and cost[v]<mi)
        {
            mi=cost[v];
            parent=v;
        }
        if(i==graph[u].size()-1)
        {
            result+=mi;
            prims(parent);
        }
    }
    return result;
}

int main()
{
    cin>>n>>e;
    for(int i=1;i<=e;++i)
    {
        cin>>x>>y>>w;
        graph[x].push_back(y);
        graph[y].push_back(x);
        cost[x].push_back(w);
        cost[y].push_back(w);
    }
    int src;cin>>src;
    int p=prims(src);
    cout<<p<<endl;

    return 0;
}
...