如题。
在之前简单图的基础上，修改一个简单的带权邻接表图如下，备用。
class MyTable { public Node[] nodes; //获得图5-2所示图形，随便加了几个权值 public static MyTable get_One_MyTable() { MyTable mtt = new(); int n = 5; mtt.nodes = new Node[n]; LinkedList<(int, int)> t; for (int i = 0; i < n; i++) { mtt.nodes[i] = new Node("v" + i); } t = new(); t.AddLast((1, 10)); t.AddLast((2, 30)); t.AddLast((4, 50)); mtt.nodes[0].next = t; t = new(); t.AddLast((0, 10)); t.AddLast((2, 60)); mtt.nodes[1].next = t; t = new(); t.AddLast((0, 30)); t.AddLast((1, 60)); t.AddLast((4, 20)); mtt.nodes[2].next = t; t = new(); t.AddLast((4, 40)); mtt.nodes[3].next = t; t = new(); t.AddLast((0, 50)); t.AddLast((2, 20)); t.AddLast((3, 40)); mtt.nodes[4].next = t; return mtt; } public void testShow() { if (nodes == null) { Console.WriteLine("No Nodes."); return; } foreach (var item in nodes) { Console.Write($"节点{item.v},边："); foreach (var item1 in item.next) { Console.Write(item1.Item1 + "," + item1.Item2 + " "); } Console.WriteLine(); } } } //顶点（值和指向边的指针） class Node { public string v; public LinkedList<(int, int)> next; public Node(string x) { v = x; } }
写一个普里姆算法辅助类，代码如下：
class PMinTree { //输入图定点状态表 //true表示已加入树，反之未加入 static bool[] flags; //准备吸入的点（起点，终点，权值） static Queue<(int start, int end, int power)> q = new(); static MyTable in_g, out_g; public static MyTable get_Min_Tree(MyTable x) { //先做准备工作 //结果图（out_g）先放上所有顶点，起始点状态为true，边空 in_g = x; out_g = new(); int n = in_g.nodes.Length; flags = new bool[n]; out_g.nodes = new Node[n]; for (int i = 0; i < in_g.nodes.Length; i++) { out_g.nodes[i]=new(in_g.nodes[i].v); out_g.nodes[i].next = new(); } flags[0] = true; //一条临时边 (int start, int end,int power) t_edge; //只要还有没加入结果的点，就一直扫描 while(flags.Contains(false)) { scan_Enqueue(); t_edge = get_Edge(); //把扫出来的边加到“生成树图”，也就是输出图中 out_g.nodes[t_edge.start].next.AddLast((t_edge.end, t_edge.power)); //注意要加两条边 out_g.nodes[t_edge.end].next.AddLast((t_edge.start, t_edge.power)); //加入的点状态设为true flags[t_edge.end] = true; } return out_g; } //扫描入队 static void scan_Enqueue() { //扫描所有输入图中 for (int i = 0; i < in_g.nodes.Length; i++) { //已连通的点（对应flag为true）的边 if(flags[i]) { //取出其中通向 foreach (var item in in_g.nodes[i].next) { //未连通点（对应flag为false）的边 if (!flags[item.Item1]) { //入队(入队格式：起点、终点、权值。） //（因为未来加入out_g的时候需要起点终点，而权值是判断依据) q.Enqueue((i, item.Item1, item.Item2)); } } } } } //获取队列中权值最小的边 static (int start,int end,int power) get_Edge() { (int start, int end, int power) r, t; if (q.Count==0) { return (-1, -1,-1); } else { r = q.Dequeue(); while(q.Count>0) { t = q.Dequeue(); if(t.power<r.power) { r = t; } } return r; } } }
主程序调用：
static void Main(string[] args) { MyTable a, b; a = MyTable.get_One_MyTable(); b = PMinTree.get_Min_Tree(a); a.testShow(); Console.WriteLine("----------------------------"); b.testShow(); }
运行结果：
节点v0,边：1,10 2,30 4,50 节点v1,边：0,10 2,60 节点v2,边：0,30 1,60 4,20 节点v3,边：4,40 节点v4,边：0,50 2,20 3,40 ---------------------------- 节点v0,边：1,10 2,30 节点v1,边：0,10 节点v2,边：0,30 4,20 节点v3,边：4,40 节点v4,边：2,20 3,40
验证正确。