![\"\"](\"https:\/\/cn.hostease.com\/xueyuan\/wp-content\/uploads\/2017\/04\/tree2.png\")
<\/a><\/figure>\n\n\n\n<\/p>\n\n\n\n
\u5bf9\u4e8e\u4e0a\u9762\u8fd9\u4e2a\u5e26\u6743\u65e0\u5411\u56fe\u6765\u8bf4\uff0c\u5b83\u7684\u751f\u6210\u6811\u6709\u591a\u4e2a\uff0c\u540c\u6837\u6700\u5c0f\u751f\u6210\u6811\u4e5f\u6709\u591a\u4e2a\uff0c\u56e0\u4e3a\u6211\u4eec\u6bd4\u7684\u662f\u6743\u91cd\u7684\u5927\u5c0f\u3002<\/p>\n\n\n\n
\u4e8c\uff1aPrim\u7b97\u6cd5<\/p>\n\n\n\n
\u6c42\u6700\u5c0f\u751f\u6210\u6811\u7684\u7b97\u6cd5\u6709\u5f88\u591a\uff0c\u5e38\u7528\u7684\u662fPrim\u7b97\u6cd5\u548cKruskal\u7b97\u6cd5\uff0c\u4e3a\u4e86\u4fdd\u8bc1\u5355\u4e00\u804c\u8d23\uff0c\u6211\u628aKruskal\u7b97\u6cd5\u653e\u5230\u4e0b\u4e00\u7bc7\uff0c\u90a3\u4e48Prim\u7b97\u6cd5\u7684\u601d\u60f3<\/p>\n\n\n\n
\u662f\u4ec0\u4e48\u5462\uff1f\u5f88\u7b80\u5355\uff0c\u8d2a\u5fc3\u601d\u60f3\u3002<\/p>\n\n\n\n
\u5982\u4e0a\u56fe\uff1a\u73b0\u6709\u96c6\u5408M={A,B,C,D,E,F}\uff0c\u518d\u8bbe\u96c6\u5408N={}\u3002<\/p>\n\n\n\n
\u7b2c\u4e00\u6b65\uff1a\u6311\u9009\u4efb\u610f\u8282\u70b9\uff08\u6bd4\u5982A),\u5c06\u5176\u52a0\u5165\u5230N\u96c6\u5408\uff0c\u540c\u65f6\u5254\u9664M\u96c6\u5408\u7684A\u3002<\/p>\n\n\n\n
\u7b2c\u4e8c\u6b65\uff1a\u5bfb\u627eA\u8282\u70b9\u6743\u503c\u6700\u5c0f\u7684\u90bb\u8282\u70b9\uff08\u6bd4\u5982F\uff09\uff0c\u7136\u540e\u5c06F\u52a0\u5165\u5230N\u96c6\u5408\uff0c\u6b64\u65f6N={A,F}\uff0c\u540c\u65f6\u5254\u9664M\u96c6\u5408\u4e2d\u7684F\u3002<\/p>\n\n\n\n
\u7b2c\u4e09\u6b65\uff1a\u5bfb\u627e{A,F}\u4e2d\u7684\u6743\u503c\u6700\u5c0f\u7684\u90bb\u8282\u70b9\uff08\u6bd4\u5982E\uff09\uff0c\u7136\u540e\u5c06E\u52a0\u5165\u5230N\u96c6\u5408\uff0c\u6b64\u65f6N={A,F,E}\uff0c\u540c\u65f6\u5254\u9664M\u96c6\u5408\u7684E\u3002<\/p>\n\n\n\n
\u3002\u3002\u3002<\/p>\n\n\n\n
\u6700\u540eM\u96c6\u5408\u4e3a{}\u65f6\uff0c\u751f\u6210\u6811\u5c31\u6784\u5efa\u5b8c\u6bd5\u4e86\uff0c\u662f\u4e0d\u662f\u975e\u5e38\u7684\u7b80\u5355\uff0c\u8fd9\u79cd\u8d2a\u5fc3\u505a\u6cd5\u6211\u60f3\u5927\u5bb6\u90fd\u80fd\u60f3\u5f97\u5230\uff0c\u5982\u679c\u7b97\u6cd5\u914d\u5408\u4e00\u4e2a\u597d\u7684\u6570\u636e\u7ed3\u6784\uff0c\u5c31\u4f1a<\/p>\n\n\n\n
\u5982\u864e\u6dfb\u7ffc\u3002<\/p>\n\n\n\n
\u4e09\uff1a\u4ee3\u7801<\/p>\n\n\n\n
1. \u56fe\u7684\u5b58\u50a8<\/p>\n\n\n\n
\u56fe\u7684\u5b58\u50a8\u6709\u5f88\u591a\u65b9\u5f0f\uff0c\u90bb\u63a5\u77e9\u9635\uff0c\u90bb\u63a5\u8868\uff0c\u5341\u5b57\u94fe\u8868\u7b49\u7b49\uff0c\u5f53\u7136\u90fd\u6709\u81ea\u5df1\u7684\u9002\u5408\u573a\u666f\uff0c\u4e0b\u9762\u7528\u90bb\u63a5\u77e9\u9635\u6765\u73a9\u73a9\uff0c\u90bb\u63a5\u77e9\u9635\u9700\u8981\u91c7\u7528\u4e24\u4e2a\u6570\u7ec4\uff0c<\/p>\n\n\n\n
\u2460. \u4fdd\u5b58\u9876\u70b9\u4fe1\u606f\u7684\u4e00\u7ef4\u6570\u7ec4\uff0c<\/p>\n\n\n\n
\u2461. \u4fdd\u5b58\u8fb9\u4fe1\u606f\u7684\u4e8c\u7ef4\u6570\u7ec4\u3002<\/p>\n\n\n\n
1 public class Graph\n 2 {\n 3 \/\/\/ <summary>\n 4 \/\/\/ \u9876\u70b9\u4e2a\u6570\n 5 \/\/\/ <\/summary>\n 6 public char[] vertexs;\n 7 \n 8 \/\/\/ <summary>\n 9 \/\/\/ \u8fb9\u7684\u6761\u6570\n10 \/\/\/ <\/summary>\n11 public int[,] edges;\n12 \n13 \/\/\/ <summary>\n14 \/\/\/ \u9876\u70b9\u4e2a\u6570\n15 \/\/\/ <\/summary>\n16 public int vertexsNum;\n17 \n18 \/\/\/ <summary>\n19 \/\/\/ \u8fb9\u7684\u4e2a\u6570\n20 \/\/\/ <\/summary>\n21 public int edgesNum;\n22 }<\/pre>\n<\/div>\n\n\n\n2\uff1a\u77e9\u9635\u6784\u5efa<\/p>\n\n\n\n
\u77e9\u9635\u6784\u5efa\u5f88\u7b80\u5355\uff0c\u8fd9\u91cc\u628a\u4e0a\u56fe\u4e2d\u7684\u9876\u70b9\u548c\u6743\u7684\u4fe1\u606f\u4fdd\u5b58\u5728\u77e9\u9635\u4e2d\u3002<\/p>\n\n\n\n
\n 1 #region \u77e9\u9635\u7684\u6784\u5efa\n 2 \/\/\/ <summary>\n 3 \/\/\/ \u77e9\u9635\u7684\u6784\u5efa\n 4 \/\/\/ <\/summary>\n 5 public void Build()\n 6 {\n 7 \/\/\u9876\u70b9\u6570\n 8 graph.vertexsNum = 6;\n 9 \n10 \/\/\u8fb9\u6570\n11 graph.edgesNum = 8;\n12 \n13 graph.vertexs = new char[graph.vertexsNum];\n14 \n15 graph.edges = new int[graph.vertexsNum, graph.vertexsNum];\n16 \n17 \/\/\u6784\u5efa\u4e8c\u7ef4\u6570\u7ec4\n18 for (int i = 0; i < graph.vertexsNum; i++)\n19 {\n20 \/\/\u9876\u70b9\n21 graph.vertexs[i] = (char)(i + 65);\n22 \n23 for (int j = 0; j < graph.vertexsNum; j++)\n24 {\n25 graph.edges[i, j] = int.MaxValue;\n26 }\n27 }\n28 \n29 graph.edges[0, 1] = graph.edges[1, 0] = 80;\n30 graph.edges[0, 3] = graph.edges[3, 0] = 100;\n31 graph.edges[0, 5] = graph.edges[5, 0] = 20;\n32 graph.edges[1, 2] = graph.edges[2, 1] = 90;\n33 graph.edges[2, 5] = graph.edges[5, 2] = 70;\n34 graph.edges[3, 2] = graph.edges[2, 3] = 100;\n35 graph.edges[4, 5] = graph.edges[5, 4] = 40;\n36 graph.edges[3, 4] = graph.edges[4, 3] = 60;\n37 graph.edges[2, 3] = graph.edges[3, 2] = 10;\n38 }\n39 #endregion<\/pre>\n<\/div>\n\n\n\n3\uff1aPrim<\/p>\n\n\n\n
\u8981\u73a9Prim\uff0c\u6211\u4eec\u9700\u8981\u4e24\u4e2a\u5b57\u5178\u3002<\/p>\n\n\n\n
\u2460\uff1a\u4fdd\u5b58\u5f53\u524d\u8282\u70b9\u7684\u5b57\u5178\uff0c\u5176\u4e2d\u5305\u542b\u8be5\u8282\u70b9\u7684\u8d77\u59cb\u8fb9\u548c\u7ec8\u8fb9\u4ee5\u53ca\u6743\u503c\uff0c\u7528weight=-1\u6765\u8bb0\u5f55\u5f53\u524d\u8282\u70b9\u5df2\u7ecf\u8bbf\u95ee\u8fc7\uff0c\u7528weight=int.MaxValue\u8868\u793a<\/p>\n\n\n\n
\u4e24\u8282\u70b9\u6ca1\u6709\u8fb9\u3002<\/p>\n\n\n\n
\u2461\uff1a\u8f93\u51fa\u8282\u70b9\u7684\u5b57\u5178\uff0c\u5b58\u653e\u7684\u5c31\u662f\u6211\u4eec\u7684N\u96c6\u5408\u3002<\/p>\n\n\n\n
\u5f53\u7136\u8fd9\u4e2a\u590d\u6742\u5ea6\u73a9\u9ad8\u4e86,\u4e3aO(N2<\/sup>)\uff0c\u5bfb\u627eN\u96c6\u5408\u7684\u90bb\u8fb9\u6700\u5c0f\u6743\u503c\u65f6\uff0c\u6211\u4eec\u53ef\u4ee5\u73a9\u73a9AVL\u6216\u8005\u4f18\u5148\u961f\u5217\u6765\u964d\u4f4e\u590d\u6742\u5ea6\u3002<\/p>\n\n\n\n\n 1 #region prim\u7b97\u6cd5\n 2 \/\/\/ <summary>\n 3 \/\/\/ prim\u7b97\u6cd5\n 4 \/\/\/ <\/summary>\n 5 public Dictionary<char, Edge> Prim()\n 6 {\n 7 Dictionary<char, Edge> dic = new Dictionary<char, Edge>();\n 8 \n 9 \/\/\u7edf\u8ba1\u7ed3\u679c\n10 Dictionary<char, Edge> outputDic = new Dictionary<char, Edge>();\n11 \n12 \/\/weight=MaxValue:\u6807\u8bc6\u6ca1\u6709\u8fb9\n13 for (int i = 0; i < graph.vertexsNum; i++)\n14 {\n15 \/\/\u8d77\u59cb\u8fb9\n16 var startEdge = (char)(i + 65);\n17 \n18 dic.Add(startEdge, new Edge() { weight = int.MaxValue });\n19 }\n20 \n21 \/\/\u53d6\u5b57\u7b26\u7684\u5f00\u59cb\u4f4d\u7f6e\n22 var index = 65;\n23 \n24 \/\/\u53d6\u5f53\u524d\u8981\u4f7f\u7528\u7684\u5b57\u7b26\n25 var start = (char)(index);\n26 \n27 for (int i = 0; i < graph.vertexsNum; i++)\n28 {\n29 \/\/\u6807\u8bb0\u5f00\u59cb\u8fb9\u5df2\u4f7f\u7528\u8fc7\n30 dic[start].weight = -1;\n31 \n32 for (int j = 1; j < graph.vertexsNum; j++)\n33 {\n34 \/\/\u83b7\u53d6\u5f53\u524d c \u7684 \u90bb\u8fb9\n35 var end = (char)(j + index);\n36 \n37 \/\/\u53d6\u5f53\u524d\u5b57\u7b26\u7684\u6743\u91cd\n38 var weight = graph.edges[(int)(start) - index, j];\n39 \n40 if (weight < dic[end].weight)\n41 {\n42 dic[end] = new Edge()\n43 {\n44 weight = weight,\n45 startEdge = start,\n46 endEdge = end\n47 };\n48 }\n49 }\n50 \n51 var min = int.MaxValue;\n52 \n53 char minkey = ' ';\n54 \n55 foreach (var key in dic.Keys)\n56 {\n57 \/\/\u53d6\u5f53\u524d \u6700\u5c0f\u7684 key(\u4f7f\u7528\u8fc7\u7684\u9664\u5916)\n58 if (min > dic[key].weight && dic[key].weight != -1)\n59 {\n60 min = dic[key].weight;\n61 minkey = key;\n62 }\n63 }\n64 \n65 start = minkey;\n66 \n67 \/\/\u8fb9\u4e3a\u9876\u70b9\u51cf\u53bb1\n68 if (outputDic.Count < graph.vertexsNum - 1 && !outputDic.ContainsKey(minkey))\n69 {\n70 outputDic.Add(minkey, new Edge()\n71 {\n72 weight = dic[minkey].weight,\n73 startEdge = dic[minkey].startEdge,\n74 endEdge = dic[minkey].endEdge\n75 });\n76 }\n77 }\n78 return outputDic;\n79 }\n80 #endregion<\/pre>\n<\/div>\n\n\n\n4\uff1a\u6700\u540e\u6211\u4eec\u6765\u6d4b\u8bd5\u4e00\u4e0b\uff0c\u770b\u770b\u627e\u51fa\u7684\u6700\u5c0f\u751f\u6210\u6811\u3002<\/p>\n\n\n\n
\n 1 public static void Main()\n 2 {\n 3 MatrixGraph martix = new MatrixGraph();\n 4 \n 5 martix.Build();\n 6 \n 7 var dic = martix.Prim();\n 8 \n 9 Console.WriteLine(\"\u6700\u5c0f\u751f\u6210\u6811\u4e3a\uff1a\");\n10 \n11 foreach (var key in dic.Keys)\n12 {\n13 Console.WriteLine(\"({0},{1})({2})\", dic[key].startEdge, dic[key].endEdge, dic[key].weight);\n14 }\n15 \n16 Console.Read();\n17 }<\/pre>\n<\/div>\n\n\n\n\n\n 1 using System;\n 2 using System.Collections.Generic;\n 3 using System.Linq;\n 4 using System.Text;\n 5 using System.Diagnostics;\n 6 using System.Threading;\n 7 using System.IO;\n 8 using SupportCenter.Test.ServiceReference2;\n 9 using System.Threading.Tasks;\n 10 \n 11 namespace ConsoleApplication2\n 12 {\n 13 public class Program\n 14 {\n 15 public static void Main()\n 16 {\n 17 MatrixGraph martix = new MatrixGraph();\n 18 \n 19 martix.Build();\n 20 \n 21 var dic = martix.Prim();\n 22 \n 23 Console.WriteLine(\"\u6700\u5c0f\u751f\u6210\u6811\u4e3a\uff1a\");\n 24 \n 25 foreach (var key in dic.Keys)\n 26 {\n 27 Console.WriteLine(\"({0},{1})({2})\", dic[key].startEdge, dic[key].endEdge, dic[key].weight);\n 28 }\n 29 \n 30 Console.Read();\n 31 }\n 32 }\n 33 \n 34 \/\/\/ <summary>\n 35 \/\/\/ \u5b9a\u4e49\u77e9\u9635\u8282\u70b9\n 36 \/\/\/ <\/summary>\n 37 public class MatrixGraph\n 38 {\n 39 Graph graph = new Graph();\n 40 \n 41 public class Graph\n 42 {\n 43 \/\/\/ <summary>\n 44 \/\/\/ \u9876\u70b9\u4e2a\u6570\n 45 \/\/\/ <\/summary>\n 46 public char[] vertexs;\n 47 \n 48 \/\/\/ <summary>\n 49 \/\/\/ \u8fb9\u7684\u6761\u6570\n 50 \/\/\/ <\/summary>\n 51 public int[,] edges;\n 52 \n 53 \/\/\/ <summary>\n 54 \/\/\/ \u9876\u70b9\u4e2a\u6570\n 55 \/\/\/ <\/summary>\n 56 public int vertexsNum;\n 57 \n 58 \/\/\/ <summary>\n 59 \/\/\/ \u8fb9\u7684\u4e2a\u6570\n 60 \/\/\/ <\/summary>\n 61 public int edgesNum;\n 62 }\n 63 \n 64 #region \u77e9\u9635\u7684\u6784\u5efa\n 65 \/\/\/ <summary>\n 66 \/\/\/ \u77e9\u9635\u7684\u6784\u5efa\n 67 \/\/\/ <\/summary>\n 68 public void Build()\n 69 {\n 70 \/\/\u9876\u70b9\u6570\n 71 graph.vertexsNum = 6;\n 72 \n 73 \/\/\u8fb9\u6570\n 74 graph.edgesNum = 8;\n 75 \n 76 graph.vertexs = new char[graph.vertexsNum];\n 77 \n 78 graph.edges = new int[graph.vertexsNum, graph.vertexsNum];\n 79 \n 80 \/\/\u6784\u5efa\u4e8c\u7ef4\u6570\u7ec4\n 81 for (int i = 0; i < graph.vertexsNum; i++)\n 82 {\n 83 \/\/\u9876\u70b9\n 84 graph.vertexs[i] = (char)(i + 65);\n 85 \n 86 for (int j = 0; j < graph.vertexsNum; j++)\n 87 {\n 88 graph.edges[i, j] = int.MaxValue;\n 89 }\n 90 }\n 91 \n 92 graph.edges[0, 1] = graph.edges[1, 0] = 80;\n 93 graph.edges[0, 3] = graph.edges[3, 0] = 100;\n 94 graph.edges[0, 5] = graph.edges[5, 0] = 20;\n 95 graph.edges[1, 2] = graph.edges[2, 1] = 90;\n 96 graph.edges[2, 5] = graph.edges[5, 2] = 70;\n 97 graph.edges[3, 2] = graph.edges[2, 3] = 100;\n 98 graph.edges[4, 5] = graph.edges[5, 4] = 40;\n 99 graph.edges[3, 4] = graph.edges[4, 3] = 60;\n100 graph.edges[2, 3] = graph.edges[3, 2] = 10;\n101 }\n102 #endregion\n103 \n104 #region \u8fb9\u7684\u4fe1\u606f\n105 \/\/\/ <summary>\n106 \/\/\/ \u8fb9\u7684\u4fe1\u606f\n107 \/\/\/ <\/summary>\n108 public class Edge\n109 {\n110 \/\/\u5f00\u59cb\u8fb9\n111 public char startEdge;\n112 \n113 \/\/\u7ed3\u675f\u8fb9\n114 public char endEdge;\n115 \n116 \/\/\u6743\u91cd\n117 public int weight;\n118 }\n119 #endregion\n120 \n121 #region prim\u7b97\u6cd5\n122 \/\/\/ <summary>\n123 \/\/\/ prim\u7b97\u6cd5\n124 \/\/\/ <\/summary>\n125 public Dictionary<char, Edge> Prim()\n126 {\n127 Dictionary<char, Edge> dic = new Dictionary<char, Edge>();\n128 \n129 \/\/\u7edf\u8ba1\u7ed3\u679c\n130 Dictionary<char, Edge> outputDic = new Dictionary<char, Edge>();\n131 \n132 \/\/weight=MaxValue:\u6807\u8bc6\u6ca1\u6709\u8fb9\n133 for (int i = 0; i < graph.vertexsNum; i++)\n134 {\n135 \/\/\u8d77\u59cb\u8fb9\n136 var startEdge = (char)(i + 65);\n137 \n138 dic.Add(startEdge, new Edge() { weight = int.MaxValue });\n139 }\n140 \n141 \/\/\u53d6\u5b57\u7b26\u7684\u5f00\u59cb\u4f4d\u7f6e\n142 var index = 65;\n143 \n144 \/\/\u53d6\u5f53\u524d\u8981\u4f7f\u7528\u7684\u5b57\u7b26\n145 var start = (char)(index);\n146 \n147 for (int i = 0; i < graph.vertexsNum; i++)\n148 {\n149 \/\/\u6807\u8bb0\u5f00\u59cb\u8fb9\u5df2\u4f7f\u7528\u8fc7\n150 dic[start].weight = -1;\n151 \n152 for (int j = 1; j < graph.vertexsNum; j++)\n153 {\n154 \/\/\u83b7\u53d6\u5f53\u524d c \u7684 \u90bb\u8fb9\n155 var end = (char)(j + index);\n156 \n157 \/\/\u53d6\u5f53\u524d\u5b57\u7b26\u7684\u6743\u91cd\n158 var weight = graph.edges[(int)(start) - index, j];\n159 \n160 if (weight < dic[end].weight)\n161 {\n162 dic[end] = new Edge()\n163 {\n164 weight = weight,\n165 startEdge = start,\n166 endEdge = end\n167 };\n168 }\n169 }\n170 \n171 var min = int.MaxValue;\n172 \n173 char minkey = ' ';\n174 \n175 foreach (var key in dic.Keys)\n176 {\n177 \/\/\u53d6\u5f53\u524d \u6700\u5c0f\u7684 key(\u4f7f\u7528\u8fc7\u7684\u9664\u5916)\n178 if (min > dic[key].weight && dic[key].weight != -1)\n179 {\n180 min = dic[key].weight;\n181 minkey = key;\n182 }\n183 }\n184 \n185 start = minkey;\n186 \n187 \/\/\u8fb9\u4e3a\u9876\u70b9\u51cf\u53bb1\n188 if (outputDic.Count < graph.vertexsNum - 1 && !outputDic.ContainsKey(minkey))\n189 {\n190 outputDic.Add(minkey, new Edge()\n191 {\n192 weight = dic[minkey].weight,\n193 startEdge = dic[minkey].startEdge,\n194 endEdge = dic[minkey].endEdge\n195 });\n196 }\n197 }\n198 return outputDic;\n199 }\n200 #endregion\n201 }\n202 }<\/pre>\n<\/div>\n