Чаще всего в задачах по программированию вершины графа пронумерованы числами от $0$ до $(n-1)$, чтобы было удобно обращаться к ним как к индексам в разных массивах.
В задачах графы чаще всего задаются списком всех ребер, которые нужно считать из ввода. В каком формате оптимально хранить граф? В зависимости от задачи есть несколько способов.
#Список рёбер
Иногда достаточно хранить просто список ребер, которые нам дают на вход. Однако часто такой подход оказывается неэффективным для определенных операций.
Например, если мы хотим проверить, существует ли ребро между вершинами $a$ и $b$, в наивном случае нам нужно пройтись по всему списку в поисках такого ребра.
Чтобы избежать этого, можно задать этому списку какую-нибудь структуру. Например, можно отсортировать его сначала по первому элементу, а потом по второму, и тогда можно выполнять проверку бинарным поиском за $O(\log m)$. Можно пойти дальше и обернуть его в какую-нибудь структуру, например в бинарное дерево или, ещё лучше, хеш-таблицу, но в любом случае возникают некоторые неэффективности.
#Матрица смежности
Матрицей смежности называется двумерная матрица $G$ размера $n \times n$, в ячейке $G_{ij}$ которой хранится единица, если существует ребро $(i, j)$, и ноль в противном случае.
При реализации обычно создается обычный двумерный массив типа bool. Если для каждой из $n$ вершин мы храним информацию, существует ли ребро в каждую из остальных вершин, то суммарно мы храним $n^2$ ячеек, и, следовательно, асимптотика по памяти — $O(n^2)$.
В случае графов с кратными ребрами, иногда вместо нулей и единиц в матрице смежности хранят кратность соответствующего ребра.
Заметим, что в случае простых неориентированных графов, матрица смежности будет симметричной и иметь нули на главной диагонали.
Матрицы смежности очень эффективны для проверок — нужно считать и сравнить всего одну ячейку. Но что, если мы хотим для заданной вершины $v$ иметь возможность быстро пройтись по всем её соседям? Здесь ничего быстрее $O(n)$ не получится.
#Список смежности
Давайте теперь для каждой из $n$ вершин хранить не булевый массив, а номера всех смежных с ней вершин. Для этого нам потребуется любая динамическая структура, например std::vector в C++.
// если на вход идет матрица смежности
vector<vector<int>> g(n);
for (int i = 0; i < n; ++i){
for (int j = 0;j < n;++j){
cin >> a;
if (a)
g[i].push_back(j);
}
}
// если на вход идет список ребер
cin >> n >> m;
vector<vector<int>> g(n);
for (int i = 0; i < m; ++i){
cin >> v1 >> v2;
g[v1].push_back(v2);
g[v2].push_back(v1);
}
Здесь асимптотика по памяти и времени считывания - $O(n + m)$, так как мы храним суммарно $2m$ ребер и $n$ векторов.
Плотные графы, имеющие большое количество ребер, следует хранить при помощи матриц смежности, а разреженные графы, имеющие малое количество ребер, оптимальнее хранить при помощи списков смежности.