结合邻接矩阵使用Prim算法求得图的最小生成树
顶点
class Vertex
{
public int data;
public Vertex(int data)
{
this.data = data;
}
}
边
class Edge
{
public int tail;
public int head;
public int width;
public Edge(int tail, int head, int width)
{
this.tail = tail;
this.head = head;
this.width = width;
}
}
创建邻接矩阵：
class PrimMinTree
{
int[,] matrix;
int vexCount;
/// <summary>
/// 构造无向图邻接矩阵
/// </summary>
/// <param name="vex"></param>
/// <param name="edge"></param>
public void GraphAdjacencyMatrix(Vertex[] vex, Edge[] edge)
{
matrix = new int[vex.Length, vex.Length];
for (int i = 0; i < vex.Length; i++)
{
for (int j = 0; j < vex.Length; j++)
{
if (i != j)
{
matrix[i, j] = 1000;
}
}
}
vexCount = vex.Length;
for (int i = 0; i < edge.Length; i++)
{
int tail = edge[i].tail;
int head = edge[i].head;
matrix[tail, head] = edge[i].width;
matrix[head, tail] = edge[i].width;
}
//打印邻接矩阵
Console.WriteLine("邻接矩阵：");
Console.Write("\t ");
for (int i = 0; i < vex.Length; i++)
{
Console.Write(vex[i].data + "\t ");
}
Console.WriteLine("\n\n");
for (int i = 0; i < vex.Length; i++)
{
Console.Write(vex[i].data + "\t");
for (int j = 0; j < vex.Length; j++)
{
Console.Write("[" + matrix[i, j] + "]\t");
}
Console.WriteLine("\n\n");
}
}
最小生成树普利姆（Prim）算法：
public void Prim(int vex)
{
//这个数组以数组的索引代表所有顶点的序号，值代表已经找到的最小生成树中，与当前顶点（索引）最近的那个顶点
//比如说，最开始默认找到0号顶点，那么与所有顶点最近的就是0号顶点，因此整个数组的值都为0
int[] adjVex = new int[vexCount];
//这个数组以数组的索引代表所有顶点的序号，值代表已经找到的最小生成树中，与当前顶点（索引）距离最近（权重最小）的值
//至于距离某点最近的已找到的点，可以根据索引在adjVex中找到
//如果是顶点自己到自己，则值为0，代表该点已经被找到
int[] lowCost = new int[vexCount];
//已开始顶点，初始化adjVex和lowCost
//此时找到的顶点只有参数提供的vex，因此距离所有点最近的也只有vex，因此adjVex所有点都为vex
//lowCost[vex]代表自己到自己的权重，设置为0，因为vex是第一个被找到的，后序不允许在找它。
for (int i = 0; i < vexCount; i++)
{
adjVex[i] = vex;
lowCost[i] = matrix[vex, i];
}
Console.WriteLine("Prim算法最小生成树：");
//n个顶点有n-1条线，所以循环n-1次
for (int i = 0; i < vexCount - 1; i++)
{
int min = 1000;//默认最小值
int j = 0;
int k = 0;
//这层循环会找到距离已找到的生成树距离最近（权重最小）的值，用K记录最小的索引值（也就是顶点）
while (j < vexCount)
{
if (lowCost[j] != 0 && lowCost[j] < min)
{
min = lowCost[j];
k = j;
}
j++;
}
Console.Write("(" + adjVex[k] + "," + k + ") ");
lowCost[k] = 0;//表示k顶点现在也是被找到的顶点集合
//这层循环判断剩余顶点到k与没有k之前的最小生成树之间的距离大小（权重）
for (j = 0; j < vexCount; j++)
{
//如果到其他某顶点到k的距离小于之前到生成树的距离，则修改lowCost的值，并把adjVex修改，因为到某顶点最近的生成树的点已经是k了
if (lowCost[j] != 0 && matrix[k, j] < lowCost[j])
{
lowCost[j] = matrix[k, j];
adjVex[j] = k;
}
}
}
}
}
以下面这个图为例，求它的最小生成树
图
Main函数代码：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 数据结构代码篇
{
class Program
{
static void Main(string[] args)
{
PrimMinTree prim = new PrimMinTree();
Vertex vex0 = new Vertex(0);
Vertex vex1 = new Vertex(1);
Vertex vex2 = new Vertex(2);
Vertex vex3 = new Vertex(3);
Vertex vex4 = new Vertex(4);
Vertex vex5 = new Vertex(5);
Vertex vex6 = new Vertex(6);
Vertex vex7 = new Vertex(7);
Vertex vex8 = new Vertex(8);
Vertex[] vex = { vex0, vex1, vex2, vex3, vex4, vex5, vex6, vex7, vex8 };
Edge edge0 = new Edge(0, 1, 10);
Edge edge1 = new Edge(0, 5, 11);
Edge edge2 = new Edge(1, 2, 18);
Edge edge3 = new Edge(1, 8, 12);
Edge edge4 = new Edge(1, 6, 16);
Edge edge5 = new Edge(5, 6, 17);
Edge edge6 = new Edge(2, 8, 8);
Edge edge7 = new Edge(2, 3, 22);
Edge edge8 = new Edge(8, 3, 21);
Edge edge9 = new Edge(6, 3, 24);
Edge edge10 = new Edge(6, 7, 19);
Edge edge11 = new Edge(3, 7, 16);
Edge edge12 = new Edge(4, 7, 7);
Edge edge13 = new Edge(3, 4, 20);
Edge edge14 = new Edge(4, 5, 26);
Edge[] edge = { edge0, edge1, edge2, edge3, edge4, edge5, edge6, edge7, edge8, edge9, edge10, edge11, edge12, edge13, edge14 };
prim.GraphAdjacencyMatrix(vex, edge);
prim.Prim(0);
Console.ReadLine();
}
}
}
运行结果：
运行结果
