それで、あなたはGraphsに慣れていないようです。ウィキペディアを見てください。また、いくつかの画像を参照すると、理解しやすくなります。
コンセプトのビット
あなたの写真は として表すことができますGraph。一般に、グラフは 2 つの基本的な種類の要素を使用して実装されます(NodesとLinks呼ばれることもありArcsます)。
ANodeは写真の文字を表し、A、B、C などになります。ArcまたはLinkは 2 つのノードを接続する線です。H から L への接続を見ると、2 つの間にリンクがあります。加重グラフ。リンクごとに加重が異なります。
問題を解決する - パート 1
Node私たちがしなければならないことは、あなたの写真をコード内のグラフとして表現することです。基本的な要素とを作成しましょうArc:
ノード
ノードには があるNameため、ノードを識別できます。ノードは他のノードに接続できます。ノードのコレクションを使用できますが、あなたのグラフは加重グラフであるため、各接続はリンクされたノードとその重みで表す必要があります。したがって、アークのコレクションを使用します。
public class Node
{
public string Name;
public List<Arc> Arcs = new List<Arc>();
public Node(string name)
{
Name = name;
}
/// <summary>
/// Create a new arc, connecting this Node to the Nod passed in the parameter
/// Also, it creates the inversed node in the passed node
/// </summary>
public Node AddArc(Node child, int w)
{
Arcs.Add(new Arc
{
Parent = this,
Child = child,
Weigth = w
});
if (!child.Arcs.Exists(a => a.Parent == child && a.Child == this))
{
child.AddArc(this, w);
}
return this;
}
}
アーク
非常に単純なクラスで、リンクされたノードと接続の重みが含まれています。
public class Arc
{
public int Weigth;
public Node Parent;
public Node Child;
}
グラフ
グラフは、組織化のための一種のラッパー クラスです。グラフのルートも宣言しました。使用していませんが、いくつかの場合に役立ちます。
public class Graph
{
public Node Root;
public List<Node> AllNodes = new List<Node>();
public Node CreateRoot(string name)
{
Root = CreateNode(name);
return Root;
}
public Node CreateNode(string name)
{
var n = new Node(name);
AllNodes.Add(n);
return n;
}
public int?[,] CreateAdjMatrix()
{
// Matrix will be created here...
}
}
問題を解決する - パート 2
これで、グラフを保持するためのすべてのデータ構造ができました。いくつかのデータを入力してみましょう。キューブ画像に似たグラフを初期化するコードを次に示します。退屈で退屈ですが、実際のケースでは、グラフは動的に作成されます。
static void Main(string[] args)
{
var graph = new Graph();
var a = graph.CreateRoot("A");
var b = graph.CreateNode("B");
var c = graph.CreateNode("C");
var d = graph.CreateNode("D");
var e = graph.CreateNode("E");
var f = graph.CreateNode("F");
var g = graph.CreateNode("G");
var h = graph.CreateNode("H");
var i = graph.CreateNode("I");
var j = graph.CreateNode("J");
var k = graph.CreateNode("K");
var l = graph.CreateNode("L");
var m = graph.CreateNode("M");
var n = graph.CreateNode("N");
var o = graph.CreateNode("O");
var p = graph.CreateNode("P");
a.AddArc(b, 1)
.AddArc(c, 1);
b.AddArc(e, 1)
.AddArc(d, 3);
c.AddArc(f, 1)
.AddArc(d, 3);
c.AddArc(f, 1)
.AddArc(d, 3);
d.AddArc(h, 8);
e.AddArc(g, 1)
.AddArc(h, 3);
f.AddArc(h, 3)
.AddArc(i, 1);
g.AddArc(j, 3)
.AddArc(l, 1);
h.AddArc(j, 8)
.AddArc(k, 8)
.AddArc(m, 3);
i.AddArc(k, 3)
.AddArc(n, 1);
j.AddArc(o, 3);
k.AddArc(p, 3);
l.AddArc(o, 1);
m.AddArc(o, 1)
.AddArc(p, 1);
n.AddArc(p, 1);
// o - Already added
// p - Already added
int?[,] adj = graph.CreateAdjMatrix(); // We're going to implement that down below
PrintMatrix(ref adj, graph.AllNodes.Count); // We're going to implement that down below
}
問題の解決 - パート 3
これで、完全に初期化されたグラフができたので、マトリックスを作成しましょう。次のメソッドは、n x n の 2 次元の行列を作成します。ここで、n は、グラフ クラスから取得したノードの数です。ノードごとに、リンクがあるかどうかを検索し、リンクがある場合は、マトリックスの適切な位置を埋めます。あなたの隣接行列の例では、1sしかないことに注意してください。ここではリンクの重みを入れています。
public int?[,] CreateAdjMatrix()
{
int?[,] adj = new int?[AllNodes.Count, AllNodes.Count];
for (int i = 0; i < AllNodes.Count; i++)
{
Node n1 = AllNodes[i];
for (int j = 0; j < AllNodes.Count; j++)
{
Node n2 = AllNodes[j];
var arc = n1.Arcs.FirstOrDefault(a => a.Child == n2);
if (arc != null)
{
adj[i, j] = arc.Weigth;
}
}
}
return adj;
}
終わり
これで、加重隣接行列が得られました。印刷する方法は次のとおりです。
private static void PrintMatrix(ref int?[,] matrix, int Count)
{
Console.Write(" ");
for (int i = 0; i < Count; i++)
{
Console.Write("{0} ", (char)('A' + i));
}
Console.WriteLine();
for (int i = 0; i < Count; i++)
{
Console.Write("{0} | [ ", (char)('A' + i));
for (int j = 0; j < Count; j++)
{
if (i == j)
{
Console.Write(" &,");
}
else if (matrix[i, j] == null)
{
Console.Write(" .,");
}
else
{
Console.Write(" {0},", matrix[i, j]);
}
}
Console.Write(" ]\r\n");
}
Console.Write("\r\n");
}
次の出力が得られます。
A B C D E F G H I J K L M N O P
A | [ &, 1, 1, ., ., ., ., ., ., ., ., ., ., ., ., ., ]
B | [ 1, &, ., 3, 1, ., ., ., ., ., ., ., ., ., ., ., ]
C | [ 1, ., &, 3, ., 1, ., ., ., ., ., ., ., ., ., ., ]
D | [ ., 3, 3, &, ., ., ., 8, ., ., ., ., ., ., ., ., ]
E | [ ., 1, ., ., &, ., 1, 3, ., ., ., ., ., ., ., ., ]
F | [ ., ., 1, ., ., &, ., 3, 1, ., ., ., ., ., ., ., ]
G | [ ., ., ., ., 1, ., &, ., ., 3, ., 1, ., ., ., ., ]
H | [ ., ., ., 8, 3, 3, ., &, ., 8, 8, ., 3, ., ., ., ]
I | [ ., ., ., ., ., 1, ., ., &, ., 3, ., ., 1, ., ., ]
J | [ ., ., ., ., ., ., 3, 8, ., &, ., ., ., ., 3, ., ]
K | [ ., ., ., ., ., ., ., 8, 3, ., &, ., ., ., ., 3, ]
L | [ ., ., ., ., ., ., 1, ., ., ., ., &, ., ., 1, ., ]
M | [ ., ., ., ., ., ., ., 3, ., ., ., ., &, ., 1, 1, ]
N | [ ., ., ., ., ., ., ., ., 1, ., ., ., ., &, ., 1, ]
O | [ ., ., ., ., ., ., ., ., ., 3, ., 1, 1, ., &, ., ]
P | [ ., ., ., ., ., ., ., ., ., ., 3, ., 1, 1, ., &, ]
