グラフ理論

nodeとedgeで構成される

node - edge - node と an edgeを共有するnodeは、neighborになる。

edgeは、有向と無向で区別する

幅優先探索

node A から node Bには経路があるか?

経路を辿っていけば、Bに到達するか?

node A から node B の最短経路は?

edgeの個数で順に、edge個数1のnodes, edge個数2のnodesと調べていく。

配列とハッシュで実装できる。

あるノードは、グラフの中では、ハッシュとして存在し、そのハッシュの値として、隣接ノードを配列で持つ。

アルゴリズムとしては

1. checkする人をqueueにいれる

2. queueからpop

3. 該当するかをcheck

4. 該当しなければ、隣接ノードを queueにpush

計算量は O(V+E), Vはノード数、Eはedge数

https://amzn.to/2GU5Wq7 https://gyazo.com/c7acfec00d1d493be2535514e550be63

なっとく! アルゴリズム