Способы представления графа - EcsFlash/DataTypes GitHub Wiki

Есть два самых базовых представления графа, которыми мы и будем пользоваться в последующем:

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

image

В классе-графе мы храним матрицу n*n, где n - количество вершин в графе, а каждый элемент матрицы либо 0 либо 1. Возможно вместо 1 (означающей что две вершины i и j смежны) будет просто число >0, означающее длину ребра из вершины i в вершину j. Иногда мы будем пользоваться таким представлением. Класс графа, основанный на матрице смежности лежит тут: SimpleGraph.h

Как данное представление выглядит в коде:

class SimpleGraph {
	vector<vector<int>> kernel;
        const unsigned int std_offset;
        //some code here
public:
SimpleGraph(vector<vector<int>>& m): std_offset(1) {
	for (int i = 0; i < m.size(); i++) {
		if(m[i].size() != m.size()) {
			throw invalid_argument("kernel must be size of n * n, n > 0");
		}
	}
	this->kernel = m;
}

Что такое std_offset? Это параметр, отвечающий за синхронизацию "человеческих" численных названий вершин и тех, которые будут использоваться внутри класса. Например мы хотим стартовать с вершины номер 1 => start = 1. Но так как индексация векторов, массивов и других структур данных начинается с 0, то нам необходимо сделать start -= std_offset и приступать к дальнейшим вычислениям. В данном случае std_offset захардкожен, однако например его можно поместить как параметр в конструктор класса и позволить пользователю задать его равным, например 65, что будет означать что для обозначения вершин можно будет использовать буквы, а не числа.

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

image Тут уже есть несколько вариантов реализации:

  • Если мы хотим обращаться по индексам, постоянно делая поправку на std_offset:
class NotSimpleGraph{
     //some code here
     const unsigned int std_offset;
     vector<vector<int>> kernel;
     //and here
}
  • Если мы хотим делать чуть меньше поправок на std_offset:
class NotSimpleGraph{
     //some code here
     const unsigned int std_offset;
     vector<pair<int, vector<int>>> kernel; //тогда в iом элементе ядра будет: kernel[i].first - имя вершины,  kernel[i].second - её список смежности
     //and here
}
  • Мой любимый вариант(т. к вообще не нужен std_offset и можно точки до человечьи называть буковками)
class NotSimpleGraph{
     //some code here
     const unsigned int std_offset;
     map<char, vector<char>> kernel;
     //and here
}
  • Список ребер(хз как этим пользоваться)

image

class NotSimpleGraph{
     //some code here
     vector<pair<int, int>> kernel;
     //and here
}
  • Матрица инциндентности

Храним матрицу размером e*n(где e-количество ребер(дуг), n - количество вершин)

image

class NotSimpleGraph{
     //some code here
     vector<vector<int>> kernel;
     //and here
}
⚠️ **GitHub.com Fallback** ⚠️