Жұптар жиынын лексикографиялық түрде реттесе, жағдайды
әлдеқайда жақсартуға болады. Онда екілік іздеуді қолдануға болады.
Көптеген жағдайлардағы үздік шешім – инциденттілік тізімі деп
аталатын деректер құрылымы болып табылады. Оның әрбір v € V шыңы үшін
V —> и бағытталған граф үшін және v—u бағытталмаған граф үшін шыңдар
тізімі бар. Мұндай тізімнің әрбір элементі екі өрістен тұратын r жазбасы
болып табылады:
r.жол – граф шыңы;
r.кел - тізімдегі келесі жазбаға сілтеме.
Тізімдегі соңғы жазба үшін - r.кел = nil. Әрбір тізімнің басына сілтеме
БАСЫ кестесінде сақтаулы. Сөйтіп БАСЫ[v] – сәйкесінше бағытталған граф
үшін {и: (v, и)} жиынынан немесе бағытталмаған графтар үшін {и: {v, и}}
жиынындағы шыңдары бар тізімнің басына сілтеме болып табылады.
Толық тізімді (формалды түрде емес) ТІЗІМ[v] деп, ал осы тізімнің
әрбір элементіне жасалатын операцияларды орындайтын циклді
For u € ТІЗІМ[v]do... деп жазып алайық.
Бағытталмаған граф үшін әрбір { и, v} қабырғасы екі рет көрсетілген:
ТІЗІМ[u] тізіміндегі v шыңы арқылы және
ТІЗІМ[v] тізіміндегі u шыңы арқылы.
Біздің мысалдарымыз үшін ТІЗІМ[v], v € V инциденттілік тізімі былай
болады:
Көптеген алгоритмдерде граф құрылымы қабырғаларды қосу мен жою
арқылы динамикалық түрде модификацияланады. Мұндай жағдайларда
ТІЗІМ[u] тізіміндегі v шыңы бар элементте ТІЗІМ[v] тізіміндегі v шыңы бар
элементке сілтеме болады және тізімнің әрбір элементте келесі элементке
ғана емес, алдыңғы элементке де сілтемесі болады. Онда тізімнен қандай да
бір элементті жойған кезде шектелген қадам саны ішінде құрамында осы
элемент бар тізімді қарамай-ақ сол қабырғаны көрсететін басқа да элементті
жоюға болады.
Графтарды инциденттілік тізімдері арқылы көрсетуге қажетті жады
ұяшықтарының санының тәртібі (n + m).
Алгоритмдерді жазып алуға байланысты кейбір ұғымдарды
қарастырайық. Алгоритмдерді Паскаль тілінің негізгі құралдарын
қолданатын формалды емес тілде жазамыз. Егер алгоритмнің қандай да бір
бөлігінің іске асуы анық болса, ондай бөлікті табиғи тілде жазамыз. Сонымен
қоса кейбір формалды емес құралдарды қолданамыз, мысалы:
FOR x € X DO – Х жиынының барлық х элементтері
үшін Р операторын ерікті
ретпен орындау;
СТЕК <= х - х айнымалысының мәнін стекке салу;
х <= СТЕК -
стектің шыңындағы элементті оқып, оны
х айнымалысының мәні ретінде қабылдау ;
ОЧЕРЕДЬ<=х – х элементін кезекке соңғы элемент
ретінде енгізу;
х <= ОЧЕРЕДЬ – кезектің бірінші элементін алып, оны х
айнымалысының мәні ретінде қабылдау .
Әдетте айнымалылардың сипаттамаларын атамаймыз, тек кейде
түсініктемеге керекті анықтамаларды қосып отырамыз. Процедурада
болатын айнымалы берілген процедура үшін локалды болып есептеледі, егер
түсініктемеде басқа ештеңе айтылмаса. Программа жолдарын сәйкес циклге,
блокқа және т.б. сілтей алу үшін номерлеп отырамыз.
Кез-келген алгоритм үшін бізді оның есептеудегі күрделілігі
қызықтырады, яғни есеп көлемділігінен функцияның нашар жағдайдағы
қадам саны. Есеп көлемділігі деп |V| немес <|V|, |Е|> жұбын айтамыз. Онда
алгоритм күрделілігі f(n) – n шыңы бар ерікті граф үшін алгоритмнің ең көп
қадам саны немесе f(n , m) - n шыңы және m қабырғасы бар ерікті граф үшін
алгоритмнің ең көп қадам саны. Қадам ретінде кез-келген машиналық
команданы (сөзді жадыдан буферге көшіру және керісінше, арифметикалық
операцияларды орындау, шартты өтулер, енгізу-шығару, жанама адрестеу
және т.б.) айтуға болады. Алайда бізді тура мағынадағы күрделілік емес,
асимптоталық күрделілік, яғни есеп көлемділігінің шексіз өсуі кезіндегі
алгоритм қадамдарының өсу жылдамдығы қызықтырады. Онда күрделіліктің
сипаттамасы үшін мынандай белгілеулерді қолданған қолайлы:
f(n) =
f(n)≤C g(n) болатын С, N константалары бар
⇔
0(g(n)) кез-келген n≥N үшін
g(n) – қандай да бір берілген функция
f(n) =
f(n)≤C g(n) болатын С, N константалары бар
⇔
Ω(g(n)) кез-келген n≥N үшін
Оқылуы: 0(g(n)) - "g(n) артық емес ретпен"
Ω (g(n)) - "g(n) кем емес ретпен"
g(n,m) функциясы үшін дәл солай.
8.2 Графта тереңдікке іздеу
Графтан іздеу әдістеріне қойылатын негізгі талаптар:
1) әдіс бізді қызықтыратын есеп шешу алгоритмі арқылы оңай жүзеге
асу керек;
2) графтың әрбір қабырғасы бір рет (немесе шектеулі рет)
анализденеді.
Негізінде граф шыңдырын жүйелік талқылау жататын графтардағы
алгоритмдер көп және әрбір шың бір рет қана қаралады.
Көптеген
графтық
алгоритмдердің
негізі
болып
табылатын
бағытталмаған графтағы іздеу тәсілдердің бірін қарастырайық. Бұл әдіс
тереңдікке іздеу (depth first search) деп аталады.
Әдістің жалпы идеясы келесідей. Іздеуді қандай да бір тұрақталған v
0
шыңынан бастаймыз. Сосын v
0
сыбайлас u ерікті шыңын таңдап, u-дан бастап
қайтадан қарап шығамыз. Жалпы жағдайда біз қандай да бір v шыңында
тұрмыз делік. Егер жаңа (әлі қарастырылмаған) u, u-v шыңы бар болса, онда
біз сол шыңды қарастырамыз (енді ол жаңа емес), содан бастап, іздеуді
жалғастырамыз. Егер v-ге сыбайлас жаңа шың жоқ болса, v шыңы
қолданылды деп, v-ге түскен шыңға оралып, іздеуді жалғастырамыз (егер
v=v
0
, онда іздеу аяқталды).
Басқаша айтқанда, v шыңынан тереңдікке іздеу v-мен сыбайлас барлық
жаңа шыңдардан тереңдікке іздеуге негізделеді.
Бұны WG(v) рекурсивтік процедурасы арқылы оңай жазуға болады:
PROCEDURE WG(v); {v шыңынан тереңдікке іздеу}
{ЖАҢА, ТІЗІМ айным. - глобалды}
BEGIN v қарастыру; ЖАҢА[v]:- false;
FOR u
∈
ТІЗІМ [v] do
IF ЖАҢА[u] THEN WG(u)
END {шың қолданылды}
Ерікті, міндетті емес байланысқан графтағы тереңдікке іздеу процесі
келесі алгоритм бойынша жүргізіледі:
BEGIN
FOR v
∈
V DO ЖАҢА [v]:= true; {инициализациялау}
FOR v
∈
V DO
IF ЖАҢА [v] THEN WG(v)
END.
Бұл алгоритм әрбір шыңды тек бір рет қарап шығады және оның рет
күрделілігі O(n+m) болатынын көруге болады. Қосымша әрбір WG(v)
шақыруы құрамында v бар (егер олар әлі қаралмаса, яғни осы компонентаға
жататын
әрбір u шыңы
үшін
ЖАҢА[u]=true
болса)
граф
байланыстылығының компоненттерінің барлық шыңдарын шолуға әкеледі.
Сонымен қоса әрбір шың бір реттен артық қаралмайды.
Алгоритмнің өзі іздеуді кезек бойынша әр қаралмаған шыңнан
бастайды, яғни графтың (байланысты болуы міндетті емес) барлық шыңдары
қарастырылады.
Алгоритмнің күрделілігін бағалау үшін FOR (2,3 жолдар) (не считая
шагов, выполненных при вызове WG) циклдерінің екеуінде де қадам саны ≈n
(WG шақыруы кезіндегі қадамдарды ескермегенде). Бұл бағдарлама әрбір
шыңға барғаннан кейін оның көршілері үшін екінші циклде n реттен артық
орындалмайды, суммада (n+m) реттен артық емес. WG процедурасының
Достарыңызбен бөлісу: | 
