隣接するテーブルの無向グラフの紹介
隣接テーブルの無向グラフは、隣接テーブルで表される無向グラフを指します。
上の図G1には、「A、B、C、D、E、F、G」の7つの頂点が含まれており、7つのエッジが含まれています。
上記の図の右側のマトリックスは、意図を示すメモリのG1の隣接です。各頂点には、「頂点の隣接点のシーケンス番号」を記録するリンクリストが含まれています。たとえば、2番目の頂点(頂点C)に含まれるリンクリストに含まれるノードのデータは、それぞれ「0、1、3」です。これらの「0、1、3」は、「A、B、D」のシーケンス番号に対応し、「A、B、D」はすべてCの隣接ポイントです。これは、画像の情報を記録する方法です。
隣接テーブルの無向グラフのコード説明
1。基本的な定義
パブリッククラスのlistudg {//リンクリストに対応するテーブルに隣接する頂点プライベートクラスeNode {int ivex; //エッジが次のアークを指している頂点の位置; //次のアークにポインター} vertex}; private vnode [] mvexs; // vertex array ...}(01)listudgは、隣接テーブルに対応する構造です。 MVEXSは、頂点情報を保存する1次元配列です。
(02)vNodeは、隣接するテーブルの頂点に対応する構造です。データは頂点に含まれるデータであり、FirstEdgeは頂点に含まれるリンクリストのヘッダーポインターです。
(03)enodeは、テーブルの頂点に含まれるリンクリストに隣接するノードに対応する構造です。 IVEXは、VEXSのこのノードに対応する頂点のインデックスであり、NextEdgeは次のノードを指します。
2。マトリックスを作成します
マトリックスを作成する2つの方法を次に示します。 1つは既知のデータを使用し、もう1つはユーザーが手動でデータを入力する必要があります。
2.1グラフを作成します(提供されたマトリックスを使用)
/ * *グラフを作成します(提供されたマトリックスを使用) vnode [vlen]; for(int i = 0; i <mvexs.length; i ++){mvexs [i] = new vnode(); mvexs [i] .data = vexs [i]; mvexs [i] .firstedge = null;}エッジの頂点Char c1 = edges [i] [0]; char c2 = edges [i] [1]; //エッジの開始頂点と終了頂点を読み取りますint p1 = getposition(edges [i] [0]); int p2 = getposition(edges [1]); node1を「p1が配置されているリンクリストの終了」にリンクします(mvexs [p1] .firstedge == null)mvexs [p1] .firstedge = node1; else linklast(mvexs [p1] .firstedge、node1); // intivalize node2enode node2 = new enode(); node2.ivex = p1; // link node2へのリンクnode2へのリンクnode p2は、p2が配置されます」 else linklast(mvexs [p2] .firstedge、node2);}}機能は、隣接テーブルの無向グラフを作成することです。実際、この方法で作成された無向グラフは、上記の図G1です。コールコードは次のとおりです。
char [] vexs = {'a'、 'b'、 'c'、 'd'、 'e'、 'f'、 'g'}; char [] [] edges = new char [] [] {{'a'、 'c'}、{'a'、 'd'}、{'a'、 'f' {'e'、 'g'}、{'f'、 'g'}}; listudg pg; pg = new listudg(vexs、edges);2.2グラフを作成する(自分で入力)
/ * *グラフを作成(自分でデータを入力) */public listudg(){//「バージョン番号」と「エッジ番号」System.out.printf( "input Vertex number:"); int vlen = readint(); system.out.printf( "input edge number:"); int elen = readint(); 1)))){System.out.printf( "入力エラー:無効なパラメーター!/n"); return;} // initialize "バージョン" mvexs = new vnode [vlen]; vnode(); mvexs [i] .data = readchar(); mvexs [i] .firstedge = null;} //「edge "// intivalize" edge "// mmatrix = new int [vlen] [vlen]; i); char c1 = readchar(); char c2 = readchar(); int p1 = getposition(c1); int p2 = getposition(c2); // node1.enode node1 = new enode(); node1.ivex = p2; mvexs [p1] .firstedge = node1; else linklast(mvexs [p1] .firstedge、node1); // intivalize node2enode node2 = new enode(); node2.ivex = p1; // link node2へのリンクnode2へのリンクnode p2は、p2が配置されます」 else linklast(mvexs [p2] .firstedge、node2);}}この関数はユーザーの入力を読み取り、入力データを対応する無向グラフに変換します。
隣接テーブルの無向グラフの完全なソースコード
java.io.ioexception; Import java.util.scanner; public class listudg {//テーブルプライベートクラスのテーブルに対応するリンクリストに隣接する頂点{int ivex; //エッジがeNode nextedgeで指している頂点の位置; {char data; // vertex Information enode firstEdge; // vertexに接続されている最初のアークへのポインター}; private vnode [] mvexs; // vertex array/ * *グラフを作成します(自分による入力データ) readint(); system.out.printf( "入力エッジ番号:"); int elen = readint(); if(vlen <1 || elen <1 ||(elen>(vlen -1))))){system.out.printf( "入力エラー:無効なパラメーター!/n"); returtize vnode [vlen]; for(int i = 0; i <mvexs.length; i ++){system.out.printf( "vertex(%d):"、i); mvexs [i] = new vnode(); mvexs [i] .data = readchar(); mvexs [i] .firstedge = nulrize "" // new int [vlen] [vlen]; for(int i = 0; i <elen; i ++){//エッジシステムの開始および終了頂点を読み取ります。 node1 = new enode(); node1.ivex = p2; // link node1に「p1が配置されているリンクリストの終了」に(mvexs [p1] .firstedge == null)mvexs [p1] .firstedge = node1; else linklast(mvexs [p1] .firstedge、node1); // intivalize node2enode node2 = new enode(); node2.ivex = p1; // link node2へのリンクnode2へのリンクnode p2は、p2が配置されます」 else linklast(mvexs [p2] .firstedge、node2);}}/ * *グラフを作成します(提供されたマトリックスを使用) * *パラメーター説明: * vexs -vertex array * edges-エッジアレイ */public listudg(char [] vexs、char [] [] edges){// intivitialize "int" int " = edges.length; // "vertex" mvexs = new vnode [vlen]; for(int i = 0; i <mvexs.length; i ++){mvexs [i] = new vnode(); mvexs [i] .data = vexs [i]; mvexs [i]。 0; i <elen ;/エッジの頂点を読んで、edges [i] [0]; node1 = new enode(); node1.ivex = p2; // link node1に「p1が配置されているリンクリストの終了」に(mvexs [p1] .firstedge == null)mvexs [p1] .firstedge = node1; else linklast(mvexs [p1] .firstedge、node1); // intivalize node2enode node2 = new enode(); node2.ivex = p1; // link node2へのリンクnode2へのリンクnode p2は、p2が配置されます」 else linklast(mvexs [p2] .firstedge、node2);}}/**ノードノードをリストの最後にリンク*/private void linklast(enode list、enode node){enode p = list; while(p.nextedge!= null)p = p = p.nextEdge = node = node = node(get for posit(fig) (int i = 0; i <mvexs.length; i ++)if(mvexs [i] .data == ch)return i; return -1;}/**入力文字を読み取り*/private char readchar(){char ch = '0'; do {try {ch =(char)system.in.read();} catch(ioexception e) {e.printstacktrace();}} while(!キューグラフ*/public void print(){system.out.printf( "list graph:/n"); while(node!= null){system.out.printf( "%d(%c)"、node.ivex、mvexs [node.ivex] .data); node = node.nextedge;} printf( "/n");}} public static boid( 'b' '' '' '' '' '' '' '' '' 'b' '' b '' '' b 'biex){"/n");}} 'd'、 'e'、 'f'、 'g' '}; char [] [] edges = new char [] [] [] {{' a '、' c '}、{' a '、{' a '、' f '}、{' b '、' c '}、{' c '}、' 'e' '' '' e ''} 'g' '}}; listudg pg; // custom "graph"(input matrix queue)// pg = new listudg(); //既存の "グラフ" pg = new listudg(vexs、edges); pg.print(); // print diagram}}}}要約します
上記は、隣接テーブルの無向グラフのJava言語の完全なソースコードの実装に関するこの記事のすべての内容です。私はそれが誰にでも役立つことを願っています。興味のある友達は引き続きこのサイトを参照できます:
Java計算数学式コードの詳細な説明
Javaの可変長さパラメーターコードの詳細な説明
完璧な番号コード分析へのJava言語ソリューション
欠点がある場合は、それを指摘するためにメッセージを残してください。このサイトへのご支援をありがとうございました!