รู้เบื้องต้นเกี่ยวกับกราฟที่ไม่ได้บอกทิศทางของตารางที่อยู่ติดกัน
กราฟที่ไม่ได้บอกทิศทางของตาราง adjacency หมายถึงกราฟที่ไม่ได้บอกทิศทางที่แสดงโดยตาราง adjacency
รูปที่ G1 ข้างต้นมี 7 จุดยอดของ "A, B, C, D, E, F, G" และมี 7 ขอบของ "(A, C), (A, D), (A, F), (B, C), (C, D), (E, G), (F, G)"
เมทริกซ์ทางด้านขวาของรูปด้านบนคือ adjacency ของ G1 ในหน่วยความจำที่ระบุความตั้งใจ จุดสุดยอดแต่ละรายการมีรายการที่เชื่อมโยงซึ่งบันทึก "หมายเลขลำดับของจุดที่อยู่ติดกันของจุดสุดยอด" ตัวอย่างเช่นข้อมูลของโหนดที่มีอยู่ในรายการที่เชื่อมโยงที่มีอยู่ในจุดสุดยอดที่สอง (จุดสุดยอด C) ตามลำดับ "0, 1, 3" ตามลำดับ และ "0, 1, 3" เหล่านี้สอดคล้องกับหมายเลขลำดับของ "A, B, D" และ "A, B, D" เป็นจุดทั้งหมดที่อยู่ติดกันของ C นี่คือวิธีการบันทึกข้อมูลของภาพ
รหัสคำอธิบายของกราฟที่ไม่ได้บอกทิศทางของตาราง adjacency
1. คำจำกัดความพื้นฐาน
คลาสสาธารณะ listudg {// จุดสุดยอดที่ adjaces ตารางที่สอดคล้องกับรายการที่เชื่อมโยงคลาสส่วนตัว enode {int iivex; // ตำแหน่งของจุดสุดยอดที่ขอบชี้ไปที่ enode nextedge; // ตัวชี้ไปยังส่วนโค้งถัดไป} // vertex Vertex}; vnode ส่วนตัว [] mvexs; // array vertex ... }(01) listudg เป็นโครงสร้างที่สอดคล้องกับตาราง adjacency MVEXS เป็นอาร์เรย์หนึ่งมิติที่เก็บข้อมูลจุดสุดยอด
(02) VNode เป็นโครงสร้างที่สอดคล้องกับจุดยอดของตารางที่อยู่ติดกัน ข้อมูลคือข้อมูลที่มีอยู่ในจุดสุดยอดและ FirstEdge เป็นตัวชี้ส่วนหัวของรายการที่เชื่อมโยงที่มีอยู่ในจุดสุดยอด
(03) ENODE เป็นโครงสร้างที่สอดคล้องกับโหนดที่อยู่ติดกับรายการที่เชื่อมโยงที่มีอยู่ในจุดยอดของตาราง IVEX เป็นดัชนีของจุดสุดยอดที่สอดคล้องกับโหนดนี้ใน VEXS ในขณะที่ NextEdge ชี้ไปที่โหนดถัดไป
2. สร้างเมทริกซ์
นี่คือสองวิธีในการสร้างเมทริกซ์ หนึ่งใช้ข้อมูลที่รู้จักและอื่น ๆ ต้องการให้ผู้ใช้ป้อนข้อมูลด้วยตนเอง
2.1 สร้างกราฟ (ใช้เมทริกซ์ที่ให้ไว้)
/ * * สร้างกราฟ (ใช้เมทริกซ์ที่ให้ไว้) * * พารามิเตอร์คำอธิบาย: * vexs - vertex array * ขอบ - array edge */public listudg (char [] vexs, char [] [] ขอบ) {// เริ่มต้น "Vertex" และ "edge" vnode [vlen]; สำหรับ (int i = 0; i <mvexs.length; i ++) {mvexs [i] = new vnode (); mvexs [i] .data = vexs [i]; mvexs [i]. firstedge = null; จุดสุดยอดจุดสุดยอดของขอบถ่าน C1 = ขอบ [i] [0]; char c2 = ขอบ [i] [1]; // อ่านจุดสุดยอดเริ่มต้นและจุดสุดยอดสิ้นสุดของขอบ int p1 = getPosition (ขอบ [i] [0]); int p2 = getPosition ลิงก์ Node1 ไปยัง "จุดสิ้นสุดของรายการที่เชื่อมโยงโดยที่ P1 อยู่" ถ้า (MVEXS [P1] .FirstEdge == NULL) MVEXS [P1] .FirstEdge = Node1; else linklast (mvexs [p1] .firstedge, node1); // เริ่มต้น node2enode node2 = new enode (); node2.ivex = p1; // link node2 ถึง "จุดสิ้นสุดของรายการที่เชื่อมโยงซึ่ง p2 อยู่ที่" ถ้า (mvexs [p2] else linklast (mvexs [p2]. Firstedge, node2);}}ฟังก์ชั่นคือการสร้างกราฟที่ไม่ได้ทิศทางของตาราง adjacency ในความเป็นจริงกราฟที่ไม่ได้ทิศทางที่สร้างโดยวิธีนี้คือรูปที่ G1 ด้านบน รหัสการโทรมีดังนี้:
char [] vexs = {'a', 'b', 'c', 'd', 'e', 'f', 'g'}; char [] [] edges = ใหม่ถ่าน [] [] {{'a', 'c'}, {'a', 'd' '' '' '' '' '' '' '' '' '' '' {'e', 'g'}, {'f', 'g'}}; stistudg pg; pg = ใหม่ listudg (vexs, ขอบ);2.2 สร้างกราฟ (ป้อนด้วยตัวเอง)
/ * * สร้างกราฟ (ป้อนข้อมูลด้วยตัวเอง) */public listudg () {// ป้อน "หมายเลขเวอร์ชัน" และ "หมายเลขขอบ" System.out.printf ("อินพุตจุดยอดหมายเลข:"); int vlen = readint (); system.out.printf ("หมายเลขอินพุต:"); int elen = readint () 1)))) {system.out.printf ("ข้อผิดพลาดอินพุต: พารามิเตอร์ที่ไม่ถูกต้อง!/n"); return;} // เริ่มต้น "เวอร์ชัน" mvexs = vnode ใหม่ [vlen]; สำหรับ (int i = 0; i <mvexs.length; i ++) vnode (); mvexs [i] .data = readchar (); mvexs [i] .firstedge = null;} // เริ่มต้น "edge" // mmatrix = new int [vlen] [vlen]; สำหรับ (int i = 0; i <elen; i ++) i); Char C1 = readchar (); char c2 = readchar (); int p1 = getPosition (c1); int p2 = getPosition (c2); // เริ่มต้น node1enode node1 = new enode (); node1.ivex = p2; // link node1 ถึง MVEXS [P1] .FirstEdge = Node1; else linklast (mvexs [p1] .firstedge, node1); // เริ่มต้น node2enode node2 = new enode (); node2.ivex = p1; // link node2 ถึง "จุดสิ้นสุดของรายการที่เชื่อมโยงซึ่ง p2 อยู่ที่" ถ้า (mvexs [p2] else linklast (mvexs [p2]. Firstedge, node2);}}ฟังก์ชั่นนี้อ่านอินพุตของผู้ใช้และแปลงข้อมูลอินพุตเป็นกราฟที่ไม่ได้กำกับที่สอดคล้องกัน
ซอร์สโค้ดที่สมบูรณ์ของกราฟที่ไม่ได้ทิศทางของตาราง adjacency
นำเข้า java.io.ioException; นำเข้า java.util.scanner; คลาสสาธารณะ listudg {// จุดสุดยอดที่อยู่ติดกับรายการที่เชื่อมโยงกับตารางในตารางส่วนตัวของตาราง {int ivex; // ตำแหน่งของ vertex {ข้อมูลถ่าน; // ข้อมูลจุดสุดยอด eNode FirstEdge; // ตัวชี้ไปยังส่วนโค้งแรกที่แนบมากับจุดสุดยอด}; vnode ส่วนตัว [] mvexs; // array vertex/ * * สร้างกราฟ (อินพุตข้อมูลด้วยตัวเอง) */public listudg () readint (); system.out.printf ("หมายเลขขอบอินพุต:"); int elen = readint (); ถ้า (vlen <1 || elen <1 || (elen> (vlen*(vlen - 1)))) {system.out.printf ( vnode [vlen]; สำหรับ (int i = 0; i <mvexs.length; i ++) {system.out.printf ("จุดสุดยอด (%d):", i); mvexs [i] = new vnode (); mvexs [i] .data = readchar () ใหม่ int [vlen] [vlen]; สำหรับ (int i = 0; i <elen; i ++) {// อ่านจุดสุดยอดเริ่มต้นและจุดสิ้นสุดของ Edge System.out.printf ("Edge (%D):", i); Char C1 = readchar (); char c2 = readchar () node1 = new eNode (); node1.ivex = p2; // link node1 ถึง "จุดสิ้นสุดของรายการที่เชื่อมโยงโดยที่ P1 อยู่" ถ้า (mvexs [p1] .Firstedge == null) mvexs [p1] .firstedge = node1; else linklast (mvexs [p1] .firstedge, node1); // เริ่มต้น node2enode node2 = new enode (); node2.ivex = p1; // link node2 ถึง "จุดสิ้นสุดของรายการที่เชื่อมโยงซึ่ง p2 อยู่ที่" ถ้า (mvexs [p2] else linklast (mvexs [p2] .firstedge, node2);}}/ * * สร้างกราฟ (ใช้เมทริกซ์ที่ให้ไว้) * * พารามิเตอร์คำอธิบาย: * vexs - erray vertex * ขอบ array */listudg publan = Edges.length; // เริ่มต้น "จุดสุดยอด" mvexs = new vnode [vlen]; สำหรับ (int i = 0; i <mvexs.length; i ++) {mvexs [i] = new vnode (); mvexs [i] .data = vexs [i] 0; i <elen; node1 = new eNode (); node1.ivex = p2; // link node1 ถึง "จุดสิ้นสุดของรายการที่เชื่อมโยงโดยที่ P1 อยู่" ถ้า (mvexs [p1] .Firstedge == null) mvexs [p1] .firstedge = node1; else linklast (mvexs [p1] .firstedge, node1); // เริ่มต้น node2enode node2 = new enode (); node2.ivex = p1; // link node2 ถึง "จุดสิ้นสุดของรายการที่เชื่อมโยงซึ่ง p2 อยู่ที่" ถ้า (mvexs [p2] else linklast (mvexs [p2] .firstedge, node2);}}/** เชื่อมโยงโหนดโหนดไปยังสุดท้ายของรายการ*/โมฆะส่วนตัว linklast (รายการ eNode, eNode node) {enode p = list; (int i = 0; i <mvexs.length; i ++) ถ้า (mvexs [i] .data == ch) return i; return -1;}/** อ่านอักขระอินพุต*/readchar ตัวถ่านส่วนตัว () {ch ch = '0'; ทำ {ลอง {ch = (char) system.in. ) {E.printStackTrace ();}} ในขณะที่ (! ((ch> = 'a' && ch <= 'z') || (ch> = 'a' && ch <= 'z'))); return ch;}/** อ่านอินพุต กราฟคิว*/โมฆะสาธารณะพิมพ์ () {system.out.printf ("รายการกราฟ:/n"); สำหรับ (int i = 0; i <mvexs.length; i ++) {system.out.printf ("%d (%c):", i, mvexs [i] .data); ในขณะที่ (node! = null) {system.out.printf ("%d (%c)", node.ivex, mvexs [node.ivex] .data); node = node.nextedge;} system.out.printf ("/n"); 'd', 'e', 'f', 'g'}; char [] [] edges = char ใหม่ [] [] {{'a', 'c'}, {'a', 'd'}, {',' f '}, {' b ',' c '} 'g'}}; stistudg pg; // custom "กราฟ" (อินพุตเมทริกซ์คิว) // pg = ใหม่ listudg (); // ใช้ "กราฟ" ที่มีอยู่ pg = listudg ใหม่ (vexs, ขอบ); pg.print (); // พิมพ์แผนภาพ}}}}}}}}สรุป
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับการใช้ซอร์สโค้ดที่สมบูรณ์ของภาษา Java ของตาราง adjacency ที่ไม่ได้กำกับ ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงเว็บไซต์นี้ต่อไปได้:
คำอธิบายโดยละเอียดของรหัสนิพจน์ทางคณิตศาสตร์การคำนวณ Java
คำอธิบายโดยละเอียดของรหัสพารามิเตอร์ความยาวตัวแปรใน Java
โซลูชันภาษา Java เพื่อการวิเคราะห์รหัสจำนวนที่สมบูรณ์แบบ
หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!