www.wikidata.uk-ua.nina.az

Граф абстрактний тип даних В інформатиці граф це абстрактний тип даних який призначений для реалізації концепцій неорієн

Граф (абстрактний тип даних)

В інформатиці граф — це абстрактний тип даних, який призначений для реалізації концепцій неорієнтованого і орієнтованого графів, які походять з математики, а саме, з теорії графів.

Орієнтований граф з трьома вершинами (сині кола) та трьома ребрами (чорні стрілки).

Структура даних графів складається зі скінченної (можливо, змінної) множини вершин (також, вони можуть називатися вузлами або точками) разом із множиною невпорядкованих пар цих вершин для неорієнтованого графу або множини впорядкованих пар для орієнтованого графу. Ці пари відомі як ребра (їх також називають зв'язками або відрізками), а для орієнтованого графу також відомі як стрілки. Вершини можуть бути частиною структури графу, або можуть бути зовнішніми об'єктами, представленими цілими індексами або посиланнями.

Структура даних у графах також може пов'язувати з кожним ребром якесь значення ребра, таке як символьний або числовий атрибут (вартість, місткість, довжина, тощо).

Операції ред.

Основні операції, передбачені структурою даних графів G:

  • суміжність(G, x, y): перевіряє наявність ребра між вершиною x та вершиною y;
  • сусідство(G, x): перераховує всі вершини y такі, які мають ребро з вершиною x;
  • додати_вершину(G, x): додає вершину x, якщо її немає;
  • видалити_вершину(G, x): видаляє вершину x, якщо вона є;
  • додати_ребро(G, x, y): додає ребро від вершини x до вершини y, якщо його немає;
  • видалити_ребро(G, x, y): видаляє ребро від вершини x до вершини y, якщо воно є;
  • отримати_значення_вершини(G, x): повертає значення, пов'язане з вершиною x ;
  • задати_значення_вершини(G, x, v): встановлює значення, пов'язане з вершиною x на v .

Структури, які приписують значення ребрам:

  • отримати_значення_ребра(G, x, y): повертає значення, пов'язане з ребром (x, y);
  • задати_значення_ребра(G, x, y, v): встановлює значення, пов'язане з ребром (x, y), на v.

Структури даних для представлення ред.

На практиці використовуються різні структури даних для представлення графів:

У наступній таблиці наведена часову складність для виконання різних операцій над графами з |V | кількістю вершин і |Е | кількістю ребер залежно від способу представлення. У матричних представленнях записи дають вартість операції для наступного ребра. Вартість для ребер, яких немає, вважається нескінченною.

Список суміжності Матриця суміжності Матриця інцидентності
Зберігати граф
Додати вершину
Додати ребро
Видалити вершину
Видалити ребро
Чи суміжні вершини x і y (якщо вважати, що місця їх зберігання відомі)?
Зауваження Повільно видаляє вершини та ребра, тому що потрібно знаходити всі вершини чи ребра Повільно додає або видаляє вершини, тому що матрицю потрібно змінювати розмір/копіювати Повільно додає або видаляє вершини та ребра, тому що матрицю потрібно змінювати розмір/копіювати

Списки суміжності зазвичай є ефективнішими, оскільки вони краще представляють розріджені графи. Матриця суміжності є ефективнішою, якщо граф є щільним, тобто кількість ребер |Е| близька до квадрату кількості вершин — |V|2, або якщо потрібно швидко знайти ребро, яке з'єднує дві вершини.

Див. також ред.

Примітки ред.

  1. ↑ Див., наприклад Goodrich та Tamassia, (2015), Section 13.1.2: Operations on graphs, p. 360. Для більш детального набору операцій, див. Mehlhorn, K.; Näher, S. (1999). Chapter 6: Graphs and their data structures. LEDA: A platform for combinatorial and geometric computing. Cambridge University Press. с. 240–282. 
  2. Cormen та ін., (2001), pp. 528—529; Goodrich та Tamassia, (2015), pp. 361—362.
  3. Cormen та ін., (2001), pp. 529—530; Goodrich та Tamassia, (2015), p. 363.
  4. Cormen та ін., (2001), Exercise 22.1-7, p. 531.
  5. Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2001) [1990]. Section 22.1: Representations of graphs. Вступ до алгоритмів (вид. 2nd). MIT Press і McGraw-Hill. с. 527–531. ISBN 0-262-03293-7. .
  6. Goodrich, Michael T.; Tamassia, Roberto (2015). Section 13.1: Graph terminology and representations. Algorithm Design and Applications. Wiley. с. 355–364. .

Посилання ред.

Вікісховище має мультимедійні дані за темою: Граф (абстрактний тип даних)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
V informatici graf ce abstraktnij tip danih yakij priznachenij dlya realizaciyi koncepcij neoriyentovanogo i oriyentovanogo grafiv yaki pohodyat z matematiki a same z teoriyi grafiv Oriyentovanij graf z troma vershinami sini kola ta troma rebrami chorni strilki Struktura danih grafiv skladayetsya zi skinchennoyi mozhlivo zminnoyi mnozhini vershin takozh voni mozhut nazivatisya vuzlami abo tochkami razom iz mnozhinoyu nevporyadkovanih par cih vershin dlya neoriyentovanogo grafu abo mnozhini vporyadkovanih par dlya oriyentovanogo grafu Ci pari vidomi yak rebra yih takozh nazivayut zv yazkami abo vidrizkami a dlya oriyentovanogo grafu takozh vidomi yak strilki Vershini mozhut buti chastinoyu strukturi grafu abo mozhut buti zovnishnimi ob yektami predstavlenimi cilimi indeksami abo posilannyami Struktura danih u grafah takozh mozhe pov yazuvati z kozhnim rebrom yakes znachennya rebra take yak simvolnij abo chislovij atribut vartist mistkist dovzhina tosho Zmist 1 Operaciyi 2 Strukturi danih dlya predstavlennya 3 Div takozh 4 Primitki 5 PosilannyaOperaciyi red Osnovni operaciyi peredbacheni strukturoyu danih grafiv G 1 sumizhnist G x y pereviryaye nayavnist rebra mizh vershinoyu x ta vershinoyu y susidstvo G x pererahovuye vsi vershini y taki yaki mayut rebro z vershinoyu x dodati vershinu G x dodaye vershinu x yaksho yiyi nemaye vidaliti vershinu G x vidalyaye vershinu x yaksho vona ye dodati rebro G x y dodaye rebro vid vershini x do vershini y yaksho jogo nemaye vidaliti rebro G x y vidalyaye rebro vid vershini x do vershini y yaksho vono ye otrimati znachennya vershini G x povertaye znachennya pov yazane z vershinoyu x zadati znachennya vershini G x v vstanovlyuye znachennya pov yazane z vershinoyu x na v Strukturi yaki pripisuyut znachennya rebram 1 otrimati znachennya rebra G x y povertaye znachennya pov yazane z rebrom x y zadati znachennya rebra G x y v vstanovlyuye znachennya pov yazane z rebrom x y na v Strukturi danih dlya predstavlennya red Na praktici vikoristovuyutsya rizni strukturi danih dlya predstavlennya grafiv Spisok sumizhnosti en 2 Vershini zberigayutsya u viglyadi zapisiv abo ob yektiv i kozhna vershina zberigaye spisok sumizhnih vershin Cya struktura danih dozvolyaye zberigati dodatkovi dani u vershinah Dodatkovi dani mozhut buti zberezheni yaksho rebra takozh zberezheni yak ob yekti i v comu vipadku kozhna vershina zberigaye incidentni yij rebra a kozhne rebro zberigaye incidentni jomu vershini Matricya sumizhnosti 3 Dvovimirna matricya v yakij ryadki predstavlyayut pochatkovi vershini a stovpci kincevi vershini Dani pro rebra ta vershini povinni zberigatisya okremo Mizh kozhnoyu paroyu vershin mozhe zberigatisya lishe odne rebro Matricya incidentnosti 4 Dvovimirna buleva matricya v yakij ryadki predstavlyayut vershini a stovpci rebra Zapisi vkazuyut chi bude vershina v ryadku incidentnoyu rebru u stovpchiku U nastupnij tablici navedena chasovu skladnist dlya vikonannya riznih operacij nad grafami z V kilkistyu vershin i E kilkistyu reber zalezhno vid sposobu predstavlennya U matrichnih predstavlennyah zapisi dayut vartist operaciyi dlya nastupnogo rebra Vartist dlya reber yakih nemaye vvazhayetsya neskinchennoyu Spisok sumizhnosti Matricya sumizhnosti Matricya incidentnostiZberigati graf O V E displaystyle O V E nbsp O V 2 displaystyle O V 2 nbsp O V E displaystyle O V cdot E nbsp Dodati vershinu O 1 displaystyle O 1 nbsp O V 2 displaystyle O V 2 nbsp O V E displaystyle O V cdot E nbsp Dodati rebro O 1 displaystyle O 1 nbsp O 1 displaystyle O 1 nbsp O V E displaystyle O V cdot E nbsp Vidaliti vershinu O E displaystyle O E nbsp O V 2 displaystyle O V 2 nbsp O V E displaystyle O V cdot E nbsp Vidaliti rebro O V displaystyle O V nbsp O 1 displaystyle O 1 nbsp O V E displaystyle O V cdot E nbsp Chi sumizhni vershini x i y yaksho vvazhati sho miscya yih zberigannya vidomi O V displaystyle O V nbsp O 1 displaystyle O 1 nbsp O E displaystyle O E nbsp Zauvazhennya Povilno vidalyaye vershini ta rebra tomu sho potribno znahoditi vsi vershini chi rebra Povilno dodaye abo vidalyaye vershini tomu sho matricyu potribno zminyuvati rozmir kopiyuvati Povilno dodaye abo vidalyaye vershini ta rebra tomu sho matricyu potribno zminyuvati rozmir kopiyuvatiSpiski sumizhnosti zazvichaj ye efektivnishimi oskilki voni krashe predstavlyayut rozridzheni grafi Matricya sumizhnosti ye efektivnishoyu yaksho graf ye shilnim tobto kilkist reber E blizka do kvadratu kilkosti vershin V 2 abo yaksho potribno shvidko znajti rebro yake z yednuye dvi vershini 5 6 Div takozh red Poshuk po grafu dlya obhodu grafiv Grafova baza danih dlya zberezhennya grafiv struktur danih Perepisuvannya grafu en dlya peretvoren grafiv zasnovanih na pravilah Programne zabezpechennya dlya zobrazhennya grafivPrimitki red a b Div napriklad Goodrich ta Tamassia 2015 Section 13 1 2 Operations on graphs p 360 Dlya bilsh detalnogo naboru operacij div Mehlhorn K Naher S 1999 Chapter 6 Graphs and their data structures LEDA A platform for combinatorial and geometric computing Cambridge University Press s 240 282 Cormen ta in 2001 pp 528 529 Goodrich ta Tamassia 2015 pp 361 362 Cormen ta in 2001 pp 529 530 Goodrich ta Tamassia 2015 p 363 Cormen ta in 2001 Exercise 22 1 7 p 531 Tomas Kormen Charlz Lejzerson Ronald Rivest Kliford Stajn 2001 1990 Section 22 1 Representations of graphs Vstup do algoritmiv vid 2nd MIT Press i McGraw Hill s 527 531 ISBN 0 262 03293 7 Goodrich Michael T Tamassia Roberto 2015 Section 13 1 Graph terminology and representations Algorithm Design and Applications Wiley s 355 364 Posilannya red Vikishovishe maye multimedijni dani za temoyu Graf abstraktnij tip danih Boost Graph Library potuzhna biblioteka na C dlya roboti z grafami Arhivovano 17 travnya 2008 u Wayback Machine div Boost Paket Networkx dlya pobudovi grafiv na Python Arhivovano 10 bereznya 2013 u Wayback Machine div NetworkX GraphMatcher Arhivovano 5 lyutogo 2020 u Wayback Machine programa na Java dlya virivnyuvannya ne oriyentovanih grafiv GraphBLAS Arhivovano 21 veresnya 2016 u Wayback Machine specifikaciya interfejsu biblioteki dlya operacij nad grafami z akcentom na rozridzheni grafi Otrimano z https uk wikipedia org w index php title Graf abstraktnij tip danih amp oldid 36145309