Составители:
Рубрика:
70
Ïîðÿäêîâàÿ ôóíêöèÿ ïîçâîëÿåò ïåðåíóìåðîâàòü âåðøèíû òàê, ÷òî
âåðøèíû óðîâíÿ N
i
èìåþò íîìåðà ìåíüøèå, ÷åì âåðøèíû óðîâíÿ N
i+1
(ðèñ. 4.6,á.). Ïîðÿäêîâàÿ ôóíêöèÿ èãðàåò âàæíóþ ðîëü âî ìíîãèõ êîì-
áèíàòîðíûõ çàäà÷àõ, íàïðèìåð ïîçâîëÿåò ðåøèòü çàäà÷ó âûáîðà ïðåä-
ïî÷òèòåëüíûõ îáúåêòîâ.
4.6.2. Îïèñàíèå ìàøèííîãî àëãîðèòìà ðàçáèåíèÿ ãðàôà
íà óðîâíè
Âîçìîæíûé âàðèàíò àëãîðèòìà âêëþ÷àåò ñëåäóþùèå øàãè.
1. Ââîä ìàòðèöû ñìåæíîñòè (S) ãðàôà è åå ðàçìåðà (n);
2. k=0; (íà÷àëüíûé íîìåð óðîâíÿ ðàçáèåíèÿ ãðàôà)
v=0; (ñ÷åò÷èê îáðàáîòàííûõ âåðøèí)
3. Öèêë j=1(1)n
C[j]=0; (îáíóëåíèå âåêòîðà Ñ)
4. Íà÷àëî öèêëà ïî v (öèêë ïî îáðàáàòûâàåìûì âåðøèíàì)
{ k0=0; (ñ÷åò÷èê íóëåâûõ ñòîëáöîâ â öèêëå îáðàáîòêè âåðøèí)
5. Öèêë j=1(1)n (çàïîëíåíèå âåêòîðîâ C è N)
6. { åñëè (C[j] ≠ 1) (âåðøèíà j íå îáðàáîòàíà )
{ sum=0; (íà÷àëî ñ÷åòà 1 äëÿ ñòîëáöà)
7. öèêë i=1(1)n
sum = sum+S[i,j]; (ñóììèðîâàíèå ñòîëáöà j)
8. åñëè (sum≠0) (ñòîëáåö j íå ïóñòîé)
C[j]=sum; (çàïîëíåíèå C
j
)
9. èíà÷å
{ C[j] = 1 ; (âåðøèíà îáðàáîòàíà)
N[j]=k ; (çàïèñü óðîâíÿ âåðøèíû)
v = v+1 ; (ïîäñ÷åò îáðàáîòàííûõ âåðøèí)
k0=k0+1; (ïîäñ÷åò íóëåâûõ ñòîëáöîâ)
}
} ( êîíåö öèêëà ïî j)
10. åñëè (k0 ≠ 0 ) (åñòü íóëåâûå ñòîëáöû)
11. { öèêë i=1(1)n (èñêëþ÷åíèå â S ñòðîê
îáðàáîòàííûõ âåðøèí)
12. { åñëè (N[i]=k) ( âåðøèíà i ïîïàëà íà óðîâåíü k)
13. öèêë j=1(1)n S[i,j]=0; ( îáíóëåíèå ñòðîêè i )
} (êîíåö öèêëà ïî i)
14. k=k+1; (ïîëó÷åíèå íîâîãî íîìåðà óðîâíÿ)
Страницы
- « первая
- ‹ предыдущая
- …
- 68
- 69
- 70
- 71
- 72
- …
- следующая ›
- последняя »
