---
id: 587d8256367417b2b2512c79
title: 接続行列
challengeType: 1
forumTopicId: 301644
dashedName: incidence-matrix
---
# --description--
グラフを表すもう一つの方法は、 接続行列に入れることです。
接続行列 は二次元 (2D) 配列です。 一般に接続行列は、2 つの次元の間で 2 種類のクラスのオブジェクトを関連付けます。 このような行列は隣接行列に似ています。 しかし、行と列の意味がそれとは異なります。
グラフにはエッジとノードがあります。 この 2 つは、私たちが使う「オブジェクトの 2 種類のクラス」です。 この行列では、行がノード、列がエッジを表します。 したがって、行と列の数が違っていても構いません。
各列は一意のエッジを表します。 また、各エッジは 2 つのノードを接続します。 2 つのノードの間に 1 本のエッジがあることを示すために、特定の列の 2 行に 1 を入れます。 下に示したのは、ノード 1 とノード 3 の間に 1 本のエッジがある、3 ノードのグラフです。
1
---
1 | 1
2 | 0
3 | 1
4 本のエッジと 4 つのノードを持つ`接続行列`の例を示します。 列はエッジ、行はノード自体であることを思い出してください。
1 2 3 4
--------
1 | 0 1 1 1
2 | 1 1 0 0
3 | 1 0 0 1
4 | 0 0 1 0
次のコードは、同じことを JavaScript で実装したものです。
```js
var incMat = [
[0, 1, 1, 1],
[1, 1, 0, 0],
[1, 0, 0, 1],
[0, 0, 1, 0]
];
```
有向グラフを作成するには、特定のノードを離れるエッジに `-1` を使用し、ノードに入るエッジに `1` を使用します。
```js
var incMatDirected = [
[ 0, -1, 1, -1],
[-1, 1, 0, 0],
[ 1, 0, 0, 1],
[ 0, 0, -1, 0]
];
```
グラフのエッジに 重み を付けることもできます。 これまでに見てきたエッジは、単にエッジの有無が二項 (`0` または `1`) で表された、重み付けされていないエッジです。 用途によって重みを変えることができます。 異なる重みは 1 より大きい数字として表されます。
# --instructions--
5 つのノードと 4 本のエッジを持つ、無向グラフの接続行列を作成してください。 この行列は多次元配列でなければなりません。
これら 5 つのノードは次のような関係にあります。 1 本目のエッジは 1 番目と 2 番目のノードの間にあります。 2 本目のエッジは 2 番目と 3 番目のノードの間にあります。 3 本目のエッジは 3 番目と 5 番目のノードの間にあります。 4 本目のエッジは 4 番目と 2 番目のノードの間にあります。 すべてのエッジの重みは 1 であり、エッジの順序には意味があります。
# --hints--
`incMatUndirected` には 5 つのノードのみが含まれている必要があります。
```js
assert(
incMatUndirected.length === 5 &&
incMatUndirected
.map(function (x) {
return x.length === 4;
})
.reduce(function (a, b) {
return a && b;
})
);
```
1 番目と 2 番目のノードの間には 1 本目のエッジが必要です。
```js
assert(incMatUndirected[0][0] === 1 && incMatUndirected[1][0] === 1);
```
2 番目と 3 番目のノードの間には、2 本目のエッジが必要です。
```js
assert(incMatUndirected[1][1] === 1 && incMatUndirected[2][1] === 1);
```
3 番目と 5 番目のノードの間には、3 本目のエッジが必要です。
```js
assert(incMatUndirected[2][2] === 1 && incMatUndirected[4][2] === 1);
```
2 番目と 4 番目のノードの間には、4 本目のエッジが必要です。
```js
assert(incMatUndirected[1][3] === 1 && incMatUndirected[3][3] === 1);
```
# --seed--
## --seed-contents--
```js
var incMatUndirected = [
];
```
# --solutions--
```js
var incMatUndirected = [[1, 0, 0, 0],[1, 1, 0, 1],[0, 1, 1, 0],[0, 0, 0, 1],[0, 0, 1, 0]];
```