蟻本、グラフ

.グラフは頂点と辺からなる。頂点は対象を表し、図では点や円で描かれる。辺は二つの対象の結びつきを表し、図では2点を結ぶ線分として描かれる。頂点の集合がV,辺の集合がEであるようなグラフをG=(V,E)と表し、2点u,vを結ぶ辺をe=(u,v)と表します。

・グラフは大きくわけて2種類あります。辺に向きがないグラフを無向グラフ、辺に向きがあるグラフを有向グラフという。友人関係のグラフや路線図は無向グラフです。数の大小関係のグラフやフローチャートは有向グラフです。辺には様々な属性が付くことがあります。代表的なものに重みがあります。辺に重みの付いたグラフを重み付きグラフといいます。重みは問題によって、距離や時間や価格などさまざまに解釈されます。

以下、VとEを頂点と辺の集合、|V|と|E|を頂点と辺の個数とする。また、Vに０～|V|-1の番号が振られているとする。

隣接行列では|V|*|V|の二次元配列gでグラフを表現します。g[i][j]はi番の頂点とj番の頂点の関係を表すことになります。

無向グラフの場合は「i番の頂点とj番の頂点が辺で結ばれているか」の情報さえあれば良いので、g[i][j]とg[j][i]の値を頂点iとjが辺で結ばれているなら１、そうでなければ０とすることで無向グラフを表現することができます。

有向グラフの場合は頂点iから頂点jに向かう辺があるかの情報があればよくg[i][j]=g[j][i]とは限らない

重み付きグラフの場合はg[i][j]を頂点iから頂点jへの辺の重みとします。辺がないときは0を入れると重みが0の場合と区別がつかなくなるので適当に大きな定数INFを定義してg[i][j]=INFとしておく。

例
二部グラフ判定
頂点数nの無向グラフが与えられます。辺の数はmです。隣接している頂点同士が違う色になるように、頂点に色を塗っていきます。2色以外ですべての頂点を塗ることができるか判定してください。多重辺やループはないものとします。

二色で塗る場合、一つの頂点の色を決めれば隣接する頂点の色も一意的に決まります。従って、適当な頂点からはじめて隣接する頂点の色を順次決めていけば2色で塗れるかが判定できます。これは深さ優先探索を用いることで簡単に解くことができます。

```
#include<iostream>
#include<vector>
using namespace std;
const int MAX_N = 1010;
vector<int>G[MAX_N];//グラフ
int n;//頂点数
int m;//辺の数
int color[MAX_N];//頂点iの色
bool dfs(int v, int c) {
	color[v] = c;//頂点ｖをcで塗る
	for (int i = 0; i < G[v].size(); ++i) {
		//隣接している頂点が同じ色ならfalse
		if (color[G[v][i]] == c)return false;
		//隣接している頂点がまだ塗られていないなら-cで塗る
		if (color[G[v][i]] == 0 && !dfs(G[v][i], -c))return false;
	}
	//全ての頂点を塗れたらtrue
	return true;
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b; cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	for(int i=0;i<n;++i)
	if (color[i] == 0) {
		if (!dfs(i, 1)) {
			cout << "no";
			return 0;
		}
	}
	cout << "yes";
	return 0;
}
```
最短路問題
最短路問題はグラフの最も基本的な問題です。2頂点が与えられた時にその頂点を始点、終点とするようなパスのうちで、通る辺のコストの和を最小にするもののことです。コストを距離として最短距離を考えるとわかりやすいと思います。パズルを解く最小手段を求めることなども一種の最短路問題と言えます。

単一始点最短路問題１(ベルマンフォード法）
ベルマンフォード法
単一始点から他の各点への最短路を求める。負の長さの辺があってもOK。負閉路を持たない場合は高々V−1回しかループが実行されないことを用いると、負閉路の検出にも適用できる。d[j] = min(d[j], d[i] + cost[i][j])という処理を繰り返し、更新されなくなったら終了。
計算量: O(VE)
ダイクストラ法
基本的にはベルマンフォード法と同じだが、負の長さの辺があるときには使えない。その代り計算量が下がる。ベルマンフォード法の式を、最短経路が小さい点から確定させながら適用する。＊計算量: O(ElogV)
(プライオリティーキューを用いた場合)
ワーシャルフロイド法
上の2つとは異なり、全点最短路対を求める方法。簡単な3重ループで実現が可能だが、計算量は大きい。計算量: O(V＊＊3)

制約が緩いとき、全点間の最短路を求めたいとき→ワーシャルフロイド
制約がきついとき、始点が決まっているとき→ダイクストラ
負の長さの辺を含むとき→ベルマンフォード

```
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX_E 50
#define MAX_V 10
#define INF 1e9
struct edge { int from, to, cost; };
edge es[MAX_E];
vector<edge>G[MAX_V];
int d[MAX_V];//最短距離
int V, E;
void shortest_path(int s) {
	for (int i = 0; i < V; ++i) {
		d[i] = INF;
	}
	d[s] = 0;
	int c;
	while (true) {
		bool update = false;
		for (int i = 0; i < E; ++i) {
			edge e = es[i];
			if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				update = true;
			}
		}
		if (!update)break;
	}
}
//trueなら負の閉路が存在する
bool find_negative_loop() {
	memset(d, 0, sizeof(d));
	for (int i = 0; i < V; ++i) {
		for (int j = 0; j < E; ++j) {
			edge e = es[j];
			if (d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				if (i == V - 1)return true;
			}
		}
	}
	return false;
}


int main() {
	cin >> V >> E;
	for (int i = 0; i < E; ++i) {
		int from, to, cost;
		cin >> from >> to >> cost;
		es[i] = edge{ from,to,cost };
	}
	shortest_path(0);
	for (int i = 0; i < V; ++i) {
		if (d[i] != INF) {
			cout << "0から" << i << "までのコストは" << d[i] << endl;
		}
	}
	return 0;
}
```
有向グラフのベルマンフォード。

```
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX_E 50
#define MAX_V 10
#define INF 1e9
struct edge { int from, to, cost; };
edge es[MAX_E];
vector<edge>G[MAX_V];
int d[MAX_V];//最短距離
int V, E;
void shortest_path(int s) {
	for (int i = 0; i < V; ++i) {
		d[i] = INF;
	}
	d[s] = 0;
	int c;
	while (true) {
		bool update = false;
		for (int i = 0; i < 2*E; ++i) {
			edge e = es[i];
			if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				update = true;
			}
		}
		if (!update)break;
	}
}
//trueなら負の閉路が存在する
bool find_negative_loop() {
	memset(d, 0, sizeof(d));
	for (int i = 0; i < V; ++i) {
		for (int j = 0; j < E; ++j) {
			edge e = es[j];
			if (d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				if (i == V - 1)return true;
			}
		}
	}
	return false;
}


int main() {
	cin >> V >> E;
	for (int i = 0; i < E; ++i) {
		int from, to, cost;
		cin >> from >> to >> cost;
		es[i] = edge{ from,to,cost };
		es[E + i] = edge{ to,from,cost };
	}
	shortest_path(0);
	for (int i = 0; i < V; ++i) {
		if (d[i] != INF) {
			cout << "0から" << i << "までのコストは" << d[i] << endl;
		}
	}
	return 0;
}
```
無向グラフ版

```
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<list>
#include<cmath>
#include<map>
#include<queue>
#define F first
#define S second
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long;
using T = tuple<ll, int, int>;
const int INF = 1e9;
#define rep(i,n)for(int i=0;i<(n);++i)
#define p pair<int,int>
int cost[10][10];
int d[10];
bool used[10];
int V;
int E;
void dijkstra(int s) {
	fill(d, d + V, INF);
	fill(used, used + V, false);
	d[s] = 0;
	while (true) {
		int v = -1;
		for (int u = 0; u < V; ++u) {
			if (!used[u] && (v == -1 || d[u] < d[v]))v = u;
		}//使われていない頂点のうち距離が最小のものを探す
		if (v == -1)break;
		used[v] = true;
		for (int u = 0; u < V; ++u) {
			d[u] = min(d[u], d[v] + cost[v][u]);
		}
	}
}
int main() {
	cin >> V >> E;
	for (int i = 0; i < V; ++i) {
		for (int j = 0; j < V; ++j) {
			cost[i][j] = INF;
		}
	}
	for (int i = 0; i < E; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		cost[a][b] = c;
		cost[b][a] = c;
	}
	dijkstra(0);
	for (int i = 0; i < V; ++i) {
		cout << d[i] << endl;
	}
	return 0;
}
```
ダイクストラ実装

```
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<list>
#include<cmath>
#include<map>
#include<queue>
#define F first
#define S second
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long;
using T = tuple<ll, int, int>;
const int INF = 1e9;
#define rep(i,n)for(int i=0;i<(n);++i)
#define p pair<int,int>
using P = pair<int, int>;//firstは最短距離secondは頂点の番号
struct edge { int to, cost; };
int V, E;
vector<edge>G[10];
int d[10];
void dijkstra(int s) {
	priority_queue<P, vector<P>, greater<P>>que;
	fill(d, d + V, INF);
	d[s] = 0;
	que.push(P(0, s));
	while (!que.empty()) {
		p P = que.top(); que.pop();
		int v = P.second;
		if (d[v] < P.first)continue;
		for (int i = 0; i < G[v].size(); ++i) {
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(p(d[e.to], e.to));
			}
		}
	}
}
int main() {
	cin >> V >> E;
	for (int i = 0; i < E; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		G[a].push_back({ b,c });
		G[b].push_back({ a,c });
	}
	dijkstra(0);
	for (int i = 0; i < V; ++i) {
		cout << d[i] << endl;
	}
	return 0;
}
```
priority_queueを使った実装

経路復元問題

```