Способы представления графов. Матрица смежности

1. Способы представления графов

Рассмотрим ориентированный взвешенный граф

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

1
2
3
4
5
1
0
10
30
50
10
2
0
0
0
0
0
3
0
0
0
0
10
4
0
40
20
0
0
5
10
0
10
30
0

3.

#include <vector>
int main(){
// объявление одномерного массива размера n
vector<bool> used(n, false);
// объявление матрицы смежности размера nxn
vector<vector<int> > g(n, vector<int> (n, 0));
// обращение к элементу массива, 0<= i < n
used[i];
// обращение к элементу матрицы, 0<= i, j <n
g[i][j];
}

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

1
(2, 10)
(3, 30)
(5, 50)
2
3
(5, 10)
4
(2, 40)
(3, 20)
5
(1, 10)
(3, 10)
(4, 30)
(5, 10)

5.

#include <vector>
int main(){
// объявление списка смежности под n вершин
vector<vector<pair<int, int> > > g(n);
// вставка ребра (u, v) весом w
g[u].push_back(make_pair(v, w));
g[i].size(); // количество вершин смежных с вершиной i
g[i][j].first; // v
g[i][j].second; // w
// 0 <= j < g[i].size()
}

6. Список ребер

u
v
w
1
2
10
1
3
30
1
4
50
1
5
10
3
5
10
4
2
40
4
3
20
5
1
10
5
3
10
5
4
30

7.

#include <vector>
int main(){
// объявление списка ребер под n ребер
vector<pair<pair<int, int>, int> > e(n);
// вставка ребра (u, v) весом w с номером i
e[i] = make_pair(make_pair(u, v), w);
e[i].first; // (u, v)
e[i].first.first; // u
e[i].first.second; // v
e[i].second; // w
}