Хранение графа: различия между версиями
Глеб (обсуждение | вклад) (Новая страница: «=Хранение графа в программе= Чаще всего в задачах по программмированию вершины графа - э...») |
(Добавлены иллюстрации) |
||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 6: | Строка 6: | ||
Для графа существуют несколько основных способов хранения: | Для графа существуют несколько основных способов хранения: | ||
| − | ==Матрица смежности | + | ==Матрица смежности== |
Давайте хранить двумерную матрицу $A_{nn}$, где для данного графа G верно, что если $A_{ij}$ = 1, то две вершины $i$ и $j$ являются смежными, иначе вершины $i$ и $j$ смежными не являются. | Давайте хранить двумерную матрицу $A_{nn}$, где для данного графа G верно, что если $A_{ij}$ = 1, то две вершины $i$ и $j$ являются смежными, иначе вершины $i$ и $j$ смежными не являются. | ||
| − | + | [[Файл:Graph-sample.png|400px|thumb|left|граф]] | |
| − | + | [[Файл: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: | ||
Плотные графы, имеющие большое количество ребер следует хранить при помощи матрицы смежности, а разреженные графы, имеющие малое количество ребер, оптимальнее при помощи списка. | Плотные графы, имеющие большое количество ребер следует хранить при помощи матрицы смежности, а разреженные графы, имеющие малое количество ребер, оптимальнее при помощи списка. | ||
| − | ==Список рёбер== | + | ==Список рёбер== |
Иногда граф явно вообще не требуется, а хватает хранить просто список ребер, который нам дают на вход. | Иногда граф явно вообще не требуется, а хватает хранить просто список ребер, который нам дают на вход. | ||
Заметьте, что все эти способы обобщаются на случай ориентированных графов - при этом матрица смежности становится неориентированной: если есть ребро из вершины $i$ в вершину $j$, то сделаем $A_{ij} = 1$, а $A_{ji} = 0$, если только нет обратного ребра тоже. А в списке смежности в ориентированном случае при считывании ребра $(u, v)$ будем добавлять только $v$ в список соседей $u$, но не наоборот. | Заметьте, что все эти способы обобщаются на случай ориентированных графов - при этом матрица смежности становится неориентированной: если есть ребро из вершины $i$ в вершину $j$, то сделаем $A_{ij} = 1$, а $A_{ji} = 0$, если только нет обратного ребра тоже. А в списке смежности в ориентированном случае при считывании ребра $(u, v)$ будем добавлять только $v$ в список соседей $u$, но не наоборот. | ||
| + | |||
| + | {{Автор|Глеб Лобанов|glebodin}} | ||
Текущая версия на 21:13, 4 ноября 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