Ïîñòàíîâêà ëàáîðàòîðíîé ðàáîòû ïî òåîèè ãðàôîâ (àëãîðèòìû è ïðîãðàììû)

Ïîñòàíîâêà ëàáîðàòîðíîé ðàáîòû ïî òåîèè ãðàôîâ (àëãîðèòìû è ïðîãðàììû)

Ïîñòàíîâêà ëàáîðàòîðíîé ðàáîòû ïî òåîðèè ãðàôîâ

(àëãîðèòìû è ïðîãðàììû)

1. Ââåäåíèå

      ïîñëåäíåå âðåìÿ èññëåäîâàíèÿ â îáëàñòÿõ, òðàäèöèîííî îòíîñÿùèõñÿ ê äèñêðåòíîé ìàòåìàòèêå, çàíèìàþò âñå áîëåå çàìåòíîå ìåñòî. Íàðÿäó ñ òàêèìè êëàññè÷åñêèìè ðàçäåëàìè ìàòåìàòèêè, êàê ìàòåìàòè÷åñêèé àíàëèç, äèôôåðåíöèàëüíûå óðàâíåíèÿ, â ó÷åáíûõ ïëàíàõ ñïåöèàëüíîñòè "Ïðèêëàäíàÿ ìàòåìàòèêà" è ìíîãèõ äðóãèõ ñïåöèàëüíîñòåé ïîÿâèëèñü ðàçäåëû ïî ìàòåìàòè÷åñêîé ëîãèêå, àëãåáðå, êîìáèíàòîðèêå è òåîðèè ãðàôîâ. Ïðè÷èíû ýòîãî íåòðóäíî ïîíÿòü, ïðîñòî îáîçíà÷èâ êðóã çàäà÷, ðåøàåìûõ íà áàçå ýòîãî ìàòåìàòè÷åñêîãî àïïàðàòà (ñì. ï.1.3 äàííîãî ðàçäåëà).

1.1 Îñíîâíûå ïîíÿòèÿ òåîðèè ãðàôîâ.

     Äåòàëüíûå îïðåäåëåíèÿ òåîðèè ãðàôîâ ìîæíî íàéòè â ðàáîòàõ [2, 3, 4, 5, 6]. Çäåñü ìû ëèøü îãðàíè÷èìñÿ ïåðå÷èñëåíèåì íåêîòîðûõ òåðìèíîâ, êîòîðûå áóäóò âñòðå÷àòüñÿ â äàëüíåéøåì, è èõ êðàòêèì îïèñàíèåì.

     Ãðàô- íåïóñòîå ìíîæåñòâî V è X- íåêîòîðûé íàáîð ïàð ýëåìåíòîâ èç V. Ýëåìåíòû ìíîæåñòâà V íàçûâàþòñÿ âåðøèíàìè, à ýëåìåíòû íàáîðà X- ðåáðàìè.

     Ïîäãðàô- ïîäãðàôîì ãðàôà G íàçûâàåòñÿ ãðàô, âñå âåðøèíû è ðåáðà êîòîðîãî ñîäåðæàòñÿ ñðåäè âåðøèí è ðåáåð ãðàôà G. Îñòîâíûé ïîäãðàô ñîäåðæèò âñå âåðøèíû ãðàôà G.

     Ñâÿçíûé ãðàô- ãðàô, ó êîòîðîãî äëÿ ëþáûõ äâóõ ðàçëè÷íûõ âåðøèí ñóùåñòâóåò öåïü (ïîñëåäîâàòåëüíîñòü ñìåæíûõ âåðøèí), ñîåäèíÿþùàÿ èõ.

     Âçâåøåííûé ñâÿçíûé ãðàô- ñâÿçíûé ãðàô, ñ çàäàííîé âåñîâîé ôóíêöèåé (êàæäîìó ýëåìåíòó íàáîðà X ñòàâèòñÿ â ñîîòâåòñòâèå íåêîòîðîå ÷èñëî - âåñ ðåáðà).

     Äåðåâî- ñâÿçíûé ãðàô, íå ñîäåðæàùèé öèêëîâ.

     Îñòîâ- îñòîâíûé ïîäãðàô, ÿâëÿþùèéñÿ äåðåâîì.

1.2 Ñïîñîáû çàäàíèÿ ãðàôîâ.

     Ñóùåñòâóåò ðÿä ñïîñîáîâ çàäàíèÿ ãðàôîâ. Äëÿ ðåøåíèÿ êîíêðåòíîé çàäà÷è ìîæíî âûáðàòü òîò èëè èíîé ñïîñîá, â çàâèñèìîñòè îò óäîáñòâà åãî ïðèìåíåíèÿ. Çäåñü ìû ïåðå÷èñëèì íåêîòîðûå, íàèáîëåå èçâåñòíûå ñïîñîáû, äàäèì èõ êðàòêóþ õàðàêòåðèñòèêó ñ òî÷êè çðåíèÿ óäîáñòâà ââîäà è îáðàáîòêè íà ÝÂÌ.

     Ìàòðèöà èíöèäåíòíîñòè- ìàòðèöà ðàçìåðîì  (n- ÷èñëî âåðøèí, m- ÷èñëî ðåáåð), ýëåìåíòû êîòîðîé ðàâíû 1, åñëè i-ÿ âåðøèíà èíöèäåíòíà j-ìó ðåáðó, è 0 â ïðîòèâíîì ñëó÷àå.

     Ìàòðèöà èíöèäåíòíîñòè íåóäîáíà äëÿ ââîäà è îáðàáîòêè íà ÝÂÌ, êðîìå òîãî îíà íå íåñåò ïðÿìîé èíôîðìàöèè î ðåáðàõ.

     Ìàòðèöà ñìåæíîñòè- ìàòðèöà ðàçìåðîì , ýëåìåíòû êîòîðîé ðàâíû 1, åñëè i-ÿ âåðøèíà ñìåæíà ñ j-îé, è 0 â ïðîòèâíîì ñëó÷àå.

     Ìàòðèöà ñìåæíîñòè ÿâëÿåòñÿ ñèììåòðè÷íîé è äîñòàòî÷íî ïðîñòî ìîæåò èñïîëüçîâàòüñÿ äëÿ ââîäà è îáðàáîòêè íà ÝÂÌ. Äëÿ ñëó÷àÿ âçâåøåííîãî ãðàôà âìåñòî 1 èñïîëüçóåòñÿ çíà÷åíèå âåñîâîé ôóíêöèè è òàêàÿ ìàòðèöà íàçûâàåòñÿ ìàòðèöåé âåñîâ.

     Ñïèñêè ñìåæíîñòè- êàæäûé i-é ñïèñîê ñîäåðæèò íîìåðà âåðøèí, ñìåæíûõ i-îé âåðøèíå.

     Ñïèñêè ñìåæíîñòè óäîáíû äëÿ ââîäà â ÝÂÌ, ýêîíîìÿò ïàìÿòü, íî íå ìîãóò èñïîëüçîâàòüñÿ â ñëó÷àå âçâåøåííîãî ãðàôà.

1.3 Îáçîð çàäà÷ òåîðèè ãðàôîâ.

     Ðàçâèòèå òåîðèè ãðàôîâ â îñíîâíîì îáÿçàíî áîëüøîìó ÷èñëó âñåâîçìîæíûõ ïðèëîæåíèé. Ïî-âèäèìîìó, èç âñåõ ìàòåìàòè÷åñêèõ îáúåêòîâ ãðàôû çàíèìàþò îäíî èç ïåðâûõ ìåñò â êà÷åñòâå ôîðìàëüíûõ ìîäåëåé ðåàëüíûõ ñèñòåì.

     Ãðàôû íàøëè ïðèìåíåíèå ïðàêòè÷åñêè âî âñåõ îòðàñëÿõ íàó÷íûõ çíàíèé: ôèçèêå, áèîëîãèè, õèìèè, ìàòåìàòèêå, èñòîðèè, ëèíãâèñòèêå, ñîöèàëüíûõ íàóêàõ, òåõíèêå è ò.ï. Íàèáîëüøåé ïîïóëÿðíîñòüþ òåîðåòèêî-ãðàôîâûå ìîäåëè èñïîëüçóþòñÿ ïðè èññëåäîâàíèè êîììóíèêàöèîííûõ ñåòåé, ñèñòåì èíôîðìàòèêè, õèìè÷åñêèõ è ãåíåòè÷åñêèõ ñòðóêòóð, ýëåêòðè÷åñêèõ öåïåé è äðóãèõ ñèñòåì ñåòåâîé ñòðóêòóðû.

     Äàëåå ïåðå÷èñëèì íåêîòîðûå òèïîâûå çàäà÷è òåîðèè ãðàôîâ è èõ ïðèëîæåíèÿ:

     - Çàäà÷à î êðàò÷àéøåé öåïè

          çàìåíà îáîðóäîâàíèÿ

          ñîñòàâëåíèå ðàñïèñàíèÿ äâèæåíèÿ òðàíñïîðòíûõ ñðåäñòâ

          ðàçìåùåíèå ïóíêòîâ ñêîðîé ïîìîùè

          ðàçìåùåíèå òåëåôîííûõ ñòàíöèé

     - Çàäà÷à î ìàêñèìàëüíîì ïîòîêå

          àíàëèç ïðîïóñêíîé ñïîñîáíîñòè êîììóíèêàöèîííîé ñåòè

          îðãàíèçàöèÿ äâèæåíèÿ â äèíàìè÷åñêîé ñåòè

          îïòèìàëüíûé ïîäáîð èíòåíñèâíîñòåé âûïîëíåíèÿ ðàáîò

          ñèíòåç äâóõïîëþñíîé ñåòè ñ çàäàííîé ñòðóêòóðíîé íàäåæíîñòüþ

          çàäà÷à î ðàñïðåäåëåíèè ðàáîò

     - Çàäà÷à îá óïàêîâêàõ è ïîêðûòèÿõ

          îïòèìèçàöèÿ ñòðóêòóðû ÏÇÓ

          ðàçìåùåíèå äèñïåò÷åðñêèõ ïóíêòîâ ãîðîäñêîé òðàíñïîðòíîé ñåòè

     - Ðàñêðàñêà â ãðàôàõ

          ðàñïðåäåëåíèå ïàìÿòè â ÝÂÌ

          ïðîåêòèðîâàíèå ñåòåé òåëåâèçèîííîãî âåùàíèÿ

     - Ñâÿçíîñòü ãðàôîâ è ñåòåé

          ïðîåêòèðîâàíèå êðàò÷àéøåé êîììóíèêàöèîííîé ñåòè

          ñèíòåç ñòðóêòóðíî-íàäåæíîé ñåòè öèðêóëÿöèîííîé ñâÿçè

          àíàëèç íàäåæíîñòè ñòîõàñòè÷åñêèõ ñåòåé ñâÿçè

     - Èçîìîðôèçì ãðàôîâ è ñåòåé

          ñòðóêòóðíûé ñèíòåç ëèíåéíûõ èçáèðàòåëüíûõ öåïåé

          àâòîìàòèçàöèÿ êîíòðîëÿ ïðè ïðîåêòèðîâàíèè ÁÈÑ

     - Èçîìîðôíîå âõîæäåíèå è ïåðåñå÷åíèå ãðàôîâ

          ëîêàëèçàöèÿ íåèñïðàâíîñòè ñ ïîìîùüþ àëãîðèòìîâ ïîèñêà ÌÈÏÃ

          ïîêðûòèå ñõåìû çàäàííûì íàáîðîì òèïîâûõ ïîäñõåì

     - Àâòîìîðôèçì ãðàôîâ

          êîíñòðóêòèâíîå ïåðå÷èñëåíèå ñòðóêòóðíûõ èçîìåðîâ äëÿ

            ïðîèçâîäíûõ îðãàíè÷åñêèõ ñîåäèíåíèé

          ñèíòåç òåñòîâ öèôðîâûõ óñòðîéñòâ

2. Ïîñòàíîâêà çàäà÷è

2.1 Àëãîðèòì ïîèñêà îñòîâà ìèíèìàëüíîãî âåñà.

     Âî âçâåøåííîì ñâÿçíîì ãðàôå (G,f) íàéòè îñòîâ ìèíèìàëüíîãî âåñà. Òàêàÿ çàäà÷à ìîæåò èìåòü, íàïðèìåð, ñëåäóþùóþ èíòåðïðåòàöèþ. Èñõîäíûé ãðàô G åñòü ïðîåêòèðóåìàÿ ñèñòåìà äîðîã (ðåáðà ãðàôà), ñâÿçûâàþùèõ ãîðîäà íåêîòîðîé îáëàñòè (âåðøèíû ãðàôà). Ïóñòü âåñ ðåáðà f(x)- ñòîèìîñòü ñòðîèòåëüñòâà äîðîãè, ñîåäèíÿþùåé äâà ãîðîäà. Òðåáóåòñÿ ïîñòðîèòü ñèñòåìó äîðîã ìèíèìàëüíîé ñòîèìîñòè, ÷òîáû èç ëþáîãî ãîðîäà ìîæíî áûëî ïðîåõàòü â ëþáîé ãîðîä (èñêîìûé îñòîâíûé ïîäãðàô - ñâÿçíûé). Î÷åâèäíî, ðåøåíèå çàäà÷è ñóùåñòâóåò, è èñêîìûé îñòîâíûé ïîäãðàô ÿâëÿåòñÿ äåðåâîì. Îïèøåì îäèí èç âîçìîæíûõ àëãîðèòìîâ ðåøåíèÿ (Ð. Ïðèì 1957 ã.).

     Äàí ñâÿçíûé ãðàô  è âåñîâàÿ ôóíêöèÿ . Àëãîðèòì ñîñòîèò èç n-1 øàãà. íà êàæäîì øàãå ñòðîèòñÿ äåðåâî . Äåðåâî  ÿâëÿåòñÿ îñòîâîì ìèíèìàëüíîãî âåñà.

     1. Âûáèðàåì ðåáðî  ìèíèìàëüíîãî âåñà èç ìíîæåñòâà âñåõ ðåáåð X è ñòðîèì äåðåâî , ïîëàãàÿ åãî ñîñòîÿùèì èç ðåáðà  è äâóõ èíöèäåíòíûõ ðåáðó  âåðøèí.

     2. Åñëè äåðåâî  ïîðÿäêà  óæå ïîñòðîåíî, òî ñðåäè ðåáåð, ñîåäèíÿþùèõ âåðøèíû ýòîãî äåðåâà ñ âåðøèíàìè ãðàôà G, íå âõîäÿùèìè â , âûáåðåì ðåáðî  ìèíèìàëüíîãî âåñà. Ñòðîèì äåðåâî  ïðèñîåäèíÿÿ ê  ðåáðî  âìåñòå ñ åãî íå âõîäÿùèì â  êîíöîì.

     3. Åñëè i=n-1 , òî îñòîâ ìèíèìàëüíîãî âåñà  ïîñòðîåí, êîíåö. Èíà÷å ïåðåéòè ê ï.2.

2.2 Àëãîðèòì ïîèñêà äåðåâà êðàò÷àéøèõ ïóòåé.

     Ðàññìîòðèì çàäà÷ó î êðàò÷àéøåì ïóòè. Ïóñòü (G,f) - âçâåøåííûé ñâÿçíûé ãðàô. Âåñ f(x) ðåáðà x èíòåðïðåòèðóåì êàê ðàññòîÿíèå ìåæäó âåðøèíàìè, ñìåæíûìè äàííîìó ðåáðó. Äëÿ çàäàííîé íà÷àëüíîé âåðøèíû s è êîíå÷íîé âåðøèíû t èùåòñÿ ïðîñòàÿ öåïü, ñîåäèíÿþùàÿ s è t ìèíèìàëüíîãî âåñà. (s,t) - öåïü ìèíèìàëüíîãî âåñà íàçûâàþò êðàò÷àéøèì (s,t) - ïóòåì. Î÷åâèäíî, ðåøåíèå çàäà÷è ñóùåñòâóåò. Îïèøåì îäèí èç âîçìîæíûõ àëãîðèòìîâ ðåøåíèÿ (Å. Äåéêñòðà, 1959 ã.).

     Äàí ñâÿçíûé ãðàô  è âåñîâàÿ ôóíêöèÿ 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) - ïóòåé, ïðîõîäÿùèõ ÷åðåç âåðøèíû, ïîëó÷èâøèõ ê äàííîìó ìîìåíòó ïîñòîÿííûå ìåòêè. Ïîñëå ïîëó÷åíèÿ âåðøèíîé ïîñòîÿííîé ìåòêè (u)+, ñ ïîìîùüþ ïîñòîÿííûõ -ìåòîê óêàçûâàåòñÿ ïîñëåäîâàòåëüíîñòü âåðøèí, ñîñòàâëÿþùàÿ êðàò÷àéøèé (s,v) - ïóòü.

     1. Ïîëîæèòü l(s)+=0, ò.å. ñ÷èòàòü ýòó ìåòêó ïîñòîÿíîé, è l(v)= äëÿ âñåõ , ñ÷èòàÿ ýòè ìåòêè âðåìåííûìè. Ïðèíÿòü u=s.

     2. Äëÿ âñåõ  ñ âðåìåííûìè ìåòêàìè âûïîëíèòü: åñëè l(v)>l(u)+f(x) è (v)=u. Èíà÷å l(v) è (v) íå ìåíÿòü.

     3. Ïóñü V' - ìíîæåñòâî âåðøèí ñ âðåìåííûìè ìåòêàìè l. Íàéòè âåðøèíó 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);          /* Ââîä ìàòpèöû âåñîâ      */

int prim(int n, double* weigh);                             /* Àëãîpèòì ïîèñêà                   */

void print(int n, double* weigh);                         /* Âûâîä 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);                                         /* Ââîä ìàòpèöû âåñîâ            */

int deik(int n, int s, double* weigh, int* Q, double* L);            /* Àëãîpèòì ïîèñêà                   */

void print(int n, int* Q, double* L);                                             /* Âûâîä 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  Âåñ:  4.00

Âåpøèíà: 2  Ïpåäîê: 5  Âåñ:  5.00

Âåpøèíà: 3  Ïpåäîê: 2  Âåñ:  7.00

Âåpøèíà: 4  Ïpåäîê: 6  Âåñ:  2.00

Âåpøèíà: 5  Ïpåäîê: 4  Âåñ:  3.00

Âåpøèíà: 6  Ïpåäîê: 6  Âåñ:  0.00

Òåñòîâûå ïðèìåðû: