Minimum Spanning Tree med Prim's Algortime

[nilsoO]

Hei. Jeg skal lage meg et program som bruker Prim's Algoritme til og finne minimum spanning tree på gitt "graf med noder". Det er et boligfelt der man skal legge en kabel mellom hvert hus, husene er koblet sammen med forskjellige kanter/størrelser. Man skal da finne hvilken vei som gjør at alle husene er koblet sammen, og at man da får minst mulig kostnad. Har lest en del om emnet men sliter litt med og starte det hele, og håpet på litt hjelp fra dere:) Jeg tenkte meg en slik 2 dimensjonal graf der jeg legger inn info om hvilken node man er i og hvilke kanter denne noden hadde. For da og legge denne noden som er valgt fra start, pluss den noden man velger, eller kanten på noden som er billigst inn i en annen graf som skal holde på disse til slutt. Da jeg skal skrive ut hvilken vei som ble billigst.

 

Håper dere forstod hvordan jeg tenkte, for er bare kodingen som jeg sliter litt med, og håpet jeg kunne få litt pekepinn på hvordan jeg skal starte det hele.

 

På forhånd takk!

[ti-guru]

Hei. Jeg skal lage meg et program som bruker Prim's Algoritme til og finne minimum spanning tree på gitt "graf med noder". Det er et boligfelt der man skal legge en kabel mellom hvert hus, husene er koblet sammen med forskjellige kanter/størrelser. Man skal da finne hvilken vei som gjør at alle husene er koblet sammen, og at man da får minst mulig kostnad. Har lest en del om emnet men sliter litt med og starte det hele, og håpet på litt hjelp fra dere:) Jeg tenkte meg en slik 2 dimensjonal graf der jeg legger inn info om hvilken node man er i og hvilke kanter denne noden hadde. For da og legge denne noden som er valgt fra start, pluss den noden man velger, eller kanten på noden som er billigst inn i en annen graf som skal holde på disse til slutt. Da jeg skal skrive ut hvilken vei som ble billigst.

 

Håper dere forstod hvordan jeg tenkte, for er bare kodingen som jeg sliter litt med, og håpet jeg kunne få litt pekepinn på hvordan jeg skal starte det hele.

 

På forhånd takk!

 

Hei,

 

Det du trenger er en god bok om algoritmer og datastrukturer. Har selv lest denne og likte den godt.I kapittelet om grafer diskuterer de også Prims og Kruskals algoritmer for minimum spanning tree

[Valkyrex]

Det beste er å lære seg algoritmen godt, sånn at man lett kan implementere den i kode.

Bedre kilder trenger man ikke nesten:

http://en.wikipedia.org/wiki/Minimum_spanning_tree

http://en.wikipedia.org/wiki/Prim's_algorithm

 

For å lage grafen, kalkulasjoner, og slutt produktet hadde jeg anbefalt Python sammen med Networkx

http://python.org/

http://networkx.lanl.gov/

 

Lagde selv Prims og denne (http://en.wikipedia.org/wiki/Dijkstra's_algorithm) med dette "oppsettet".

[GeirGrusom]

Tror dette er en skoleoppgave... Og det er postet i en språkspesifikk seksjon, så tror ikke anbefalninger om andre programmeringsspråk har noe her å gjøre.

Endret 26. april 2012 av GeirGrusom

[etse]

Et annet tips er å bli kjent med begreper som "nabomatriser" og "nabolister". (Adjency list og adjency matrix på engelsk). For prims er en sortert Adjency list perfekt, og åpner opp for enkle og effektive implementasjoner.

[Valkyrex]

Tror dette er en skoleoppgave... Og det er postet i en språkspesifikk seksjon, så tror ikke anbefalninger om andre programmeringsspråk har noe her å gjøre.

 

Ble litt revet med da jeg har vært igjenom samma oppgave, bare med fritt valg av språk, hehe. Skal dobelt sjekke hvilket forum-del jeg er på nesten gang, hehe ^^