"KPV" <k.vester@FjerNmobilixnet.dk> writes:
> Hvordan kan jeg undersøge om tilføjelsen af en kant danner en kreds?
> Grafen er på computeren et int[][] (dobbelt array), der indeholder værdier
> hvis en kant er brugt og 0 hvis den ikke er.
> "X-" og "Y-aksen" er punkterne i grafen
Det er en representation af incidens-matricen, og du vil se om
tilføjelsen af en ny kant skaber en cykel i grafen (for nu at bruge
løst-oversatte engelske ord for det - det er en vane, beklager).
Jeg antager at det er en orienteret graf, altså kanterne har en
retning, og bare fordi der en kant fra knude A til knude B, så er der
ikke nødvendigvis en kant den anden vej.
Man taler typisk ikke om cykler i uorienterede grafer.
Ok, først og fremmest: Ved du at der ikke er en cykel i forvejen?
Lad os antage at der ikke er. Det gør det nemmere, fordi så vil enhver
cykel skyldes den nye kant.
Der er forskellige måder at finde ud af om en graf har en cykel. Den
nemmeste er nok graffarvning.
Antag den nye kant (A->B) går fra knude A til knude B.
Du er så interesseret i om man kan komme fra B til A.
Følgende markerer (farver) alle knuder man kan nå fra B, så hvis A
bliver markeret, så vil tilføjelsen af kanten A->B lave en cykel.
Lav en list af knuder.
Farv B rød og put den i listen.
Så længe der er knuder i listen, så gør følgende:
Tag en knude fra listen, kalde den K.
For hver knude, L, som K har en kant til:
Hvis L ikke er rød, så farv L rød og tilføj den til listen.
Hvis A er rød, så er der en cykel, ellers er der ikke.
Algoritmen stopper, da en knude kun kan komme i listen en gang
(derefter er den markeret, og bliver ikke puttet i den igen).
Håber det hjælper
/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgement merely degrades the spirit divine.'
|