## Матрица смежности - хранит связи вершин графа ``` 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 | ]; +---+ +---+ ```