แผนภูมิผู้มีอำนาจที่เรียกว่าแต่ละขอบในแผนภูมิจะมีหนึ่งหรือกลุ่มของค่าที่สอดคล้องกัน โดยปกติค่านี้เป็นเพียงตัวเลข
ตัวอย่างเช่น: ในเครือข่ายการขนส่งน้ำหนักที่ด้านข้างอาจเป็นตัวแทนของระยะทางหรือค่าขนส่ง (เห็นได้ชัดว่าทั้งคู่เป็นตัวเลข) อย่างไรก็ตามน้ำหนักบนขอบอาจเป็นอย่างอื่นเช่นสตริงหรือแม้แต่แพ็กเก็ตข้อมูลที่ซับซ้อนมากขึ้นซึ่งรวบรวมข้อมูลเพิ่มเติม
แนวคิดหลักของอัลกอริทึม Kruskar คือ: ในกราฟการเชื่อมต่อถ่วงน้ำหนักขอบที่เล็กที่สุดจะพบได้อย่างต่อเนื่องในชุดขอบ หากขอบตรงกับเงื่อนไขในการรับต้นไม้ที่ทอดน้อยที่สุดมันจะถูกสร้างขึ้นจนกว่าจะได้รับต้นไม้ที่ทอดน้อยที่สุดในที่สุด
ขั้นตอนการดำเนินการของอัลกอริทึม Kruskar:
ขั้นตอนที่ 1: ในกราฟการเชื่อมต่อถ่วงน้ำหนักเรียงลำดับน้ำหนักของขอบ;
ขั้นตอนที่ 2: พิจารณาว่าคุณจำเป็นต้องเลือกขอบนี้ (ในเวลานี้ขอบในรูปได้รับการจัดเรียงจากน้ำหนักขนาดเล็กถึงใหญ่) พื้นฐานสำหรับการตัดสินคือการเชื่อมต่อจุดยอดทั้งสองของขอบหรือไม่ หากพวกเขาเชื่อมต่อให้ดำเนินการต่อไปยังอีก หากพวกเขาไม่ได้เชื่อมต่อให้เลือกที่จะเชื่อมต่อ
ขั้นตอนที่ 3: วนขั้นตอนที่สองจนกว่าจุดยอดทั้งหมดในกราฟจะอยู่ในส่วนประกอบที่เชื่อมต่อเดียวกันซึ่งหมายถึงทรีสปีนเนอร์ขั้นต่ำ
เกี่ยวกับการใช้งานกราฟสิทธิ์ดูตัวอย่างต่อไปนี้:
กราฟ:
แพ็คเกจ kruskal; กราฟคลาสสาธารณะ {int สุดท้าย max = 100;/** vertex โหนด*/คลาสสาธารณะ vexnode {int adjvex; ข้อมูล int;} vexnode [] vexnodes; int [] thevexs; // vertex set int [] edges = new int [max] [max]; a, int [] vexs) {theVexs = vexs; สำหรับ (int i = 0; i <vexs.length; i ++) {สำหรับ (int j = 0; j <vexs.length; j ++) {graph.edges [i] [j] = a [i] [j];}}}} graph.thevexs.length; {system.out.printf ("%4d", graph.edges [i] [j]);}} system.out.println ("/n");}}}อัลกอริทึม:
แพ็คเกจ kruskal; คลาสสาธารณะ kruskal {ระดับระดับสาธารณะ {int start; int end; int weight;} public void sortedge (edge [] e, int e) {edge temp; int j; สำหรับ (int i = 0; i <e; i ++) {temp = e [i] j = i-1; e [j]; j-;} e [j+1] = temp;}} public kruskal (กราฟกราฟ) {int i, j, u1, v1, sn1, sn2, k; int [] vset = new int [100]; edge [] e = new edge [100]; k = 0; สำหรับ (i = 0; (j = 0; j <= i; j ++) {e [k] = new edge (); ถ้า (graph.edges [i] [j]> 0) {e [k]. start = i; e [k] .end = j; e [k] .weight = graph.edges [i] [j]; (i = 0; i <graph.thevexs.length; i ++) {veted [i] = i;} k = 1; j = 0; ในขณะที่ (k <graph.thevexs.length) {u1 = e [j] .start; v1 = e [j] {system.out.printf ("(%d,%d), น้ำหนัก:%d", u1, v1, e [j] .weight); system.out.println ("/n"); k ++; สำหรับ (i = 0; {vset [i] = sn1;}}} j ++;}}}คลาสทดสอบ:
แพ็คเกจ kruskal; การทดสอบระดับสาธารณะ {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int [] vexs = {0,1,2,3,4}; int [] [] a = a = {{0,1,3,4,7}, {1,0,2, -1, -1}, {3,2,0,5,8}, {4, -1,5,0,6}, {7, -1,8,6,0}} กราฟกราฟ (กราฟกราฟ (กราฟใหม่) กราฟ (กราฟกราฟ kruskal = new kruskal (กราฟ);}}สรุป
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับตัวอย่างรหัสของภาษา Java เพื่อใช้อัลกอริทึม Cruzkal ตามกราฟที่ได้รับอนุญาต ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน หากคุณมีคำถามใด ๆ โปรดฝากข้อความไว้ได้ตลอดเวลา บรรณาธิการจะพยายามอย่างเต็มที่เพื่อตอบคุณ