Skip to content

Appliquer l'algorithme de Prim sur le graphe suivant et montrer toutes les étapes qui doivent être faites, le sommet de départ est A {solution requise sous forme de tableau] exemple de code

Notre équipe de rédaction a passé des heures à enquêter sur la réponse à vos recherches, nous vous fournissons les réponses et nous espérons qu'elle vous sera d'un grand soutien.

Exemple 1 : algorithme de Prim en python

def empty_graph(n):
    res =[]for i in range(n):
        res.append([0]*n)return res
def convert(graph):
    matrix =[]for i in range(len(graph)): 
        matrix.append([0]*len(graph))for j in graph[i]:
            matrix[i][j]=1return matrix
def prims_algo(graph):
    graph1 =convert(graph)
    n =len(graph1)
    tree =empty_graph(n)
    con =[0]whilelen(con)< n :
        found = False
        for i in con:for j in range(n):if j not in con and graph1[i][j]==1:
                    tree[i][j]=1
                    tree[j][i]=1
                    con +=[j]
                    found  = True
                    breakif found :breakreturn tree
matrix =[[0,1,1,1,0,1,1,0,0],[1,0,0,1,0,0,1,1,0],[1,0,0,1,0,0,0,0,0],[1,1,1,0,1,0,0,0,0],[0,0,0,1,0,1,0,0,1],[1,0,0,0,1,0,0,0,1],[1,1,0,0,0,0,0,0,0],[0,1,0,0,0,0,0,0,0],[0,0,0,0,1,1,0,0,0]]

lst =[[1,2,3,5,6],[0,3,6,7],[0,3],[0,1,2,4],[3,5,8],[0,4,8],[0,1],[1],[4,5]]print("From graph to spanning tree:n")print(prims_algo(lst))

Exemple 2 : prims c++

#include#include#include#include#include

using namespace std;constint MAX =1e4+5;typedef pair<longlong,int> PII;
bool marked[MAX];
vector <PII> adj[MAX];longlongprim(int x){
    priority_queue<PII, vector<PII>, greater<PII>> Q;int y;longlong minimumCost =0;
    PII p;
    Q.push(make_pair(0, x));while(!Q.empty()){// Select the edge with minimum weight
        p = Q.top();
        Q.pop();
        x = p.second;// Checking for cycleif(marked[x]== true)continue;
        minimumCost += p.first;
        marked[x]= true;for(int i =0;i < adj[x].size();++i){
            y = adj[x][i].second;if(marked[y]== false)
                Q.push(adj[x][i]);}}return minimumCost;}intmain(){int nodes, edges, x, y;longlong weight, minimumCost;
    cin >> nodes >> edges;for(int i =0;i < edges;++i){
        cin >> x >> y >> weight;
        adj[x].push_back(make_pair(weight, y));
        adj[y].push_back(make_pair(weight, x));}// Selecting 1 as the starting node
    minimumCost =prim(1);
    cout << minimumCost << endl;return0;}

Nous vous montrons des avis et des notes

Si vous avez une déception et une volonté d'innover notre article, nous vous suggérons d'ajouter une note et nous l'examinerons avec plaisir.


Tags : /

Utilisez notre moteur de recherche

Ricerca
Generic filters

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.