データ構造知識整理-構造図(隣接表と隣接マトリクス)
主な内容
図の定義図の記憶構造隣接行列隣接テーブル隣接行列と隣接テーブルクロスリンク隣接する多重表
前言
線形表では、データ要素の間には線形関係しかなく、各データ要素は直接の前駆者と直接の後継者しかない.
ツリー構造では、データ要素の間に明らかな階層関係があり、各階層のデータ要素は、次の層の複数の要素(サブノード)と関連していてもよく、前の層の1つの要素(親ノード)としか関連していない.
図の構造では、結点間の関係は任意であり、樹形構造は特殊な図構造であると言える.
図の定義
図(Graph)Gは、2つの集合VとGからなり、G=(V,G)と記す.このうち、Vは各頂点(結点)の貧困非空集合であり、Vのいずれかの2つの頂点が対になった後、集合Eの要素として、頂点の対は辺とも呼ばれる.
方向図において、E中の要素形式は、頂点xから頂点yまでを表す1本の向辺があり、向辺があり、弧とも呼ばれ、xは弧の尾、yは弧の頭である.
無方向図では、Eの要素形式は(x,y)であり、頂点xと頂点yを接続する一方だけを表し、効果は同じ(y,x)である.
実際の応用において、各辺はある意味の数値を表示してもよく、この値は辺の権利と呼ばれ、これらの権利は一つの頂点からもう一つの頂点までの距離または消費を表してもよい.このような権利のある図は網ともいう.
図の記憶構造
図の任意の2つの頂点の間には連絡があり得るので、データ要素の記憶領域の物理的な位置で要素間の関係を表してはいけません.すなわち図には順序格納構造がありませんが、要素間の関係である隣接行列を2次元配列(行列)で表してもいいです.この他にもチェーン式の記憶構造があり、隣接表、十字チェーン表、隣接多重表が含まれています.このうち、隣接行列と隣接表が最もよく使われています.
隣接行列
隣接行列(Adjacency Matrix)は、頂点間の隣接関係を示す行列であり、二次元配列に格納されている.
1)無方向図において、頂点v 1がv 2に関係していて、v 1がv 3に関係していない場合、マトリックスにおいて、(1,2)と(2,1)の値が1、(1,3)と(3,1)の値が0、対称行列になる.
2)無向網において、辺(v 1,v 2)の権利は7であり、v 1はy 3と関係がない場合、マトリックスにおいて、(1,2)と(2,1)の値は7であり、(1,3)と(3,1)の値は∞(無限)である.
3)図中に、v 1が弧の尾であり、v 2が弧の頭であり、v 2がv 1を指すことがない場合、マトリックス中で、(1,2)の値は1であり、(2,1)の値は0である.
4)ネットに向かっている場合は類推できます.
*マトリックスと二次元配列の「座標」は、マトリクスの(1,1)が二次元配列の「0,0」に等しいことを意味します.
隣接行列は任意の2点間の連絡だけを記録しています.また、1次元配列を必要として、各頂点の情報を記録して、端に頂点があります.
隣接行列の使い方を明確にしてから、それをベースにした図の構造を簡単に書き出すことができます.
概念の混淆を避けるために、後で図を隣接マトリックス図と呼びます.
隣接マトリックス図の構造形式を書き出したら、中に物を入れ始めることができます.
隣接マトリックス表示法の使用方法を「無向網」の例に書きます.
(1)無向網の頂点(vexnum)を数え、いくつかの辺(arcnum)を数えて、数値を入力します.もちろん、あなたも無条件にネットを作ってもいいです.以前に定義されたMaxVNumに値を付けたらいいです.
(2)1次元配列vex内で頂点情報を入力し、1サイクルが完了します.
(3)隣接行列を初期化し、各重み値をMaxIntに初期化する.なぜですか?行列の中でいくつかの権能値を除いて、残りは全部MaxIntなので、先に権力値を記入することができません.もう一つは権力のないところをMaxIntに記入します.このように効率が低くて、煩雑です.
(4)隣接マトリックスを構築します.各辺に依存する2つの頂点v 1とv 2とその値wを順次入力して値を付けます.入力されたv 1、v 2は、0〜MaxIntの範囲内ではない可能性があり、マトリックスと二次元配列の「座標」は、マトリクスの(1,1)が二次元配列の「0,0」に等しいという意味であるため、関数LocateVex()が判断を助け、変換し、「座標」を決定する必要がある.
隣接マトリックスの長所と短所:
1)メリット:
a.二つの頂点に連絡があるかどうかを判断するのに便利です.頂点を決定してから、マトリックス上の該当位置が0でないかどうか、またはMaxIntでないかを決定すればいいです.
b.各頂点の度を計算するのに便利です.実は計算しなくてもいいです.数えたら終わります.無方向図については、いくつかの(1,n)の値が1であり、v 1の度はいくらであるか.向図がある場合、いくつかの<1,n>の値は1で、v 1の度はいくらで、どれぐらいの値が1で、v 1の度はいくらですか?
2)短所:
a.頂点の追加と削除は容易ではない.非連鎖構造の通病
b.統計端の数が容易ではないので、隣接行列のすべての要素を遍歴する必要があり、時間の複雑さはO(n)である.²).無方向図を巡回した後、2で除算します.
c.空間複雑度が高い.非連鎖構造の別の通病、間引き図(辺または弧数が少ない)は特に空間を浪費する.
隣接表
隣接表(Adjacency List)は図のチェーン構造であり、図の頂点の数だけ、個々のチェーンテーブルがいくつかあり、各頂点はそれぞれ単一のチェーンテーブルの先頭ノードとして、頂点に接続されている残りの頂点が無秩序に連結されています.
頂点間の関係はいくつかのシングルチェーンテーブルに含まれているので、隣接テーブル(ALGraph)の構造体は、｛個々のチェーンテーブルのヘッダノード(すなわち、各頂点)とトップ点数とサイド数｝だけを含む必要がある.
頭の結点を管理しやすくするために、一次元配列ALs[MaxVNum]にそれらを置くことができ、この一次元配列の機能は隣接行列図中のvexs[MaxVNum]の機能を含む.
＊下では、先頭の頂点を先頭の頂点と呼びます.
もう一つのチェーンテーブルに注目してください.スタートの頂点はすでに確定していますので、スタートの頂点につながる各頂点はそれぞれ一つの辺に対応しています.したがって、シングルチェーン表の残りの点をエッジの接合点と見なしてもいいです.
エッジポイントに含まれる情報は、「エッジ依存のもう一つの頂点番号(頂点は1次元配列ALs［MaxVNum］にあるので、頂点v 1の番号は0で、このように類推する)と、次の辺の接合点を指し示すポインタと、その辺の権利)があります.
頭の結点に含まれる情報には、「開始頂点の情報、次の辺の結点を指すポインタ」があります.
上の考え方によって、私たちは全部で三つの構造体を作る必要があります.
隣接表図の構造形式を書き出すと、中に物を入れ始めることができます.
以下、「無向図」を例にして、隣接表表示法の使用方法を書きます.
(1)図の頂点と辺の数がないことを入力します.
(2)一次元配列ALs［MaxVNum］に開始頂点の情報を入力し、ポインタ領域をNULLに初期化し、各シングルチェーンテーブルの初期化を完了する.
(3)隣接テーブルを作成します.開始頂点vaと隣接頂点vaの値、および(va,vb)の権利wを入力します.
(4)new一時的な辺結点tempnodeは、tempnodeの「もう一つの頂点の番号」をvbの番号とし、そのポインタを先頭の結点ポインタが元々指す「空間」に向けて、さらに先頭の結点ポインタをtempnodeに向けて、tempnodeの挿入を完了させ、すなわち隣接する頂点の接続を完了させる.
(5)これは無方向図であるため、開始頂点がvbであるシングルチェーンテーブルの挿入を対称的に行う必要がある.
(6)エッジ数arcnumに達する前にループ実行ステップ(3)(4)(5)を実行します.
隣接表の長所と短所:
1)メリット:
a.頂点の追加と削除が容易です.
b.統計しやすい辺の数、時間の複雑さはO(n＋e)である.
c.空間効率が高い.
2)短所:
a.頂点間に連絡があるかどうかを判断するのに不便です.
b.図の各頂点への入力が容易ではないので、残りのすべての開始頂点を巡回するシングルチェーンテーブルが必要です.
隣接行列と隣接表
1)上でまとめたそれぞれの長所と短所が見られます.「私の長所はあなたの短所です.and vice versa」.
2)一つの図の隣接マトリクスが唯一で、隣接テーブルが一意ではない.前述したように、「図の中にいくつの頂点があり、いくつかのシングルチェーンテーブルがあり、各頂点はそれぞれ単一チェーンテーブルの先頭ノードとして、頂点につながる残りの頂点が無秩序に(特殊な順序要求なし)対応するシングルチェーンテーブルに接続されている」したがって、個々のチェーンテーブルのリンク順序は、アルゴリズムおよび入力に依存する.
3)隣接マトリックスと隣接表は図の最も一般的な記憶構造です.з」∠(u)
4)次の「遍歴図」では、深さ優先検索か広さ優先検索かにかかわらず、隣接マトリックスとして記憶されている構造の時間複雑度はO(n)である.²),格納構造が隣接テーブルの時間複雑度はすべてO(n＋e)である.
十字リンク表
十字チェーン(Orthogonal List)は、図の別のチェーン記憶構造であり、図の隣接テーブル(シングルチェーンテーブルの接合点数-1は出度)と逆隣接テーブル(シングルチェーンテーブルの接合点数-1は入度)とが結合したチェーンテーブルと考えられています.
クロスチェーン表では、vi(vi∈G(V)を弧の尾または弧の頭とする弧を見つけやすいので、頂点の入度と出度を求めやすいです.
隣接多重表
隣接する多重表(Adjacency Multiilist)は、図の別のチェーン記憶構造である.
無方向図にとって、隣接表の欠点:各辺(va,vb)には2つの結点があり、それぞれaとb番目のシングルチェーンテーブルにおいて、これは辺の検索、削除などの操作に不便をもたらすかもしれない.
隣接する多重表と隣接表の違いは、同じ辺で、隣接表では2つの結点で表しますが、隣接する多重表では1つの結点だけが必要です.
また、隣接する多重表には、この辺が検索されたかどうかを示すためのフラグ領域が追加されており、同じ辺の重複検索が回避されている.
通りすがりの輪毛君:「図形の構造は三つに分けて言います.構造図、遍歴図、応用図.一度書きたいのですが、力に限りがあります.やるべきことが多いです.私もそろそろ肝臓の保護を始めます.」з」∠_」
図の定義図の記憶構造隣接行列隣接テーブル隣接行列と隣接テーブルクロスリンク隣接する多重表
前言
線形表では、データ要素の間には線形関係しかなく、各データ要素は直接の前駆者と直接の後継者しかない.
ツリー構造では、データ要素の間に明らかな階層関係があり、各階層のデータ要素は、次の層の複数の要素(サブノード)と関連していてもよく、前の層の1つの要素(親ノード)としか関連していない.
図の構造では、結点間の関係は任意であり、樹形構造は特殊な図構造であると言える.
図の定義
図(Graph)Gは、2つの集合VとGからなり、G=(V,G)と記す.このうち、Vは各頂点(結点)の貧困非空集合であり、Vのいずれかの2つの頂点が対になった後、集合Eの要素として、頂点の対は辺とも呼ばれる.
方向図において、E中の要素形式は、頂点xから頂点yまでを表す1本の向辺があり、向辺があり、弧とも呼ばれ、xは弧の尾、yは弧の頭である.
無方向図では、Eの要素形式は(x,y)であり、頂点xと頂点yを接続する一方だけを表し、効果は同じ(y,x)である.
実際の応用において、各辺はある意味の数値を表示してもよく、この値は辺の権利と呼ばれ、これらの権利は一つの頂点からもう一つの頂点までの距離または消費を表してもよい.このような権利のある図は網ともいう.
図の記憶構造
図の任意の2つの頂点の間には連絡があり得るので、データ要素の記憶領域の物理的な位置で要素間の関係を表してはいけません.すなわち図には順序格納構造がありませんが、要素間の関係である隣接行列を2次元配列(行列)で表してもいいです.この他にもチェーン式の記憶構造があり、隣接表、十字チェーン表、隣接多重表が含まれています.このうち、隣接行列と隣接表が最もよく使われています.
隣接行列
隣接行列(Adjacency Matrix)は、頂点間の隣接関係を示す行列であり、二次元配列に格納されている.
1)無方向図において、頂点v 1がv 2に関係していて、v 1がv 3に関係していない場合、マトリックスにおいて、(1,2)と(2,1)の値が1、(1,3)と(3,1)の値が0、対称行列になる.
2)無向網において、辺(v 1,v 2)の権利は7であり、v 1はy 3と関係がない場合、マトリックスにおいて、(1,2)と(2,1)の値は7であり、(1,3)と(3,1)の値は∞(無限)である.
3)図中に、v 1が弧の尾であり、v 2が弧の頭であり、v 2がv 1を指すことがない場合、マトリックス中で、(1,2)の値は1であり、(2,1)の値は0である.
4)ネットに向かっている場合は類推できます.
*マトリックスと二次元配列の「座標」は、マトリクスの(1,1)が二次元配列の「0,0」に等しいことを意味します.
隣接行列は任意の2点間の連絡だけを記録しています.また、1次元配列を必要として、各頂点の情報を記録して、端に頂点があります.
隣接行列の使い方を明確にしてから、それをベースにした図の構造を簡単に書き出すことができます.
概念の混淆を避けるために、後で図を隣接マトリックス図と呼びます.
/* */
#include
using namespace std;
#define MaxInt 32767 /* ∞（ ）*/
#define MaxVNum 100 /* */
typedef char Vextype; /* ， */
typedef int Arctype; /* */
typedef struct
{
Vextype vexs[MaxVNum]; /* */
Arctype arcs[MaxVNum][MaxVNum]; /* */
int vexnum, arenum; /* */
} AMGraph; /* AMGraph*/
隣接マトリックス図の構造形式を書き出したら、中に物を入れ始めることができます.
隣接マトリックス表示法の使用方法を「無向網」の例に書きます.
(1)無向網の頂点(vexnum)を数え、いくつかの辺(arcnum)を数えて、数値を入力します.もちろん、あなたも無条件にネットを作ってもいいです.以前に定義されたMaxVNumに値を付けたらいいです.
(2)1次元配列vex内で頂点情報を入力し、1サイクルが完了します.
(3)隣接行列を初期化し、各重み値をMaxIntに初期化する.なぜですか?行列の中でいくつかの権能値を除いて、残りは全部MaxIntなので、先に権力値を記入することができません.もう一つは権力のないところをMaxIntに記入します.このように効率が低くて、煩雑です.
(4)隣接マトリックスを構築します.各辺に依存する2つの頂点v 1とv 2とその値wを順次入力して値を付けます.入力されたv 1、v 2は、0〜MaxIntの範囲内ではない可能性があり、マトリックスと二次元配列の「座標」は、マトリクスの(1,1)が二次元配列の「0,0」に等しいという意味であるため、関数LocateVex()が判断を助け、変換し、「座標」を決定する必要がある.
int CreatUDN(AMGraph &G) /*UDN Omnidirectional Net， */
{ /* */
int i, j, w;
cin>>G.vexnum>>G.arcnum;
for(i = 0; i < G.vexnum; i++) cin>>G.vexs[i];
for(i = 0; i < G.vexnum; i++)
for(j = 0; j < G.vexnum; j++)
G.arcs[i][j] = MaxInt;
for(int k = 0; k < G.arcnum; k++)
{
cin>>v1>>v2>>w;
i = LocateVex(G, v1); j = LocateVex(G, v2);
G.arc[i][j] = G.arc[j][i] = w;
}
return 0;
}
隣接マトリックスの長所と短所:
1)メリット:
a.二つの頂点に連絡があるかどうかを判断するのに便利です.頂点を決定してから、マトリックス上の該当位置が0でないかどうか、またはMaxIntでないかを決定すればいいです.
b.各頂点の度を計算するのに便利です.実は計算しなくてもいいです.数えたら終わります.無方向図については、いくつかの(1,n)の値が1であり、v 1の度はいくらであるか.向図がある場合、いくつかの<1,n>の値は1で、v 1の度はいくらで、どれぐらいの値が1で、v 1の度はいくらですか?
2)短所:
a.頂点の追加と削除は容易ではない.非連鎖構造の通病
b.統計端の数が容易ではないので、隣接行列のすべての要素を遍歴する必要があり、時間の複雑さはO(n)である.²).無方向図を巡回した後、2で除算します.
c.空間複雑度が高い.非連鎖構造の別の通病、間引き図(辺または弧数が少ない)は特に空間を浪費する.
隣接表
隣接表(Adjacency List)は図のチェーン構造であり、図の頂点の数だけ、個々のチェーンテーブルがいくつかあり、各頂点はそれぞれ単一のチェーンテーブルの先頭ノードとして、頂点に接続されている残りの頂点が無秩序に連結されています.
頂点間の関係はいくつかのシングルチェーンテーブルに含まれているので、隣接テーブル(ALGraph)の構造体は、｛個々のチェーンテーブルのヘッダノード(すなわち、各頂点)とトップ点数とサイド数｝だけを含む必要がある.
頭の結点を管理しやすくするために、一次元配列ALs[MaxVNum]にそれらを置くことができ、この一次元配列の機能は隣接行列図中のvexs[MaxVNum]の機能を含む.
＊下では、先頭の頂点を先頭の頂点と呼びます.
もう一つのチェーンテーブルに注目してください.スタートの頂点はすでに確定していますので、スタートの頂点につながる各頂点はそれぞれ一つの辺に対応しています.したがって、シングルチェーン表の残りの点をエッジの接合点と見なしてもいいです.
エッジポイントに含まれる情報は、「エッジ依存のもう一つの頂点番号(頂点は1次元配列ALs［MaxVNum］にあるので、頂点v 1の番号は0で、このように類推する)と、次の辺の接合点を指し示すポインタと、その辺の権利)があります.
頭の結点に含まれる情報には、「開始頂点の情報、次の辺の結点を指すポインタ」があります.
上の考え方によって、私たちは全部で三つの構造体を作る必要があります.
/* */
typedef struct ArcNode /* */
{
int anothervex; /* */
ArcNode *nextarcnode; /* */
int weight; /* */
};
typedef struct VexNode /* */
{
VexType data; /* */
ArcNode *nextarcnode; /* */
};
typedef struct ALGraph /* */
{
VexNode ALs[MaxInt]; /* */
int vexnum, arcnum; /* 、 */
};隣接表図の構造形式を書き出すと、中に物を入れ始めることができます.
以下、「無向図」を例にして、隣接表表示法の使用方法を書きます.
(1)図の頂点と辺の数がないことを入力します.
(2)一次元配列ALs［MaxVNum］に開始頂点の情報を入力し、ポインタ領域をNULLに初期化し、各シングルチェーンテーブルの初期化を完了する.
(3)隣接テーブルを作成します.開始頂点vaと隣接頂点vaの値、および(va,vb)の権利wを入力します.
(4)new一時的な辺結点tempnodeは、tempnodeの「もう一つの頂点の番号」をvbの番号とし、そのポインタを先頭の結点ポインタが元々指す「空間」に向けて、さらに先頭の結点ポインタをtempnodeに向けて、tempnodeの挿入を完了させ、すなわち隣接する頂点の接続を完了させる.
(5)これは無方向図であるため、開始頂点がvbであるシングルチェーンテーブルの挿入を対称的に行う必要がある.
(6)エッジ数arcnumに達する前にループ実行ステップ(3)(4)(5)を実行します.
int CreatUDG(ALGraph &G)
{ /* */
cin>>G.vexnum>>G.arcnum;
int i, j;
for(i =0; i < G.vexnum; i++)
{
cin>>G.ALs[i].data;
G.ALs[i].nextarcnode = NULL;
}
for(int k = 0; k < G.arcnum; k++)
{
cin>>va>>vb>>w;
i = LocateVex(G, va); j = LocateVex(G, vb);
tempnode1 = new ArcNode;
tempnode1->anothervex = j;
tempnode1->nextarcnode = G.ALs[i].nextarcnode;
G.ALs[i].nextarcnode = tempnode1;
tempnode2 = new ArcNode;
tempnode2->anothervex = i;
tempnode2->nextarcnode = G.ALs[j].nextarcnode;
G.ALs[j].nextarcnode = tempnode2;
}
return 0;
}
隣接表の長所と短所:
1)メリット:
a.頂点の追加と削除が容易です.
b.統計しやすい辺の数、時間の複雑さはO(n＋e)である.
c.空間効率が高い.
2)短所:
a.頂点間に連絡があるかどうかを判断するのに不便です.
b.図の各頂点への入力が容易ではないので、残りのすべての開始頂点を巡回するシングルチェーンテーブルが必要です.
隣接行列と隣接表
1)上でまとめたそれぞれの長所と短所が見られます.「私の長所はあなたの短所です.and vice versa」.
2)一つの図の隣接マトリクスが唯一で、隣接テーブルが一意ではない.前述したように、「図の中にいくつの頂点があり、いくつかのシングルチェーンテーブルがあり、各頂点はそれぞれ単一チェーンテーブルの先頭ノードとして、頂点につながる残りの頂点が無秩序に(特殊な順序要求なし)対応するシングルチェーンテーブルに接続されている」したがって、個々のチェーンテーブルのリンク順序は、アルゴリズムおよび入力に依存する.
3)隣接マトリックスと隣接表は図の最も一般的な記憶構造です.з」∠(u)
4)次の「遍歴図」では、深さ優先検索か広さ優先検索かにかかわらず、隣接マトリックスとして記憶されている構造の時間複雑度はO(n)である.²),格納構造が隣接テーブルの時間複雑度はすべてO(n＋e)である.
十字リンク表
十字チェーン(Orthogonal List)は、図の別のチェーン記憶構造であり、図の隣接テーブル(シングルチェーンテーブルの接合点数-1は出度)と逆隣接テーブル(シングルチェーンテーブルの接合点数-1は入度)とが結合したチェーンテーブルと考えられています.
クロスチェーン表では、vi(vi∈G(V)を弧の尾または弧の頭とする弧を見つけやすいので、頂点の入度と出度を求めやすいです.
隣接多重表
隣接する多重表(Adjacency Multiilist)は、図の別のチェーン記憶構造である.
無方向図にとって、隣接表の欠点:各辺(va,vb)には2つの結点があり、それぞれaとb番目のシングルチェーンテーブルにおいて、これは辺の検索、削除などの操作に不便をもたらすかもしれない.
隣接する多重表と隣接表の違いは、同じ辺で、隣接表では2つの結点で表しますが、隣接する多重表では1つの結点だけが必要です.
また、隣接する多重表には、この辺が検索されたかどうかを示すためのフラグ領域が追加されており、同じ辺の重複検索が回避されている.
通りすがりの輪毛君:「図形の構造は三つに分けて言います.構造図、遍歴図、応用図.一度書きたいのですが、力に限りがあります.やるべきことが多いです.私もそろそろ肝臓の保護を始めます.」з」∠_」