サーチ…
前書き
グラフは、いくつかの（おそらく空の）サブセットを結ぶ点と線の集合です。グラフのポイントは、グラフ頂点、「ノード」または単に「ポイント」と呼ばれます。同様に、グラフの頂点を結ぶ線は、グラフエッジ、「円弧」または「線」と呼ばれます。
グラフGは対（V、E）として定義することができ、ここでVは頂点の集合であり、Eは頂点E⊆{（u、v）| u、v∈V}である。
備考
グラフは、エッジまたはリンクのセットからメンバーに接続されている場合と接続されていない場合があるオブジェクトのセットをモデル化する数学的な構造です。
グラフは、2つの異なる数学的オブジェクトの集合を介して記述することができる。
- 頂点の集合。
- 頂点のペアを接続するエッジのセット。
グラフは、有向グラフまたは無向グラフのいずれかになります。
- 有向グラフには、一方向にのみ「接続」するエッジが含まれています。
- 方向切れのないグラフには、2つの頂点を自動的に両方向に接続するエッジのみが含まれます。
トポロジカルソート
トポロジカル・オーダリングまたはトポロジカル・ソートは、線上、すなわちリスト内の有向非循環グラフ内の頂点を、すべての有向枝が左から右に向くように順序付けする。このような順序は、グラフに指示されたサイクルが含まれている場合は存在しません。これは、行を続けることができず、開始した場所に戻って戻ることができないためです。
正式に、グラフにG = (V, E)は、すべての頂点の線形順序は場合は、そのようなものであるGエッジを含ん(u, v) ∈ E頂点からu頂点v次にu先行v順序で。
各DAG に少なくとも1つのトポロジカルソートがあることに注意することが重要です。
線形時間で任意のDAGのトポロジカルな順序を構築するための既知のアルゴリズムがあり、その一例は次のとおりである。
-
depth_first_search(G)を呼び出して各頂点の仕上げ時間vfを計算するv - 各頂点が完成したら、それをリンクリストの先頭に挿入します
- ソートされた頂点のリンクリスト。
トポロジカルソートをして行うことができるϴ(V + E)深さ優先探索アルゴリズムがかかるため、時間ϴ(V + E)の時間およびそれが取るΩ(1)の各挿入する（時定数） |V|リンクされたリストの前に頂点を追加します。
多くのアプリケーションでは、イベント間の優先順位を示すために有向非循環グラフが使用されます。私たちはトポロジカルソートを使用して、後続のいずれかの前に各頂点を処理する順序を取得します。
グラフの頂点は、実行されるタスクを表してもよく、エッジは、あるタスクが別のタスクの前に実行されなければならないという制約を表すことができる。トポロジカルな順序付けは、 V説明したタスクのタスクセットを実行するための有効なシーケンスです。
問題インスタンスとその解決策
頂点を聞かせてv記述Task(hours_to_complete: int) 、すなわち、 Task(4)について説明Taskかかり4完了する時間を、エッジe記述Cooldown(hours: int)するように、 Cooldown(3)の期間を説明します完了したタスクの後に冷却する時間。
私たちのグラフをdag （それは有向非循環グラフであるため）と呼び、5つの頂点を持つようにしましょう：
A <- dag.add_vertex(Task(4));
B <- dag.add_vertex(Task(5));
C <- dag.add_vertex(Task(3));
D <- dag.add_vertex(Task(2));
E <- dag.add_vertex(Task(7));
ここでは、グラフが非周期的であるように、頂点を有向エッジで接続し、
// A ---> C ----+
// | | |
// v v v
// B ---> D --> E
dag.add_edge(A, B, Cooldown(2));
dag.add_edge(A, C, Cooldown(2));
dag.add_edge(B, D, Cooldown(1));
dag.add_edge(C, D, Cooldown(1));
dag.add_edge(C, E, Cooldown(1));
dag.add_edge(D, E, Cooldown(3));
AとE間に3つの可能なトポロジカルな順序があり、
-
A -> B -> D -> E -
A -> C -> D -> E -
A -> C -> E
Thorupのアルゴリズム
無向グラフの単一ソース最短経路に対するThorupのアルゴリズムは、Dijkstraよりも低い時間複雑度O（m）を有する。
基本的なアイデアは次のとおりです。 （申し訳ありませんが、私はまだそれを実装しようとしませんでしたので、私は細かい部分を見逃す可能性があります元の論文はpaywalledですので、それを参照する他のソースから再構築しようとしました。
- O（m）でスパニングツリーを見つける方法はあります（ここでは説明しません）。スパニングツリーを最短エッジから最長まで「成長」させる必要があります。完全に成長する前に、複数のコンポーネントが接続された森林になります。
- 整数b（b> = 2）を選択し、長さ制限b ^ kのスパニングフォレストのみを考慮します。まったく同じであるがkが異なるコンポーネントをマージし、コンポーネントのレベルを最小にする。その後、コンポーネントを論理的にツリーにします。 uはvの親であるiff uはvを完全に含むvとは別の最小の成分である。ルートはグラフ全体であり、葉は元のグラフ（負の無限大のレベル）の単一の頂点である。ツリーにはまだO（n）個のノードしかありません。
- Dijkstraのアルゴリズムのように、各コンポーネントのソースまでの距離を維持する。複数の頂点を持つコンポーネントの距離は、拡張されていない子の最小距離です。元の頂点の距離を0に設定し、それに応じて祖先を更新します。
- 基底bの距離を考慮する。レベルkのノードを初めて訪れたときは、レベルkのすべてのノード（バケットソートのように、Dijkstraのアルゴリズムのヒープを置き換える）で共有されたバケットに、その距離の数字k以上の子を配置します。ノードを訪れるたびに、最初のbバケットだけを検討し、それぞれを訪問して削除し、現在のノードの距離を更新し、新しい距離を使用して現在のノードを自身の親に再リンクし、次の訪問を待つバケツ。
- 葉が訪問されると、現在の距離が頂点の最終距離になります。元のグラフのすべての辺を展開し、それに応じて距離を更新します。
- 目的地に達するまでルートノード（全体のグラフ）を繰り返し訪問してください。
これは、長さ制限lを持つスパニングフォレストの2つの接続されたコンポーネントの間にl未満の長さのエッジがないため、距離xから始まり、到達するまで1つの接続されたコンポーネントにのみ集中できます距離x + l。より短い距離の頂点がすべて訪問される前に、いくつかの頂点を訪問しますが、それらの頂点からのパスが短くなることは知られているため、問題はありません。他の部分は、バケットソート/ MSD基数ソートのように機能し、もちろん、O（m）スパニングツリーが必要です。
Depth First Traversalを使用した有向グラフのサイクルの検出
有向グラフのサイクルは、DFS中にバックエッジが検出された場合に存在します。バックエッジは、ノードからDFSツリー内の祖先の1つへのエッジです。切断されたグラフの場合、DFSフォレストが取得されるため、グラフ内のすべての頂点を反復処理して、互いに素なDFSツリーを見つける必要があります。
C ++実装：
#include <iostream>
#include <list>
using namespace std;
#define NUM_V 4
bool helper(list<int> *graph, int u, bool* visited, bool* recStack)
{
visited[u]=true;
recStack[u]=true;
list<int>::iterator i;
for(i = graph[u].begin();i!=graph[u].end();++i)
{
if(recStack[*i]) //if vertice v is found in recursion stack of this DFS traversal
return true;
else if(*i==u) //if there's an edge from the vertex to itself
return true;
else if(!visited[*i])
{ if(helper(graph, *i, visited, recStack))
return true;
}
}
recStack[u]=false;
return false;
}
/*
/The wrapper function calls helper function on each vertices which have not been visited. Helper function returns true if it detects a back edge in the subgraph(tree) or false.
*/
bool isCyclic(list<int> *graph, int V)
{
bool visited[V]; //array to track vertices already visited
bool recStack[V]; //array to track vertices in recursion stack of the traversal.
for(int i = 0;i<V;i++)
visited[i]=false, recStack[i]=false; //initialize all vertices as not visited and not recursed
for(int u = 0; u < V; u++) //Iteratively checks if every vertices have been visited
{ if(visited[u]==false)
{ if(helper(graph, u, visited, recStack)) //checks if the DFS tree from the vertex contains a cycle
return true;
}
}
return false;
}
/*
Driver function
*/
int main()
{
list<int>* graph = new list<int>[NUM_V];
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(2);
graph[2].push_back(0);
graph[2].push_back(3);
graph[3].push_back(3);
bool res = isCyclic(graph, NUM_V);
cout<<res<<endl;
}
結果：以下に示すように、グラフには3つのバックエッジがあります。頂点0と2の間の1つ。頂点0,1,2の間。頂点の数であり、Eはエッジの数である。 
グラフ理論の紹介
グラフ理論は、オブジェクトの対の関係をモデル化するために使用される数学的構造であるグラフの研究です。
あなたは知っていましたか？惑星地球のほとんどすべての問題は、道路と都市の問題に変換して解決できますか？グラフ理論は数年前、たとえコンピュータの発明前に発明されました。 Leonhard EulerはKönigsbergの7つの橋について論文を書いた。これはグラフ理論の最初の論文とみなされている。それ以来、人々はこの問題をこの都市道路問題に変えることができれば、グラフ理論によって簡単に解くことができることを認識するようになりました。
グラフ理論は多くのアプリケーションを持っています。最も一般的なアプリケーションの1つは、都市間の最短距離を見つけることです。我々は皆、あなたのPCに到達するために、このWebページはサーバから多くのルータを移動しなければならないことを知っています。グラフ理論は、交差する必要のあるルータを見つけるのに役立ちます。戦時中に首都を他の都市から切り離すためにはどの街を砲撃する必要があるのか、それもグラフ理論を使って見つけることができます。
最初にグラフ理論に関する基本的な定義を学びましょう。
グラフ：
6つの都市があるとしましょう。 1、2、3、4、5、6とマークします。ここで道路を結んでいる都市を結びます。
これは、いくつかの都市がそれらを結ぶ道路とともに示されている簡単なグラフです。グラフ理論では、これらの各都市をノードまたは頂点と呼び、道路をエッジと呼びます。グラフは、単にこれらのノードとエッジの接続です。
ノードは多くのことを表すことができます 。いくつかのグラフでは、ノードは都市を表し、いくつかは空港を表し、いくつかはチェス盤の正方形を表します。 Edgeは各ノード間の関係を表す。その関係は、ある空港から別の空港へ行く時間、ある広場から他の広場までの騎士の動きなどです。
チェス盤の騎士道
簡単に言えば、 Nodeは任意のオブジェクトを表し、 Edgeは2つのオブジェクト間の関係を表します。
隣接ノード：
ノードAがノードBとエッジを共有する場合、 BはAに隣接しているとみなされます。言い換えると、2つのノードが直接接続されている場合、それらを隣接ノードと呼びます。 1つのノードは複数の隣接ノードを持つことができます。
有向グラフと無向グラフ：
有向グラフでは、エッジは片側に方向記号を持ちます。つまり、エッジは単方向です。一方、無向グラフのエッジは、 双方向の方向を示します。つまり、 双方向です。通常、無向グラフは、エッジの両側に符号なしで表されます。
パーティーがあると仮定しましょう。パーティー内の人々はノードによって表され、彼らが手を振ると2人の間にはエッジがあります。すべての人Aがあれば、人のBと手を振ると、Bも Aと握手する場合にのみので、このグラフは無向です。賞賛は必ずしも往復動されていないため、これとは対照的に、Bは Aの眺めBに対応する別の人物に人物Aからエッジ場合、このグラフは、向けられています。グラフの前者は、 無向グラフと呼ばれ、グラフの後者のタイプは、 有向グラフと呼ばれ、エッジは有向エッジと呼ばれながら、エッジは無向エッジと呼ばれます。
加重および非加重グラフ：
加重グラフとは、各辺に数値（重み）が割り当てられたグラフです。そのような重みは、手元の問題に応じて、例えばコスト、長さまたは容量を表すことができる。 
重み付けされていないグラフは、単に反対です。我々は、すべての辺の重みが同じである（おそらく1）と仮定する。
パス：
パスとは、あるノードから別のノードに移動する方法を表します。これは一連のエッジで構成されています。 2つのノード間に複数のパスが存在する可能性があります。 
上の例では、 AからDの 2つのパスがあります。 A→B、B→C、C→Dは1つのパスです。このパスのコストは3 + 4 + 2 = 9です。再び、別の経路A→Dがあります。このパスのコストは10です。最低コストのパスを最短パスと呼びます 。
度：
頂点の次数は、それに接続されている辺の数です。両端の頂点に接続する辺がある場合（ループ）、2回カウントされます。
有向グラフでは、ノードには次の2種類の度合いがあります。
- In-degree：ノードを指すエッジの数。
- Out-degree：ノードから他のノードを指すエッジの数。
無向グラフの場合、単にdegreeと呼ばれます。
グラフ理論に関連したアルゴリズム
- ベルマンフォードアルゴリズム
- ダイクストラのアルゴリズム
- Ford-Fulkersonアルゴリズム
- クルスカルのアルゴリズム
- 最近傍アルゴリズム
- プリムのアルゴリズム
- 深さ優先検索
- 幅優先探索
グラフの保存（隣接行列）
グラフを保存するには、2つの方法が一般的です。
- 隣接行列
- 隣接リスト
隣接行列は、有限グラフを表すために使用される正方行列です。行列の要素は、グラフの頂点のペアが隣接しているかどうかを示します。
隣接するとは、「他のものの隣にあるか隣接している」、または何かの隣にあることを意味します。たとえば、あなたの隣人はあなたに隣接しています。グラフ理論では、 ノードAからノード Bに行くことができれば、 ノードBはノードAに隣接していると言える。ここでは、どのノードを隣接行列に格納するかについて学習します。つまり、どのノードがノード間でエッジを共有するかを表します。行列は2D配列を意味します。
ここでグラフの横のテーブルを見ることができます。これは私たちの隣接行列です。ここで、 Matrix [i] [j] = 1は、 iとjの間にエッジがあることを表します。エッジがない場合は、単純にMatrix [i] [j] = 0を入力します。
これらのエッジは、2つの都市間の距離を表すことができるように、重み付けすることができます。次に、1を代入する代わりにMatrix [i] [j]に値を代入します。
上記グラフは、我々は、ノード2からノード1に行くことができれば手段は、我々は、 ノード1からノード2に行くことができることは、 双方向または無向です。グラフがDirectedの場合、グラフの片側に矢印記号が表示されます。それでも、隣接行列を使って表現することができます。
私たちは、 無限にエッジを共有しないノードを表します 。注目すべき点の1つは、グラフが無向であれば、行列は対称になるということです。
行列を作成する擬似コード：
Procedure AdjacencyMatrix(N): //N represents the number of nodes
Matrix[N][N]
for i from 1 to N
for j from 1 to N
Take input -> Matrix[i][j]
endfor
endfor
このような一般的な方法で行列を生成することもできます。
Procedure AdjacencyMatrix(N, E): // N -> number of nodes
Matrix[N][E] // E -> number of edges
for i from 1 to E
input -> n1, n2, cost
Matrix[n1][n2] = cost
Matrix[n2][n1] = cost
endfor
有向グラフの場合、 Matrix [n2] [n1] = cost lineを削除できます。
隣接行列の欠点：
メモリは大きな問題です。どのくらいの辺があっても、常にN * N個のサイズの行列が必要です。ここで、Nはノードの数です。 10000ノードがある場合、マトリックスサイズは約381メガバイトの4 * 10000 * 10000になります。エッジの数が少ないグラフを考えると、これは大きなメモリの無駄です。
どのノードにノードuから行くことができるかを知りたいとしよう。私たちはuの行全体をチェックする必要がありますが、時間がかかります。
唯一の利点は、Adjacency Matrixを使用して、 uvノードとそのコストの接続を簡単に見つけることができることです。
上記の疑似コードを使用して実装されたJavaコード：
import java.util.Scanner;
public class Represent_Graph_Adjacency_Matrix
{
private final int vertices;
private int[][] adjacency_matrix;
public Represent_Graph_Adjacency_Matrix(int v)
{
vertices = v;
adjacency_matrix = new int[vertices + 1][vertices + 1];
}
public void makeEdge(int to, int from, int edge)
{
try
{
adjacency_matrix[to][from] = edge;
}
catch (ArrayIndexOutOfBoundsException index)
{
System.out.println("The vertices does not exists");
}
}
public int getEdge(int to, int from)
{
try
{
return adjacency_matrix[to][from];
}
catch (ArrayIndexOutOfBoundsException index)
{
System.out.println("The vertices does not exists");
}
return -1;
}
public static void main(String args[])
{
int v, e, count = 1, to = 0, from = 0;
Scanner sc = new Scanner(System.in);
Represent_Graph_Adjacency_Matrix graph;
try
{
System.out.println("Enter the number of vertices: ");
v = sc.nextInt();
System.out.println("Enter the number of edges: ");
e = sc.nextInt();
graph = new Represent_Graph_Adjacency_Matrix(v);
System.out.println("Enter the edges: <to> <from>");
while (count <= e)
{
to = sc.nextInt();
from = sc.nextInt();
graph.makeEdge(to, from, 1);
count++;
}
System.out.println("The adjacency matrix for the given graph is: ");
System.out.print(" ");
for (int i = 1; i <= v; i++)
System.out.print(i + " ");
System.out.println();
for (int i = 1; i <= v; i++)
{
System.out.print(i + " ");
for (int j = 1; j <= v; j++)
System.out.print(graph.getEdge(i, j) + " ");
System.out.println();
}
}
catch (Exception E)
{
System.out.println("Somthing went wrong");
}
sc.close();
}
}
コードの実行：ファイルを保存し、 javac Represent_Graph_Adjacency_Matrix.javaを使用してコンパイルしますjavac Represent_Graph_Adjacency_Matrix.java
例：
$ java Represent_Graph_Adjacency_Matrix
Enter the number of vertices:
4
Enter the number of edges:
6
Enter the edges: <to> <from>
1 1
3 4
2 3
1 4
2 4
1 2
The adjacency matrix for the given graph is:
1 2 3 4
1 1 1 0 1
2 0 0 1 1
3 0 0 0 1
4 0 0 0 0
グラフの保存（隣接リスト）
隣接リストは、有限グラフを表すために使用される順序付けられていないリストの集合です。各リストは、グラフ内の頂点の近隣の集合を記述する。グラフを格納するために必要なメモリは少なくて済みます。
グラフとその隣接行列を見てみましょう： 
これらの値を使用してリストを作成します。
これは隣接リストと呼ばれます。どのノードがどのノードに接続されているかを示します。この情報は2D配列を使用して保存することができます。しかし、Adjacency Matrixと同じメモリが必要になります。代わりに、動的に割り当てられたメモリを使用してこれを格納します。
多くの言語がベクトルまたはリストをサポートしており、これを使用して隣接リストを格納できます。これらのために、 Listのサイズを指定する必要はありません。ノードの最大数を指定するだけです。
疑似コードは次のようになります。
Procedure Adjacency-List(maxN, E): // maxN denotes the maximum number of nodes
edge[maxN] = Vector() // E denotes the number of edges
for i from 1 to E
input -> x, y // Here x, y denotes there is an edge between x, y
edge[x].push(y)
edge[y].push(x)
end for
Return edge
この1つは無向グラフであるので、XからYへのエッジが存在し、xにyからエッジもあります。有向グラフの場合は、2番目のグラフを省略します。加重グラフの場合、コストも保存する必要があります。これを格納するためにcost []という名前の別のベクトルまたはリストを作成します。擬似コード：
Procedure Adjacency-List(maxN, E):
edge[maxN] = Vector()
cost[maxN] = Vector()
for i from 1 to E
input -> x, y, w
edge[x].push(y)
cost[x].push(w)
end for
Return edge, cost
これにより、任意のノードに接続されているノードの総数、およびこれらのノードの数を簡単に調べることができます。隣接行列よりも時間がかかりません。しかし、 uとvの間にエッジがあるかどうかを調べる必要がある場合は、隣接行列を保持する方が簡単でした。
