Хранение графа: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Добавлены иллюстрации)
 
Строка 6: Строка 6:
  
 
Для графа существуют несколько основных способов хранения:
 
Для графа существуют несколько основных способов хранения:
==Матрица смежности.==
+
==Матрица смежности==
  
 
Давайте хранить двумерную матрицу $A_{nn}$, где для данного графа G верно, что если $A_{ij}$ = 1, то две вершины $i$ и $j$ являются смежными, иначе вершины $i$ и $j$ смежными не являются.
 
Давайте хранить двумерную матрицу $A_{nn}$, где для данного графа G верно, что если $A_{ij}$ = 1, то две вершины $i$ и $j$ являются смежными, иначе вершины $i$ и $j$ смежными не являются.
  
Граф G и Матрица смежности :
+
[[Файл:Graph-sample.png|400px|thumb|left|граф]]
  
(http://www.compendium.su/informatics/ege_1/ege_1.files/image026.jpg)
+
[[Файл:Adj-matrix.png|400px|thumb|left|Матрица смежности]]
 +
[[Файл:Adj-list.png|400px|thumb|left|Список смежности]]
 +
[[Файл:Edge-list.png|300px|thumb|left|Список ребер]]
  
 
Мы храним для каждой из $N$ вершин информацию, есть ли ребро в другие вершины, то есть  суммарно мы храним $N^2$  ячеек, а следовательно асимптотика по памяти - $O(N^2)$.
 
Мы храним для каждой из $N$ вершин информацию, есть ли ребро в другие вершины, то есть  суммарно мы храним $N^2$  ячеек, а следовательно асимптотика по памяти - $O(N^2)$.
  
==Список смежности.==
+
==Список смежности==
  
 
Давайте для каждой из $N$ вершин хранить все смежные с ней,  для этого нам потребуется любая динамическая структура, например vector в с++.
 
Давайте для каждой из $N$ вершин хранить все смежные с ней,  для этого нам потребуется любая динамическая структура, например vector в с++.
Строка 43: Строка 45:
 
Плотные графы, имеющие большое количество ребер следует хранить при помощи матрицы смежности, а разреженные графы, имеющие малое количество ребер, оптимальнее при помощи списка.
 
Плотные графы, имеющие большое количество ребер следует хранить при помощи матрицы смежности, а разреженные графы, имеющие малое количество ребер, оптимальнее при помощи списка.
  
==Список рёбер.==
+
==Список рёбер==
  
 
Иногда граф явно вообще не требуется, а хватает хранить просто список ребер, который нам дают на вход.
 
Иногда граф явно вообще не требуется, а хватает хранить просто список ребер, который нам дают на вход.

Текущая версия на 00:13, 5 ноября 2019

Хранение графа в программе

Чаще всего в задачах по программмированию вершины графа - это числа от $0$ до $N-1$, чтобы удобно было обращаться к ним как к индексам в разных массивах.

Также чаще всего вам дают считать граф как просто список всех рёбер в нем (но не всегда, конечно). Как оптимально считать и сохранить граф? Есть 3 способа.

Для графа существуют несколько основных способов хранения:

Матрица смежности

Давайте хранить двумерную матрицу $A_{nn}$, где для данного графа G верно, что если $A_{ij}$ = 1, то две вершины $i$ и $j$ являются смежными, иначе вершины $i$ и $j$ смежными не являются.

граф
Матрица смежности
Список смежности
Список ребер

Мы храним для каждой из $N$ вершин информацию, есть ли ребро в другие вершины, то есть суммарно мы храним $N^2$ ячеек, а следовательно асимптотика по памяти - $O(N^2)$.

Список смежности

Давайте для каждой из $N$ вершин хранить все смежные с ней, для этого нам потребуется любая динамическая структура, например vector в с++.

 1 // как сделать список по матрице
 2 vector<vector<int> > g(n);
 3 for (int i = 0; i < n; ++i){
 4     for (int j = 0;j < n;++j){
 5         cin >> a;
 6         if (a) g[i].push_back(j);
 7     }
 8 }
 9 // список по списку ребер
10 cin >> n >> m;
11 vector<vector<int> > g(n);
12 for (int i = 0; i < m; ++i){
13   cin >> v1 >> v2;
14   g[v1].push_back(v2);
15   g[v2].push_back(v1);
16 }

Здесь асимптотика по памяти и времени считывания - $O(N + M)$, так как мы храним для каждой вершины, куда есть ребра, то есть $2 M$ ребер, а также суммарно $N$ векторов.

Плотные графы, имеющие большое количество ребер следует хранить при помощи матрицы смежности, а разреженные графы, имеющие малое количество ребер, оптимальнее при помощи списка.

Список рёбер

Иногда граф явно вообще не требуется, а хватает хранить просто список ребер, который нам дают на вход.

Заметьте, что все эти способы обобщаются на случай ориентированных графов - при этом матрица смежности становится неориентированной: если есть ребро из вершины $i$ в вершину $j$, то сделаем $A_{ij} = 1$, а $A_{ji} = 0$, если только нет обратного ребра тоже. А в списке смежности в ориентированном случае при считывании ребра $(u, v)$ будем добавлять только $v$ в список соседей $u$, но не наоборот.



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin