close

Вход

Забыли?

вход по аккаунту

?

Постановка лабораторной работы по теории графов

код для вставкиСкачать
1996г.
Ïîñòàíîâêà ëàáîðàòîðíîé ðàáîòû ïî òåîðèè ãðàôîâ
(àëãîðèòìû è ïðîãðàììû)
1. Ââåäåíèå
 ïîñëåäíåå âðåìÿ èññëåäîâàíèÿ â îáëàñòÿõ, òðàäèöèîííî îòíîñÿùèõñÿ ê äèñêðåòíîé
ìàòåìàòèêå, çàíèìàþò âñå áîëåå çàìåòíîå ìåñòî. Íàðÿäó ñ òàêèìè êëàññè÷åñêèìè
ðàçäåëàìè ìàòåìàòèêè, êàê ìàòåìàòè÷åñêèé àíàëèç, äèôôåðåíöèàëüíûå óðàâíåíèÿ, â
ó÷åáíûõ ïëàíàõ ñïåöèàëüíîñòè "Ïðèêëàäíàÿ ìàòåìàòèêà" è ìíîãèõ äðóãèõ
ñïåöèàëüíîñòåé ïîÿâèëèñü ðàçäåëû ïî ìàòåìàòè÷åñêîé ëîãèêå, àëãåáðå,
êîìáèíàòîðèêå è òåîðèè ãðàôîâ. Ïðè÷èíû ýòîãî íåòðóäíî ïîíÿòü, ïðîñòî îáîçíà÷èâ êðóã
çàäà÷, ðåøàåìûõ íà áàçå ýòîãî ìàòåìàòè÷åñêîãî àïïàðàòà (ñì. ï.1.3 äàííîãî ðàçäåëà).
1.1 Îñíîâíûå ïîíÿòèÿ òåîðèè ãðàôîâ.
Äåòàëüíûå îïðåäåëåíèÿ òåîðèè ãðàôîâ ìîæíî íàéòè â ðàáîòàõ [2, 3, 4, 5, 6]. Çäåñü
ìû ëèøü îãðàíè÷èìñÿ ïåðå÷èñëåíèåì íåêîòîðûõ òåðìèíîâ, êîòîðûå áóäóò âñòðå÷àòüñÿ
â äàëüíåéøåì, è èõ êðàòêèì îïèñàíèåì.
Ãðàô- íåïóñòîå ìíîæåñòâî V è X- íåêîòîðûé íàáîð ïàð ýëåìåíòîâ èç V. Ýëåìåíòû
ìíîæåñòâà V íàçûâàþòñÿ âåðøèíàìè, à ýëåìåíòû íàáîðà X- ðåáðàìè.
Ïîäãðàô- ïîäãðàôîì ãðàôà G íàçûâàåòñÿ ãðàô, âñå âåðøèíû è ðåáðà êîòîðîãî
ñîäåðæàòñÿ ñðåäè âåðøèí è ðåáåð ãðàôà G. Îñòîâíûé ïîäãðàô ñîäåðæèò âñå
âåðøèíû ãðàôà G.
Ñâÿçíûé ãðàô- ãðàô, ó êîòîðîãî äëÿ ëþáûõ äâóõ ðàçëè÷íûõ âåðøèí ñóùåñòâóåò
öåïü (ïîñëåäîâàòåëüíîñòü ñìåæíûõ âåðøèí), ñîåäèíÿþùàÿ èõ.
Âçâåøåííûé ñâÿçíûé ãðàô- ñâÿçíûé ãðàô, ñ çàäàííîé âåñîâîé ôóíêöèåé (êàæäîìó
ýëåìåíòó íàáîðà X ñòàâèòñÿ â ñîîòâåòñòâèå íåêîòîðîå ÷èñëî - âåñ ðåáðà).
Äåðåâî- ñâÿçíûé ãðàô, íå ñîäåðæàùèé öèêëîâ.
Îñòîâ- îñòîâíûé ïîäãðàô, ÿâëÿþùèéñÿ äåðåâîì.
1.2 Ñïîñîáû çàäàíèÿ ãðàôîâ.
Ñóùåñòâóåò ðÿä ñïîñîáîâ çàäàíèÿ ãðàôîâ. Äëÿ ðåøåíèÿ êîíêðåòíîé çàäà÷è ìîæíî
âûáðàòü òîò èëè èíîé ñïîñîá, â çàâèñèìîñòè îò óäîáñòâà åãî ïðèìåíåíèÿ. Çäåñü ìû
ïåðå÷èñëèì íåêîòîðûå, íàèáîëåå èçâåñòíûå ñïîñîáû, äàäèì èõ êðàòêóþ
õàðàêòåðèñòèêó ñ òî÷êè çðåíèÿ óäîáñòâà ââîäà è îáðàáîòêè íà ÝÂÌ.
Ìàòðèöà èíöèäåíòíîñòè- ìàòðèöà ðàçìåðîì n  m (n- ÷èñëî âåðøèí, m- ÷èñëî
ðåáåð), ýëåìåíòû êîòîðîé ðàâíû 1, åñëè i-ÿ âåðøèíà èíöèäåíòíà j-ìó ðåáðó, è 0 â
ïðîòèâíîì ñëó÷àå.
Ìàòðèöà èíöèäåíòíîñòè íåóäîáíà äëÿ ââîäà è îáðàáîòêè íà ÝÂÌ, êðîìå òîãî îíà íå
íåñåò ïðÿìîé èíôîðìàöèè î ðåáðàõ.
Ìàòðèöà ñìåæíîñòè- ìàòðèöà ðàçìåðîì n  n, ýëåìåíòû êîòîðîé ðàâíû 1, åñëè i-ÿ
âåðøèíà ñìåæíà ñ j-îé, è 0 â ïðîòèâíîì ñëó÷àå.
Ìàòðèöà ñìåæíîñòè ÿâëÿåòñÿ ñèììåòðè÷íîé è äîñòàòî÷íî ïðîñòî ìîæåò
èñïîëüçîâàòüñÿ äëÿ ââîäà è îáðàáîòêè íà ÝÂÌ. Äëÿ ñëó÷àÿ âçâåøåííîãî ãðàôà âìåñòî
1 èñïîëüçóåòñÿ çíà÷åíèå âåñîâîé ôóíêöèè è òàêàÿ ìàòðèöà íàçûâàåòñÿ ìàòðèöåé
âåñîâ.
Ñïèñêè ñìåæíîñòè- êàæäûé i-é ñïèñîê ñîäåðæèò íîìåðà âåðøèí, ñìåæíûõ i-îé
âåðøèíå.
Ñïèñêè ñìåæíîñòè óäîáíû äëÿ ââîäà â ÝÂÌ, ýêîíîìÿò ïàìÿòü, íî íå ìîãóò
èñïîëüçîâàòüñÿ â ñëó÷àå âçâåøåííîãî ãðàôà.
1.3 Îáçîð çàäà÷ òåîðèè ãðàôîâ.
Ðàçâèòèå òåîðèè ãðàôîâ â îñíîâíîì îáÿçàíî áîëüøîìó ÷èñëó âñåâîçìîæíûõ
ïðèëîæåíèé. Ïî-âèäèìîìó, èç âñåõ ìàòåìàòè÷åñêèõ îáúåêòîâ ãðàôû çàíèìàþò îäíî èç
ïåðâûõ ìåñò â êà÷åñòâå ôîðìàëüíûõ ìîäåëåé ðåàëüíûõ ñèñòåì.
Ãðàôû íàøëè ïðèìåíåíèå ïðàêòè÷åñêè âî âñåõ îòðàñëÿõ íàó÷íûõ çíàíèé: ôèçèêå,
áèîëîãèè, õèìèè, ìàòåìàòèêå, èñòîðèè, ëèíãâèñòèêå, ñîöèàëüíûõ íàóêàõ, òåõíèêå è
ò.ï. Íàèáîëüøåé ïîïóëÿðíîñòüþ òåîðåòèêî-ãðàôîâûå ìîäåëè èñïîëüçóþòñÿ ïðè
èññëåäîâàíèè êîììóíèêàöèîííûõ ñåòåé, ñèñòåì èíôîðìàòèêè, õèìè÷åñêèõ è
ãåíåòè÷åñêèõ ñòðóêòóð, ýëåêòðè÷åñêèõ öåïåé è äðóãèõ ñèñòåì ñåòåâîé
ñòðóêòóðû.
Äàëåå ïåðå÷èñëèì íåêîòîðûå òèïîâûå çàäà÷è òåîðèè ãðàôîâ è èõ ïðèëîæåíèÿ:
- Çàäà÷à î êðàò÷àéøåé öåïè
 çàìåíà îáîðóäîâàíèÿ
 ñîñòàâëåíèå ðàñïèñàíèÿ äâèæåíèÿ òðàíñïîðòíûõ ñðåäñòâ
 ðàçìåùåíèå ïóíêòîâ ñêîðîé ïîìîùè
 ðàçìåùåíèå òåëåôîííûõ ñòàíöèé
- Çàäà÷à î ìàêñèìàëüíîì ïîòîêå
 àíàëèç ïðîïóñêíîé ñïîñîáíîñòè êîììóíèêàöèîííîé ñåòè
 îðãàíèçàöèÿ äâèæåíèÿ â äèíàìè÷åñêîé ñåòè
 îïòèìàëüíûé ïîäáîð èíòåíñèâíîñòåé âûïîëíåíèÿ ðàáîò
 ñèíòåç äâóõïîëþñíîé ñåòè ñ çàäàííîé ñòðóêòóðíîé íàäåæíîñòüþ
 çàäà÷à î ðàñïðåäåëåíèè ðàáîò
- Çàäà÷à îá óïàêîâêàõ è ïîêðûòèÿõ
 îïòèìèçàöèÿ ñòðóêòóðû ÏÇÓ
 ðàçìåùåíèå äèñïåò÷åðñêèõ ïóíêòîâ ãîðîäñêîé òðàíñïîðòíîé ñåòè
- Ðàñêðàñêà â ãðàôàõ
 ðàñïðåäåëåíèå ïàìÿòè â ÝÂÌ
 ïðîåêòèðîâàíèå ñåòåé òåëåâèçèîííîãî âåùàíèÿ
- Ñâÿçíîñòü ãðàôîâ è ñåòåé
 ïðîåêòèðîâàíèå êðàò÷àéøåé êîììóíèêàöèîííîé ñåòè
 ñèíòåç ñòðóêòóðíî-íàäåæíîé ñåòè öèðêóëÿöèîííîé ñâÿçè
 àíàëèç íàäåæíîñòè ñòîõàñòè÷åñêèõ ñåòåé ñâÿçè
- Èçîìîðôèçì ãðàôîâ è ñåòåé
 ñòðóêòóðíûé ñèíòåç ëèíåéíûõ èçáèðàòåëüíûõ öåïåé
 àâòîìàòèçàöèÿ êîíòðîëÿ ïðè ïðîåêòèðîâàíèè ÁÈÑ
- Èçîìîðôíîå âõîæäåíèå è ïåðåñå÷åíèå ãðàôîâ
 ëîêàëèçàöèÿ íåèñïðàâíîñòè ñ ïîìîùüþ àëãîðèòìîâ ïîèñêà ÌÈÏÃ

ïîêðûòèå ñõåìû çàäàííûì íàáîðîì òèïîâûõ ïîäñõåì
- Àâòîìîðôèçì ãðàôîâ
 êîíñòðóêòèâíîå ïåðå÷èñëåíèå ñòðóêòóðíûõ èçîìåðîâ äëÿ
ïðîèçâîäíûõ îðãàíè÷åñêèõ ñîåäèíåíèé
 ñèíòåç òåñòîâ öèôðîâûõ óñòðîéñòâ
2. Ïîñòàíîâêà çàäà÷è
2.1 Àëãîðèòì ïîèñêà îñòîâà ìèíèìàëüíîãî âåñà.
Âî âçâåøåííîì ñâÿçíîì ãðàôå (G,f) íàéòè îñòîâ ìèíèìàëüíîãî âåñà. Òàêàÿ çàäà÷à
ìîæåò èìåòü, íàïðèìåð, ñëåäóþùóþ èíòåðïðåòàöèþ. Èñõîäíûé ãðàô G åñòü
ïðîåêòèðóåìàÿ ñèñòåìà äîðîã (ðåáðà ãðàôà), ñâÿçûâàþùèõ ãîðîäà íåêîòîðîé îáëàñòè
(âåðøèíû ãðàôà). Ïóñòü âåñ ðåáðà f(x)- ñòîèìîñòü ñòðîèòåëüñòâà äîðîãè,
ñîåäèíÿþùåé äâà ãîðîäà. Òðåáóåòñÿ ïîñòðîèòü ñèñòåìó äîðîã ìèíèìàëüíîé ñòîèìîñòè,
÷òîáû èç ëþáîãî ãîðîäà ìîæíî áûëî ïðîåõàòü â ëþáîé ãîðîä (èñêîìûé îñòîâíûé ïîäãðàô ñâÿçíûé). Î÷åâèäíî, ðåøåíèå çàäà÷è ñóùåñòâóåò, è èñêîìûé îñòîâíûé ïîäãðàô
ÿâëÿåòñÿ äåðåâîì. Îïèøåì îäèí èç âîçìîæíûõ àëãîðèòìîâ ðåøåíèÿ (Ð. Ïðèì 1957 ã.).
Äàí ñâÿçíûé ãðàô G  V , X , V  n è âåñîâàÿ ôóíêöèÿ f x , x  X . Àëãîðèòì
ñîñòîèò èç n-1 øàãà. íà êàæäîì øàãå ñòðîèòñÿ äåðåâî Di , i  1,..., n  1. Äåðåâî Dn1
ÿâëÿåòñÿ îñòîâîì ìèíèìàëüíîãî âåñà.
1. Âûáèðàåì ðåáðî x 1 ìèíèìàëüíîãî âåñà èç ìíîæåñòâà âñåõ ðåáåð X è ñòðîèì
äåðåâî D1 , ïîëàãàÿ åãî ñîñòîÿùèì èç ðåáðà x 1 è äâóõ èíöèäåíòíûõ ðåáðó x 1 âåðøèí.
2. Åñëè äåðåâî Di ïîðÿäêà Di  i  1 óæå ïîñòðîåíî, òî ñðåäè ðåáåð, ñîåäèíÿþùèõ
âåðøèíû ýòîãî äåðåâà ñ âåðøèíàìè ãðàôà G, íå âõîäÿùèìè â Di , âûáåðåì ðåáðî x i 1
ìèíèìàëüíîãî âåñà. Ñòðîèì äåðåâî Di 1 ïðèñîåäèíÿÿ ê Di ðåáðî x i 1 âìåñòå ñ åãî íå
âõîäÿùèì â Di êîíöîì.
3. Åñëè i=n-1 , òî îñòîâ ìèíèìàëüíîãî âåñà Dn1 ïîñòðîåí, êîíåö. Èíà÷å ïåðåéòè ê ï.2.
a f
af
2.2 Àëãîðèòì ïîèñêà äåðåâà êðàò÷àéøèõ ïóòåé.
Ðàññìîòðèì çàäà÷ó î êðàò÷àéøåì ïóòè. Ïóñòü (G,f) - âçâåøåííûé ñâÿçíûé ãðàô.
Âåñ f(x) ðåáðà x èíòåðïðåòèðóåì êàê ðàññòîÿíèå ìåæäó âåðøèíàìè, ñìåæíûìè äàííîìó
ðåáðó. Äëÿ çàäàííîé íà÷àëüíîé âåðøèíû s è êîíå÷íîé âåðøèíû t èùåòñÿ ïðîñòàÿ öåïü,
ñîåäèíÿþùàÿ s è t ìèíèìàëüíîãî âåñà. (s,t) - öåïü ìèíèìàëüíîãî âåñà íàçûâàþò
êðàò÷àéøèì (s,t) - ïóòåì. Î÷åâèäíî, ðåøåíèå çàäà÷è ñóùåñòâóåò. Îïèøåì îäèí èç
âîçìîæíûõ àëãîðèòìîâ ðåøåíèÿ (Å. Äåéêñòðà, 1959 ã.).
Äàí ñâÿçíûé ãðàô G  V , X , V  n è âåñîâàÿ ôóíêöèÿ f(x).
Íà êàæäîé èòåðàöèè àëãîðèòìà ëþáàÿ âåðøèíà v ãðàôà G èìååò íåîòðèöàòåëüíóþ
ìåòêó l(v), êîòîðàÿ ìîæåò áûòü âðåìåííîé èëè ïîñòîÿííîé (ïîñòîÿííóþ ìåòêó ïîìå÷àåì l(v)+).
Ïåðåä íà÷àëîì ïåðâîé èòåðàöèè âåðøèíà s èìååò ïîñòîÿííóþ ìåòêó l(s)+=0, à ìåòêè
âñåõ îñòàëüíûõ âåðøèí ðàâíû  è ýòè ìåòêè âðåìåííûå. Ïîñòîÿííàÿ ìåòêà l(v)+ íàéäåííûé âåñ êðàò÷àéøåãî (s,v) - ïóòè. Âðåìåííàÿ ìåòêà l(v) - âåñ êðàò÷àéøåãî (s,v)
- ïóòè, ïðîõîäÿùåãî ÷åðåç âåðøèíû ñ ïîñòîÿííûìè ìåòêàìè.
Íà êàæäîé èòåðàöèè àëãîðèòìà âðåìåííàÿ ìåòêà îäíîé èç âåðøèí ïåðåõîäèò â
ïîñòîÿííóþ; òàêèì îáðàçîì, äëÿ íàõîæäåíèÿ êðàò÷àéøèõ (s,v) - ïóòåé äëÿ âñåõ âåðøèí
v ãðàôà G òðåáóåòñÿ n-1 èòåðàöèÿ àëãîðèòìà.
Òàêæå ñ êàæäîé âåðøèíîé v ãðàôà G (êðîìå s) ñâÿçûâàåòñÿ âðåìåííàÿ èëè
ïîñòîÿííàÿ ìåòêà (u) (ïîñòîÿííóþ ìåòêó ïîìå÷àåì (u)+). (u) ÿâëÿåòñÿ íîìåðîì âåðøèíû,
ïðåäøåñòâóþùåé v â (s,v) - ïóòè, èìåþùèì ìèíèìàëüíûé âåñ ñðåäè âñåõ (s,v) - ïóòåé,
ïðîõîäÿùèõ ÷åðåç âåðøèíû, ïîëó÷èâøèõ ê äàííîìó ìîìåíòó ïîñòîÿííûå ìåòêè. Ïîñëå
a f
ïîëó÷åíèÿ âåðøèíîé ïîñòîÿííîé ìåòêè (u)+, ñ ïîìîùüþ ïîñòîÿííûõ -ìåòîê óêàçûâàåòñÿ
ïîñëåäîâàòåëüíîñòü âåðøèí, ñîñòàâëÿþùàÿ êðàò÷àéøèé (s,v) - ïóòü.
1. Ïîëîæèòü l(s)+=0, ò.å. ñ÷èòàòü ýòó ìåòêó ïîñòîÿíîé, è l(v)= äëÿ âñåõ
v  V , v  s, ñ÷èòàÿ ýòè ìåòêè âðåìåííûìè. Ïðèíÿòü u=s.
2. Äëÿ âñåõ v  Ã u ñ âðåìåííûìè ìåòêàìè âûïîëíèòü: åñëè l(v)>l(u)+f(x) è (v)=u.
Èíà÷å l(v) è (v) íå ìåíÿòü.
3. Ïóñü V' - ìíîæåñòâî âåðøèí ñ âðåìåííûìè ìåòêàìè l. Íàéòè âåðøèíó v*, òàêóþ, ÷òî
af
l ( v *)  min l ( v )
v V '
Ñ÷èòàòü ìåòêó l(v*)+ ïîñòîÿííîé ìåòêîé âåðøèíû v*; (v*)+.
4. u=v*. Åñëè u=t, òî ïåðåéòè ê ï.5 (l(t)+ - âåñ êðàò÷àéøåãî (s,t) - ïóòè). Èíà÷å
ïåðåéòè ê ï.2.
5. Ïî ïîñòîÿííûì  - ìåòêàì óêàçûâàåòñÿ êðàò÷àéøèé (s,t) - ïóòü. Êîíåö.
Ïóíêò 4 ìîæíî ìîäèôèöèðîâàòü òàê, ÷òîáû àëãîðèòì çàêàí÷èâàë ðàáîòó ïîñëå
ïîëó÷åíèÿ âñåìè âåðøèíàìè ãðàôà G ïîñòîÿííûõ ìåòîê, ò.å. íàõîäÿòñÿ êðàò÷àéøèå ïóòè
èç s âî âñå âåðøèíû ãðàôà. Àëãîðèòì îïðåäåëèò îñòîâíîå äåðåâî D êðàò÷àéøèõ
ïóòåé èç âåðøèíû s. Äëÿ ëþáîé âåðøèíû v åäèíñòâåííûé (s,v) - ïóòü â äåðåâå D
áóäåò
êðàò÷àéøèì
(s,v)
ïóòåì
â
ãðàôå
G.
4. Ñïèñîê ëèòåpàòópû
1 Èñìàãèëîâ Ð.Ñ., Êàëèíêèí À.Â. Ìàòåpèàëû ê ïpàêòè÷åñêèì çàíÿòèÿì ïî êópñó:
Äèñêpåòíàÿ ìàòåìàòèêà ïî òåìå: Àëãîpèòìû íà ãpàôàõ. - Ì.: ÌÃÒÓ, 1995, 24 ñ.
2 Ãàâpèëîâ Ã.Ï., Ñàïîæåíêî À.À. Çàäà÷è è óïpàæíåíèÿ ïî êópñó äèñêpåòíîé
ìàòåìàòèêè. - Ì.: Hàóêà, 1992, 408 ñ.
3 Ñìîëüÿêîâ Ý.Ð. Ââåäåíèå â òåîpèþ ãpàôîâ. Ì.: ÌÃÒÓ, 1992, 32 ñ.
4 Hå÷åïópåíêî Ì.È. Àëãîpèòìû è ïpîãpàììû påøåíèÿ çàäà÷ íà ãpàôàõ è ñåòÿõ. Hîâîñèáèpñê: Hàóêà, 1990, 515 ñ.
5 Ðîìàíîâñêèé È.Â. Àëãîpèòìû påøåíèÿ ýêñòpåìàëüíûõ çàäà÷. - Ì.: Hàóêà, 1977,
352 ñ.
6 Håôåäîâ Â.H., Îñèïîâà Â.À. Êópñ äèñêpåòíîé ìàòåìàòèêè. - Ì.: ÌÀÈ, 1992, 264 ñ.
7 Ïèññàíåöêè Ñ. Òåõíîëîãèÿ ðàçðåæåííûõ ìàòðèö. - Ì.: Ìèð, 1988, 412 ñ.
8 Ãíåäåíêî Á.Â. Êóðñ òåîðèè âåðîÿòíîñòåé. - Ì.: Íàóêà, 1988, 448 ñ.
9 Âåíòöåëü Å.Ñ., Îâ÷àðîâ Ë.À. Òåîðèÿ âåðîÿòíîñòåé. - Ì.: Íàóêà, 1969, 367 ñ.
10 Çóáêîâ À.Ì., Ñåâàñòüÿíîâ Á.À., ×èñòÿêîâ Â.Ï. - Ñáîðíèê çàäà÷ ïî òåîðèè
âåðîÿòíîñòåé. - Ì.: Íàóêà, 1989, 320 ñ.
11 Ñåâàñòüÿíîâ Á.À. Âåðîÿòíîñòíûå ìîäåëè. - Ì.: Íàóêà, 1992, 176 ñ.
12 Áî÷àðîâ Ï.Ï., Ïå÷èíêèí À.Â. Òåîðèÿ âåðîÿòíîñòåé. - Ì.: Èçä-âî ÐÓÄÍ, 1994, 172 ñ.
13 Áî÷àðîâ Ï.Ï., Ïå÷èíêèí À.Â. Ìàòåìàòè÷åñêàÿ ñòàòèñòèêà. - Ì.: Èçä-âî ÐÓÄÍ,
1994, 164 ñ.
14 Êîëìîãîðîâ À.Í., Ôîìèí Ñ.Â. Ýëåìåíòû òåîðèè ôóíêöèé è ôóíêöèîíàëüíîãî àíàëèçà.
- Ì.: Íàóêà, 1989, 624 ñ.
5. Ïpèëîæåíèå:
Òåêñòû ïpîãpàìì íà ÿçûêå Ñ
/* File prim.c Òåîpèÿ ãpàôîâ
ÐÊ6 Ðåäíèêèí À.H. 1996ã.
/* Àëãîpèòì ïîèñêà îñòîâà ìèíèìàëüíîãî âåñà âî âçâåøåííîì ãpàôå
*/
/* Ð.Ïpèì, 1957 ã.
*/
*/
#include <stdio.h>
#include <stdlib.h>
#include <float.h>
int load_matrix(int n, double* weigh);
int prim(int n, double* weigh);
void print(int n, double* weigh);
/* Ââîä ìàòpèöû âåñîâ */
/* Àëãîpèòì ïîèñêà
/* Âûâîä påçóëüòàòà
*/
*/
void main(void){
int n=0,ret=0;
double *weigh;
printf("\nÀëãîpèòì ïîèñêà îñòîâà ìèíèìàëüíîãî âåñà âî âçâåøåííîì ãpàôå.\n");
printf("Ð.Ïpèì, 1957 ã.\n");
printf("\nÂâåäèòå êîëè÷åñòâî âåpøèí..");
scanf("%d",&n);
if (n <= 1){
printf("\nÊîëè÷åñòâî âåpøèí äîëæíî áûòü áîëüøå åäèíèöû!\n");
exit(1);
}
weigh=malloc(sizeof(double)*n*n);
if (weigh == NULL){
printf("\nHåäîñòàòî÷íî ïàìÿòè äëÿ çàãpóçêè ìàññèâà!\n");
exit(2);
}
ret=load_matrix(n,weigh);
if (ret != 0){
printf("\nÎøèáêà ââîäà äàííûõ!\n");
exit(5);
}
ret=prim(n,weigh);
if (ret != 0){
switch (ret){
case 1 :
printf("\nÃpàô íå ÿâëÿåòñÿ ñâÿçàííûì!\n");
exit(3);
case 2 :
printf("\nHåäîñòàòî÷íî ïàìÿòè äëÿ pàáîòû!\n");
exit(4);
}
}
print(n,weigh);
free(weigh);
}
int load_matrix(int n, double* weigh){
int i,j,k;
double tmp;
for (i=0; i < n; i++){
for (j=0; j < n; j++){
weigh[n*i+j]=(-1);
}
}
printf("\nÂâåäèòå ïîñëåäîâàòåëüíî âåñà påáåp äëÿ óêàçàííûõ âåpøèí èëè -1 äëÿ íåñìåæíûõ.");
for (i=0; i < n; i++){
for (j=i+1; j < n; j++){
printf("\nÂåpøèíû %d è %d ",i+1,j+1);
k=scanf("%lf",&tmp);
if (k != 1){return(1);}
weigh[i*n+j]=tmp;
}
}
return(0);
}
int prim(int n, double* weigh){
int i,j,k,l,m,flag;
int* index;
double tmp;
index=calloc(sizeof(int),n);
if (index == NULL){return(2);}
index[0]=1;
for (k=0; k < (n-1); k++){
for (i=0,flag=0,tmp=DBL_MAX; i < n; i++){
for (j=i+1; j < n; j++){
if ((weigh[i*n+j] < tmp)&&
(weigh[i*n+j] >= 0)&&
(weigh[j*n+i] == (-1))&&
(index[i]*index[j] == 0)&&
(index[i]+index[j] == 1)){
flag=1;
tmp=weigh[i*n+j];
l=i;
m=j;
}
}
}
if (flag == 1){
weigh[m*n+l]=tmp;
index[m]=1;
index[l]=1;
}
}
for (i=0; i < n; i++){
if (index[i] == 0)
return(1);
}
free(index);
return(0);
}
void print(int n, double* weigh){
int i,j;
double tmp=0.0;
printf("\nÎñòîâ ìèíèìàëüíîãî âåñà:");
for (i=0; i < n; i++){
printf("\n");
for (j=(i+1); j < n; j++){
if (weigh[j*n+i] != (-1)){
printf(" weigh[%d,%d]=%6.2f",i+1,j+1,weigh[j*n+i]);
tmp+=weigh[j*n+i];
}
}
}
printf("\nÂåñ íàéäåííîãî äåpåâà: %6.2f\n",tmp);
}
Òåñòîâûé ïðèìåð èç ðàáîòû [1] (ðèñ.6 íà ñòð. 9).
Àëãîpèòì ïîèñêà îñòîâà ìèíèìàëüíîãî âåñà âî âçâåøåííîì ãpàôå.
Ð.Ïpèì, 1957 ã.
Ââåäèòå êîëè÷åñòâî âåpøèí.. 6
Ââåäèòå ïîñëåäîâàòåëüíî âåñà påáåp äëÿ óêàçàííûõ âåpøèí èëè -1 äëÿ íåñìåæíûõ.
Âåpøèíû 1 è 2 3
Âåpøèíû 1 è 3 -1
Âåpøèíû 1 è 4 -1
Âåpøèíû 1 è 5 -1
Âåpøèíû 1 è 6 1
Âåpøèíû 2 è 3 1
Âåpøèíû 2 è 4 -1
Âåpøèíû 2 è 5 1
Âåpøèíû 2 è 6 2
Âåpøèíû 3 è 4 4
Âåpøèíû 3 è 5 -1
Âåpøèíû 3 è 6 -1
Âåpøèíû 4 è 5 6
Âåpøèíû 4 è 6 -1
Âåpøèíû 5 è 6 2
Îñòîâ ìèíèìàëüíîãî âåñà:
weigh[1,6]= 1.00
weigh[2,3]= 1.00 weigh[2,5]= 1.00 weigh[2,6]= 2.00
weigh[3,4]= 4.00
Âåñ íàéäåííîãî äåpåâà: 9.00
/* File deik.c Òåîpèÿ ãpàôîâ
ÐÊ6 Ðåäíèêèí À.H. 1996ã. */
/* Àëãîpèòì ïîèñêà äåpåâà êpàò÷àéøèõ ïóòåé âî âçâåøåííîì ãpàôå */
/* Å.Äåéêñòpà 1959 ã.
*/
#include <stdio.h>
#include <stdlib.h>
#include <float.h>
int load_matrix(int n, double* weigh);
int deik(int n, int s, double* weigh, int* Q, double* L);
void print(int n, int* Q, double* L);
/* Ââîä ìàòpèöû âåñîâ
/* Àëãîpèòì ïîèñêà
/* Âûâîä påçóëüòàòà
void main(void){
int n=0,s=0,ret=0;
double *weigh;
int* Q; /* Ìàññèâ ìåòîê óêàçàòåëåé íà ïpåäûäóùóþ âåpøèíó
double* L; /* Ìàññèâ íàéäåíûõ âåñîâ ïóòè äî âåpøèíû
*/
*/
printf("\nÀëãîpèòì ïîèñêà äåpåâà êpàò÷àéøèõ ïóòåé âî âçâåøåííîì ãpàôå.\n");
printf("Å.Äåéêñòpà, 1959 ã.\n");
printf("\nÂâåäèòå êîëè÷åñòâî âåpøèí..");
scanf("%d",&n);
if (n <= 1){
printf("\nÊîëè÷åñòâî âåpøèí äîëæíî áûòü áîëüøå åäèíèöû!\n");
exit(1);
}
printf("\nÂâåäèòå íà÷àëüíóþ âåpøèíó..");
scanf("%d",&s);
s--;
if ((s < 0)||(s > (n-1))){
printf("\nHà÷àëüíàÿ âåpøèíà óêàçàíà íåïpàâèëüíî!\n");
exit(1);
}
Q=malloc(n*sizeof(int));
L=malloc(n*sizeof(double));
weigh=malloc(sizeof(double)*n*n);
if ((weigh == NULL)||(Q == NULL)||(L == NULL)){
printf("\nHåäîñòàòî÷íî ïàìÿòè äëÿ çàãpóçêè ìàññèâà!\n");
exit(2);
}
ret=load_matrix(n,weigh);
if (ret != 0){
printf("\nÎøèáêà ââîäà äàííûõ!\n");
exit(5);
}
ret=deik(n,s,weigh,Q,L);
if (ret != 0){
switch (ret){
case 1 :
printf("\nÃpàô íå ÿâëÿåòñÿ ñâÿçàííûì!\n");
exit(3);
case 2 :
printf("\nHåäîñòàòî÷íî ïàìÿòè äëÿ pàáîòû!\n");
exit(4);
}
}
print(n,Q,L);
free(weigh);
free(Q);
free(L);
}
int load_matrix(int n, double* weigh){
int i,j,k;
double tmp;
*/
*/
*/
for (i=0; i < n; i++){
for (j=0; j < n; j++){
weigh[n*i+j]=(-1);
}
}
printf("\nÂâåäèòå ïîñëåäîâàòåëüíî âåñà påáåp äëÿ óêàçàííûõ âåpøèí èëè -1 äëÿ íåñìåæíûõ.");
for (i=0; i < n; i++){
for (j=i+1; j < n; j++){
printf("\nÂåpøèíû %d è %d ",i+1,j+1);
k=scanf("%lf",&tmp);
if (k != 1){return(1);}
weigh[i*n+j]=tmp;
}
}
return(0);
}
int deik(int n,int s, double* weigh, int* Q, double* L){
int i,j,k;
int* QI;
/* Ìàññèâ èíäèêàòîpîâ ïîñòîÿíñòâà ìåòîê óêàçàòåëåé */
double tmp;
QI=calloc(n,sizeof(int));
if (QI == NULL){return(2);}
QI[s]=1;
for (i=0; i < n; i++){
Q[i]=(-1);
L[i]=DBL_MAX;
}
Q[s]=s;
L[s]=0;
weigh[n*(n-1)+s]=0;
for (k=0; k < n; k++){
/* Îñíîâíîé öèêë ïî âåpøèíàì
*/
for (i=0; i < n; i++){
/* Öèêë ïî ñòpîêàì ìàòpèöû âåñîâ */
for (j=i+1; j < n; j++){
/* Öèêë ïî ñòîëáöàì ìàòpèöû âåñîâ */
if ((QI[i]+QI[j] == 1)&&
(QI[i]*QI[j] == 0)&&
(weigh[i*n+j] != (-1.0))&&
(((QI[i] == 1)&&((L[i]+weigh[i*n+j]) < L[j]))||
((QI[j] == 1)&&((L[j]+weigh[i*n+j]) < L[i])))){
if (QI[i] == 1){
L[j]=L[i]+weigh[i*n+j];
Q[j]=i;
}
else{
L[i]=L[j]+weigh[i*n+j];
Q[i]=j;
}
}
}
}
for (tmp=DBL_MAX,i=0; i < n; i++){
if ((tmp > L[i])&&(QI[i] == 0)){
tmp=L[i];
j=i;
}
}
QI[j]=1;
}
free(QI);
return(0);
}
void print(int n, int* Q, double* L){
int i;
printf("\n\nÄåpåâî êpàò÷àéøèõ ïóòåé:");
for (i=0; i < n; i++){
printf("\nÂåpøèíà: %d Ïpåäîê: %d Âåñ: %5.2lf",i+1,Q[i]+1,L[i]);
}
}
Òåñòîâûé ïðèìåð èç ðàáîòû [1] (ðèñ.8 íà ñòð. 12).
Àëãîpèòì ïîèñêà äåpåâà êpàò÷àéøèõ ïóòåé âî âçâåøåííîì ãpàôå.
Å.Äåéêñòpà, 1959 ã.
Ââåäèòå êîëè÷åñòâî âåpøèí.. 6
Ââåäèòå íà÷àëüíóþ âåpøèíó.. 6
Ââåäèòå ïîñëåäîâàòåëüíî âåñà påáåp äëÿ óêàçàííûõ âåpøèí èëè -1 äëÿ íåñìåæíûõ.
Âåpøèíû 1 è 2 2
Âåpøèíû 1 è 3 -1
Âåpøèíû 1 è 4 2
Âåpøèíû 1 è 5 -1
Âåpøèíû 1 è 6 5
Âåpøèíû 2 è 3 2
Âåpøèíû 2 è 4 -1
Âåpøèíû 2 è 5 2
Âåpøèíû 2 è 6 -1
Âåpøèíû 3 è 4 -1
Âåpøèíû 3 è 5 -1
Âåpøèíû 3 è 6 12
Âåpøèíû 4 è 5 1
Âåpøèíû 4 è 6 2
Âåpøèíû 5 è 6 5
Äåpåâî êpàò÷àéøèõ ïóòåé:
Âåpøèíà: 1 Ïpåäîê: 4 Âåñ:
Âåpøèíà: 2 Ïpåäîê: 5 Âåñ:
Âåpøèíà: 3 Ïpåäîê: 2 Âåñ:
Âåpøèíà: 4 Ïpåäîê: 6 Âåñ:
Âåpøèíà: 5 Ïpåäîê: 4 Âåñ:
Âåpøèíà: 6 Ïpåäîê: 6 Âåñ:
4.00
5.00
7.00
2.00
3.00
0.00
Òåñòîâûå ïðèìåðû:
Òåñòîâûé ñâÿçíûé âçâåøåííûé ãðàô
äëÿ àëãîðèòìà ïîèñêà îñòîâà ìèíèìàëüíîãî
âåñà (Ð.Ïðèì 1957ã.)
1
2
Ðåøåíèå: îñòîâ ìèíèìàëüíîãî âåñà
3
1
2
3
3
4
1
1
2
4
4
1
1
1
2
4
1
6
2
6
5
6
Òåñòîâûé ñâÿçíûé âçâåøåííûé ãðàô
äëÿ àëãîðèòìà ïîèñêà äåðåâà êðàò÷àéøèõ
ïóòåé èç âåðøèíû 6 (Å.Äåéêñòðà 1959ã.)
5
Ðåøåíèå: äåðåâî êðàò÷àéøèõ ïóòåé
èç âåðøèíû 6
1
1
2
2
4
5
2
6
(s)
5
2
1 5
2
4
2
2
2
2
1 5
2
2
12
6
3
(s)
3
Документ
Категория
Программирование, Базы данных
Просмотров
6
Размер файла
69 Кб
Теги
работа
1/--страниц
Пожаловаться на содержимое документа