Матрица смежности - хранит связи вершин графа 1 +---+ const graph = [
+--------------+ B +--+ [0, 1, 1, 0, 1],
| +---+ | [1, 0, 0, 1, 0],
| | [1, 0, 0, 1, 0],
+-+-+ 2 | [0, 1, 1, 0, 0],
| A +----------+ |3 [1, 0, 0, 0, 0],
+-+-+ | | ];
| | |
| +-+-+ | const graph = {
|5 | C | | A: [0, 1, 1, 0, 1],
| +-+-+ | B: [1, 0, 0, 1, 0],
+--+ | | C: [1, 0, 0, 1, 0],
| | | D: [0, 1, 1, 0, 0],
+-+-+ 4 | +-+-+ E: [1, 0, 0, 0, 0],
| E | +------+ D | };
+---+ +---+
Матрица смежности в виде плоского массива 1 +---+ const graph = [
+--------------+ B +--+ 0, 1, 1, 0, 1,
| +---+ | 1, 0, 0, 1, 0,
| | 1, 0, 0, 1, 0,
+-+-+ 2 | 0, 1, 1, 0, 0,
| A +----------+ |3 1, 0, 0, 0, 0,
+-+-+ | | ];
| | |
| +-+-+ |
|5 | C | |
| +-+-+ |
+--+ | |
| | |
+-+-+ 4 | +-+-+
| E | +------+ D |
+---+ +---+
Матрица инцидентности - связь вершин (строки) с дугами (колонки) 1 +---+ const graph = [
+--------------+ B +--+ [1, 1, 0, 0, 1],
| +---+ | [1, 0, 1, 0, 0],
| | [0, 1, 0, 1, 0],
+-+-+ 2 | [0, 0, 1, 1, 0],
| A +----------+ |3 [0, 0, 0, 0, 1],
+-+-+ | | ];
| | |
| +-+-+ | const graph = {
|5 | C | | A: [1, 1, 0, 0, 1],
| +-+-+ | B: [1, 0, 1, 0, 0],
+--+ | | C: [0, 1, 0, 1, 0],
| | | D: [0, 0, 1, 1, 0],
+-+-+ 4 | +-+-+ E: [0, 0, 0, 0, 1],
| E | +------+ D | ];
+---+ +---+
Список смежности - список вершин, для каждой списк смежных вершин 1 +---+ const graph = {
+--------------+ B +--+ A: [],
| +---+ | B: [],
| | C: [],
+-+-+ 2 | D: [],
| A +----------+ |3 E: [],
+-+-+ | | };
| | |
| +-+-+ | const { A, B, C, D, E } = graph;
|5 | C | | A.push(B, C, E);
| +-+-+ | B.push(A, D);
+--+ | | C.push(A, D);
| | | D.push(B, C);
+-+-+ 4 | +-+-+ E.push(A);
| E | +------+ D |
+---+ +---+ console.dir({ graph });
Список ребер - список с указанием ребра как пары вершин 1 +---+ const graph = [
+--------------+ B +--+ [A, B],
| +---+ | [A, C],
| | [B, D],
+-+-+ 2 | [C, D],
| A +----------+ |3 [A, E],
+-+-+ | | ];
| | |
| +-+-+ | const graph = [
|5 | C | | { from: A, to: B },
| +-+-+ | { from: A, to: C },
+--+ | | { from: B, to: D },
| | | { from: C, to: D },
+-+-+ 4 | +-+-+ { from: A, to: E },
| E | +------+ D | ];
+---+ +---+