データ構造学習ノート＜7＞図

一、グラフ#

1. グラフとは何か#

「多対多」の関係を表し、以下を含む：

一組の頂点：通常 V (Vertex) で頂点集合を表す
一組の辺：通常 E (Edge) で辺の集合を表す
無向辺は頂点対：(v，w) ∈ E、ここで v，w∈V
有向辺 <v,w> は v から w への辺を表す（単行線）
重辺と自己ループは考慮しない

抽象データ型の定義#

型名：グラフ (Graph)
データオブジェクト集合：G (V,E) は非空の有限頂点集合 V と有限辺集合 E から構成される。
操作集合：任意のグラフ G ∈ Graph、および v ∈ V、e ∈ E に対して

Graph Create (): 空のグラフを作成して返す；
Graph InsertVertex (Graph G, Vertex v)：v 頂点をグラフ G に挿入する
Graph InsertEdge (Graph G, Edge e)：辺 e をグラフ G に挿入する
void DFS (Graph G, Vertex v)：頂点 v から深さ優先でグラフ G を遍歴する；
void BFS (Graph G, Vertex v)：頂点 v から幅優先でグラフ G を遍歴する；
void ShortestPath (Graph G, Vertex v, int Dist []): グラフ G における頂点 v から他の任意の頂点までの最短距離を計算する；
void MST (Graph G)：グラフ G の最小生成木を計算する
一般的な用語：
無向グラフ、有向グラフ、ネットワークなど……

プログラムでのグラフの表現方法#

隣接行列#

ここに画像の説明を挿入

隣接行列の利点

直感的で、シンプルで、理解しやすい
任意の頂点対間に辺が存在するかどうかを簡単に確認できる
任意の頂点のすべての「** 隣接点」（辺で直接接続されている頂点）** を簡単に見つけることができる
任意の頂点の「** 次数」（その点から出る辺の数は「出次数」、その点を指す辺の数は「入次数」）を簡単に計算できる
- 無向グラフは対応する行（または列）の非 0 要素の個数
- 有向グラフ：対応する行の非 0 要素の個数は出次数、対応する列の非 0 要素の個数は入次数

隣接リスト#

ポインタ配列 + 連結リスト、点が非常に疎な場合に非常に効率的
ここに画像の説明を挿入
隣接リストの利点：

任意の頂点のすべての「隣接点」（辺で直接接続されている頂点）を簡単に見つけることができる
疎グラフの空間を節約できる
- N 個のヘッダポインタ + 2E 個のノード（各ノードは少なくとも 2 つのフィールドを持つ）
無向グラフの任意の頂点の「次数」を計算するのが簡単だが、有向グラフでは出次数のみ計算できる。

2. グラフの遍歴#

DFS 深さ優先探索#

深さ優先探索 (Depth First Search,DFS) は、可能なすべての分岐パスを深く掘り下げ、もはや深く掘り下げられないところまで進むもので、各ノードは一度だけ訪問できる。
擬似コードの説明：

void DFS(Vertex V) {
	visited[V] = true;
	for(Vの各隣接点W)
		if (!visited[W])
			DFS(W);
}

BFS 幅優先探索#

幅優先探索 (Breadth First Search,BFS) は、キュー（先入れ先出し）を利用して実現する
擬似コードの説明：

void BFS(Vertex V) {
	visited[V] = true;
	Enqueue(V, Q);//その頂点をキューに入れる
	while(!IsEmpty(Q)) {//キューが空になるまで探索を終了
		V = Dequeue(Q);//Vはキューの先頭要素
		for(Vの各隣接点W) {
			if ( !visited[W] ) {
				visited[W] = true;//その点を訪問済みとしてマーク
				Enqueue(W, Q);//その点をキューにプッシュ
			}
		}
	}
}

グラフが非連結の場合はどうするか？#

パス：V から W へのパスは一連の頂点 {V，V1，V2，……，Vn，W} の集合であり、任意の隣接する頂点間にはグラフ内の辺が存在する。パスの長さはパス内の辺の数（重み付きの場合は、すべての辺の重みの合計）。V から W の間のすべての頂点が異なる場合、これを単純パスと呼ぶ
連結：V から W に無向パスが存在する場合、V と W は連結していると呼ばれる
ループ：始点と終点が同じパス
連結グラフ：グラフ内の任意の 2 頂点が連結している
連結成分：無向グラフの最大連結部分グラフ
- 最大頂点数：1 つの頂点を追加すると連結でなくなる
- 最大辺数：部分グラフ内のすべての頂点が接続されるすべての辺を含む
強連結：有向グラフにおいて頂点 V と W の間に双方向のパスが存在する場合、V と W は強連結していると呼ばれる
強連結グラフ：有向グラフ内の任意の 2 頂点が強連結している
強連結成分：有向グラフの最大強連結部分グラフ

DFS を 1 回呼び出すごとに、実際には V が所在する連結成分を一遍遍歴していることになる。BFS も同様である。

void ListComponents ( Graph G ) {//連結成分を遍歴する
	for (each V in G)
		if ( !visited[V] ) {
			DFS( V );
		}
}

3. グラフの構築方法#

(1) 隣接行列で表現されたグラフの構築#

定義#

const int MaxVertexNum = 100;
typedef int DataType;
typedef bool WeightType;
typedef struct GNode *PtrToGNode;
struct GNode {
    int Nv;//頂点数
    int Ne;//辺数
    WeightType G[MaxVertexNum][MaxVertexNum];
    DataType Data[MaxVertexNum];//頂点のデータを格納
};
typedef PtrToGNode MGraph;//隣接行列で保存されたグラフの型

初期化#

頂点数が VertexNum の辺がないグラフを初期化する

typedef int Vertex;
MGraph CreateGraph(int VertexNum) {
    Vertex V, W;
    MGraph Graph;
    Graph = (MGraph) malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    //頂点番号は0から始まり、Graph->Nv-1まで
    for (V = 0; V < Graph->Nv; V++) {
        for(W = 0; W < Graph->Nv; W++) {
            Graph->G[V][W] = 0; //有向グラフでは0をINFなどに変更可能
        }
    }
    return Graph;
}

グラフに辺を挿入する#

辺の定義

typedef struct ENode *PtrToENode;
struct ENode {
    Vertex V1, V2;//有向辺<V1,V2>
    WeightType Weight;//重み
};
typedef PtrToENode Edge;

挿入操作

void InsertEdge(MGraph Graph, Edge E) {
    //辺<V1,V2>を挿入
    Graph->G[E->V1][E->V2] = E->Weight;
    //無向グラフの場合、辺<V2,V1>も挿入する必要がある
    Graph->G[E->V2][E->V1] = E->Weight;
}

完全な MGraph の構築#

入力形式

Nv Ne
V1 V2 Weight
……

MGraph BuildGraph() {
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv;
    cin >> Nv;
    Graph = CreateGraph(Nv);//Nv個の頂点を持つグラフを構築
    cin >> Graph->Ne;//辺数Ne
    if(Graph->Ne != 0) {
        E = (Edge)malloc(sizeof(struct ENode));
        for (int i = 0; i < Graph->Ne; i++) {
            cin >> E->V1 >> E->V2 >> E->Weight;
            InsertEdge(Graph, E);
        }
    }
    //頂点にデータがある場合、データを読み込む
    for(V = 0; V < Graph->Nv; V++) {
        cin >> Graph->Data[V];
    }
    return Graph;
}

(2) 隣接リストで表現されたグラフの構築#

隣接行列を基に修正可能

定義#

const int MaxVertexNum = 100;
typedef int DataType;
typedef int Vertex;
typedef bool WeightType;
//隣接リストの定義
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode {
    Vertex AdjV;//隣接点のインデックス
    WeightType Weight;//辺の重み
    PtrToAdjVNode Next;
};

typedef struct VNode {
    PtrToAdjVNode FirstEdge;
    DataType Data;//頂点のデータを格納
}AdjList;

typedef struct GNode *PtrToGNode;
struct GNode {
    int Nv;//頂点数
    int Ne;//辺数
    AdjList G;//隣接リスト
};
typedef PtrToGNode LGraph;//隣接リストで保存されたグラフの型

LGraph の初期化#

LGraph CreateGraph(int VertexNum) {
    Vertex V, W;
    LGraph Graph;
    Graph = (LGraph) malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    //頂点番号は0から始まり、Graph->Nv-1まで
    for (V = 0; V < Graph->Nv; V++) {
        Graph->G[V].FirstEdge = NULL;
    }
    return Graph;
}

LGraph に辺を挿入する#

typedef struct ENode *PtrToENode;
struct ENode {
    Vertex V1, V2;//有向辺<V1,V2>
    WeightType Weight;//重み
};
typedef PtrToENode Edge;
void InsertEdge(LGraph Graph, Edge E){
    PtrToAdjVNode NewNode;
    //辺<V1,V2>を挿入
    //V2の新しい隣接点を作成
    NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V2;
    NewNode->Weight = E->Weight;
    //V2の隣接点をV1のリストの先頭に挿入
    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;
    
    //無向グラフの場合、辺<V2,V1>も挿入する必要がある
    //V1の新しい隣接点を作成
    NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V1;
    NewNode->Weight = E->Weight;
    //V1の隣接点をV2のリストの先頭に挿入
    NewNode->Next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}

完全な LGraph の構築#

MGraph を LGraph に置き換え、Data を保存する部分を少し変更すればよい

LGraph BuildGraph() {
    LGraph Graph;
    Edge E;
    Vertex V;
    int Nv;
    cin >> Nv;
    Graph = CreateGraph(Nv);//Nv個の頂点を持つグラフを構築
    cin >> Graph->Ne;//辺数Ne
    if(Graph->Ne != 0) {
        E = (Edge)malloc(sizeof(struct ENode));
        for (int i = 0; i < Graph->Ne; i++) {
            cin >> E->V1 >> E->V2 >> E->Weight;
            InsertEdge(Graph, E);
        }
    }
    //頂点にデータがある場合、データを読み込む
    for(V = 0; V < Graph->Nv; V++) {
        cin >> Graph->G[V].Data;
    }
    return Graph;
}

二、最短経路問題#

1. 概念の概要#

ネットワーク内で、2 つの異なる頂点間のすべてのパスの中で、辺の重みの合計が最小のパスを求める
- このパスは 2 点間の ** 最短経路 (Shortest Path)** である
- 最初の頂点は ** 始点 (Source)** と呼ばれる
- 最後の頂点は ** 終点 (Destination)** と呼ばれる

2. 問題の分類#

単一始点最短経路問題：特定の始点から出発し、他のすべての頂点への最短経路を求める
- （有向）無重みグラフ
- （有向）有重みグラフ
多始点最短経路問題：任意の 2 頂点間の最短経路を求める

2. 無重みグラフの単一始点最短経路アルゴリズム#

増加順に各頂点への最短経路を見つける、BFS の考え方に非常に似ている！
ここに画像の説明を挿入
まず、配列 dist を定義する、dist [W] は S から W への最短距離を格納する、S は始点、dist [S]=0、dist は - 1（または無限大）に初期化する必要があり、後で訪問済みかどうかを判別するのに便利である。
次に、配列 path を定義する、path [W] は S から W への経路上を通過するある頂点を格納する。
dist と path 配列はすべて - 1 で初期化され、始点の dist [S] を 0 に設定し、キューにプッシュして探索を開始する
擬似コード：

void Unweighted(Vertex S) {
	Enqueue(S, Q);
	while(!IsEmpty(Q)) {
		V = Dequeue(Q);
		for (Vの各隣接点W)
			if(dist[W] == -1) {
				dist[W] = dist[V]+1;
				path[W] = V;
				Enqueue(W, Q);
			}
	}
}

3. 有重みグラフの単一始点最短経路アルゴリズム#

ここに画像の説明を挿入

ダイクストラアルゴリズム！#

s={始点 s + すでに最短経路が確定した頂点 v~i~}
任意の未収録の頂点 v に対して dist [v] を s から v への最短経路の長さと定義するが、その経路はS 内の頂点のみを通過する、すなわち経路 {s→(v~i~∈S)→v} の最小長さ
経路が増加の順序で生成される場合、
- 本当の最短経路は必ず S 内の頂点のみを通過する（反証法で証明可能）
- 毎回未収録の頂点の中から dist が最小のものを選んで収録する（貪欲法）
- 頂点 v を S に追加すると、他の w の dist 値に影響を与える可能性がある！(したがって v のすべての隣接点 w を確認する必要がある！)
  - dist [w] = min { dist [w]，dist [v] + <v,w > の重み}
    dist の初期化：S のすべての隣接点 W の dist は s と w の重みで初期化でき、他は正の無限大と定義する。

擬似コードの説明：

void Dijkstra(Vertex s) {
	while (1){
		V = 未収録頂点の中でdistが最小のもの;
		if (そんなVが存在しない場合)
			break;
		collected[V] = true;
		for (Vの各隣接点W)
			if(collected[W] == false)
				if(dist[V] + E<v,w> < dist[W]) {
					dist[W] = dist[V]+E<v,w>;
					path[W] = V;
				}
	}
}//負の辺のある場合には解決できない

擬似コード中の dist [W]=dist [V]+E~<V,W>~；は単純な代入ではなく、より短い距離があればそれを更新する必要がある
ここに画像の説明を挿入

ダイクストラの核心コード#

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1005;
const int inf  = 0x3f3f3f;
int T,N,x,y,z;
int edge[maxn][maxn];
int dist[maxn];
bool vis[maxn];
void init() {
    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= N; ++j) {
            edge[i][j] = inf;
        }
        edge[i][i] = 0;
    }
}
void Dijstra(int u) {
    for(int i = 1; i <= N; ++i) {
        vis[i] = false;
        dist[i] = edge[u][i];
    }
    vis[u] = true;
    for(int i = 1; i <= N; ++i) {
        int t, mindis = inf;
        for(int j = 1; j <= N; ++j) {
            if(!vis[j] && dist[j] < mindis) {
                mindis = dist[j];
                t = j;
            }
        }
        vis[t] = true;
        for(int j = 1; j <= N; ++j) 
            if(!vis[j] && dist[j] > edge[t][j] + dist[t]) 
                dist[j] = edge[t][j] + dist[t];
    }
}

三、最小生成木#

1. 最小生成木 (Minimum Spanning Tree) とは何か#

木である
- ループがない
- |V | 個の頂点には必ず | V|-1 本の辺がある
生成木である
- すべての頂点を含む
- |V|-1 本の辺はすべてグラフに存在する
- 生成木に任意の辺を追加すると必ずループが形成される
辺の重みの合計が最小である

最小生成木とグラフの連結は同値である

2. 最小生成木問題の解決#

通常は貪欲法を用いる：

「貪欲」：各ステップで最良のものを選ぶ
「良い」：重みが最小の辺
制約が必要：
- グラフに存在する辺のみを使用できる
- 正確に | V|-1 本の辺を使用しなければならない
- ループを持ってはいけない

別のブログに掲載されている。
グラフ理論 —— 最小生成木問題の解決（クラスカルアルゴリズム＆プリムアルゴリズム）