December 2016
Intermediate to advanced
440 pages
9h 44m
Japanese
Content preview from アルゴリズムクイックリファレンス 第2版
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
■
149
6
章
グラフアルゴリズム
グラフは、複雑な構造を持った情報を表すための基本的な構造だ。図6-1の画像
はいずれもグラフの例である。
本章では、グラフを表現する一般的な方法と、よく使われる関連アルゴリズムと
を検討する。本質的に、グラフは、節点（
vertex
）と呼ばれる要素の集合と、辺（
edge
）
と呼ばれる要素間の関係で構成される。本章では、この用語を一貫して使う。他に、
同じものを「ノード」および「リンク」という用語で表すことがある。本章では、単純
グラフ（
simple graph
）だけを考慮する。これは、
(a)
節点が自分自身への辺、すな
わちループ（
self edge
）を持たず、
(b)
同じ
2
節点間に多重辺を持たないグラフのこ
とを指す。
グラフの構造は辺によって定義される。そのため、多くの問題がグラフ内の
2
つの節点の間の最短経路問題に帰着する。ここで経路（
path
）の長さは、経路を
構成する辺の長さの総和と
して求められる。辺には重み（
weight
）と呼ばれる数値
が付随することも、（一方通行の道路のように）特定の方向が指定されている有向
（
directed
）のこともある。
単一始点最短経路
アルゴリズムでは、特定の節点
s
が与え
られ、そこから他のすべての節点への最短経路を計算する。
全対最短経路
アルゴリ
ズムでは、すべての節点対
(u, v)
について最短経路を計算する。
問題によっては、その背景にあるグラフ構造をより深く理解することが求められ
る。例えば、無向重み付きグラフの最小被覆木（
MST
）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.