{"id":2075,"date":"2017-04-15T13:09:12","date_gmt":"2017-04-15T05:09:12","guid":{"rendered":"http:\/\/cn.hostease.com\/xueyuan\/?p=2075"},"modified":"2025-01-07T16:11:05","modified_gmt":"2025-01-07T08:11:05","slug":"%e7%bb%8f%e5%85%b8%e7%ae%97%e6%b3%95%e9%a2%98%e6%af%8f%e6%97%a5%e6%bc%94%e7%bb%83-%e7%ac%ac%e5%8d%81%e5%85%ad%e9%a2%98-kruskal%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"https:\/\/cn.hostease.com\/xueyuan\/jishu\/%e7%bb%8f%e5%85%b8%e7%ae%97%e6%b3%95%e9%a2%98%e6%af%8f%e6%97%a5%e6%bc%94%e7%bb%83-%e7%ac%ac%e5%8d%81%e5%85%ad%e9%a2%98-kruskal%e7%ae%97%e6%b3%95\/","title":{"rendered":"\u7ecf\u5178\u7b97\u6cd5\u9898\u6bcf\u65e5\u6f14\u7ec3\u2014\u2014\u7b2c\u5341\u516d\u9898 Kruskal\u7b97\u6cd5"},"content":{"rendered":"\n

\u8fd9\u7bc7\u6211\u4eec\u770b\u770b\u7b2c\u4e8c\u79cd\u751f\u6210\u6811\u7684Kruskal\u7b97\u6cd5\uff0c\u8fd9\u4e2a\u7b97\u6cd5\u7684\u9b45\u529b\u5728\u4e8e\u6211\u4eec\u53ef\u4ee5\u6253\u4e00\u4e0b\u7b97\u6cd5\u548c\u6570\u636e\u7ed3\u6784\u7684\u7ec4\u5408\u62f3\uff0c\u5f88\u6709\u610f\u601d\u7684\u3002<\/p>\n\n\n\n

\u4e00\uff1a\u601d\u60f3<\/p>\n\n\n\n

\u82e5\u5b58\u5728M={0,1,2,3,4,5}\u8fd9\u68376\u4e2a\u8282\u70b9\uff0c\u6211\u4eec\u77e5\u9053Prim\u7b97\u6cd5\u6784\u5efa\u751f\u6210\u6811\u662f\u4ece\u201d\u9876\u70b9\u201d\u8fd9\u4e2a\u89d2\u5ea6\u6765\u601d\u8003\u7684\uff0c\u7136\u540e\u91c7\u7528\u201c\u8d2a\u5fc3\u601d\u60f3\u201d<\/p>\n\n\n\n

\u6765\u4e00\u6b65\u6b65\u6269\u5927\u5316\uff0c\u6700\u540e\u5f62\u6210\u6574\u4f53\u6700\u4f18\u89e3\uff0c\u800cKruskal\u7b97\u6cd5\u6709\u70b9\u610f\u601d\uff0c\u5b83\u662f\u7ad9\u5728\u201d\u8fb9\u201c\u8fd9\u4e2a\u89d2\u5ea6\u5728\u601d\u8003\u7684\uff0c\u9996\u5148\u6211\u6709\u4e24\u4e2a\u96c6\u5408\u3002<\/p>\n\n\n\n

1. \u9876\u70b9\u96c6\u5408(vertexs)\uff1a<\/p>\n\n\n\n

\u6bd4\u5982M\u96c6\u5408\u4e2d\u7684\u6bcf\u4e2a\u5143\u7d20\u90fd\u53ef\u4ee5\u8ba4\u4e3a\u662f\u4e00\u4e2a\u72ec\u6839\u6811\uff08\u662f\u4e0d\u662f\u60f3\u5230\u4e86\u5e76\u67e5\u96c6\uff1f\uff09\u3002<\/p>\n\n\n\n

2.\u8fb9\u96c6\u5408(edges)\uff1a<\/p>\n\n\n\n

\u5bf9\u56fe\u4e2d\u7684\u6bcf\u6761\u8fb9\u6309\u7167\u6743\u503c\u5927\u5c0f\u8fdb\u884c\u6392\u5e8f\u3002\uff08\u662f\u4e0d\u662f\u60f3\u5230\u4e86\u4f18\u5148\u961f\u5217\uff1f\uff09<\/p>\n\n\n\n

\u597d\u4e86\uff0c\u4e0b\u9762\u8be5\u5982\u4f55\u64cd\u4f5c\u5462\uff1f<\/p>\n\n\n\n

\u9996\u5148\uff1a\u6211\u4eec\u4eceedges\u4e2d\u9009\u51fa\u6743\u503c\u6700\u5c0f\u7684\u4e00\u6761\u8fb9\u6765\u4f5c\u4e3a\u751f\u6210\u6811\u7684\u4e00\u6761\u8fb9\uff0c\u7136\u540e\u5c06\u8be5\u8fb9\u7684\u4e24\u4e2a\u9876\u70b9\u5408\u5e76\u4e3a\u4e00\u4e2a\u65b0\u7684\u6811\u3002<\/p>\n\n\n\n

\u7136\u540e\uff1a\u6211\u4eec\u7ee7\u7eed\u4eceedges\u4e2d\u9009\u51fa\u6b21\u5c0f\u7684\u8fb9\u4f5c\u4e3a\u751f\u6210\u6811\u7684\u7b2c\u4e8c\u6761\u8fb9\uff0c\u4f46\u662f\u524d\u63d0\u5c31\u662f\u8fb9\u7684\u4e24\u4e2a\u9876\u70b9\u4e00\u5b9a\u662f\u5c5e\u4e8e\u4e24\u4e2a\u96c6\u5408\u4e2d\uff0c\u5982\u679c\u4e0d\u662f<\/p>\n\n\n\n

\u5219\u5254\u9664\u8be5\u8fb9\u7ee7\u7eed\u9009\u4e0b\u4e00\u6761\u6b21\u5c0f\u8fb9\u3002<\/p>\n\n\n\n

\u6700\u540e\uff1a\u7ecf\u8fc7\u53cd\u590d\u64cd\u4f5c\uff0c\u5f53\u6211\u4eec\u53d1\u73b0n\u4e2a\u9876\u70b9\u7684\u56fe\u4e2d\u751f\u6210\u6811\u5df2\u7ecf\u6709n-1\u8fb9\u7684\u65f6\u5019\uff0c\u6b64\u65f6\u751f\u6210\u6811\u6784\u5efa\u5b8c\u6bd5\u3002<\/p>\n\n\n\n

\"\"<\/a><\/figure>\n\n\n\n

<\/p>\n\n\n\n

\"\"<\/a><\/figure>\n\n\n\n

<\/p>\n\n\n\n

\u4ece\u56fe\u4e2d\u6211\u4eec\u8fd8\u662f\u5f88\u6e05\u695a\u7684\u770b\u5230Kruskal\u7b97\u6cd5\u6784\u5efa\u751f\u6210\u6811\u7684\u8be6\u7ec6\u8fc7\u7a0b\uff0c\u540c\u65f6\u6211\u4eec\u4e5f\u770b\u5230\u4e86\u201d\u5e76\u67e5\u96c6\u201c\u548c\u201c\u4f18\u5148\u961f\u5217\u201c\u8fd9\u4e24\u4e2a\u795e\u5668<\/p>\n\n\n\n

\u6765\u52a0\u901f\u6211\u4eec\u7684\u751f\u6210\u6811\u6784\u5efa\u3002<\/p>\n\n\n\n

\u4e8c\uff1a\u6784\u5efa<\/p>\n\n\n\n

1.Build\u65b9\u6cd5<\/p>\n\n\n\n

\u8fd9\u91cc\u6211\u704c\u7684\u662f\u4e00\u4e9b\u6d4b\u8bd5\u6570\u636e\uff0c\u540c\u65f6\u5728\u77e9\u9635\u6784\u5efa\u5b8c\u6bd5\u540e\uff0c\u5c06\u9876\u70b9\u4fe1\u606f\u653e\u5165\u5e76\u67e5\u96c6\uff0c\u540c\u65f6\u5c06\u8fb9\u7684\u4fe1\u606f\u653e\u5165\u4f18\u5148\u961f\u5217\uff0c\u65b9\u4fbf\u6211\u4eec\u5728<\/p>\n\n\n\n

\u505a\u751f\u6210\u6811\u7684\u65f6\u5019\u79d2\u6740\u3002<\/p>\n\n\n\n

\n
 <\/div>\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 int[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] = i;\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[4, 5] = graph.edges[5, 4] = 40;\n35             graph.edges[3, 4] = graph.edges[4, 3] = 60;\n36             graph.edges[2, 3] = graph.edges[3, 2] = 10;\n37 \n38             \/\/\u4f18\u5148\u961f\u5217\uff0c\u5b58\u653e\u6811\u4e2d\u7684\u8fb9\n39             queue = new PriorityQueue<Edge>();\n40 \n41             \/\/\u5e76\u67e5\u96c6\n42             set = new DisjointSet<int>(graph.vertexs);\n43 \n44             \/\/\u5c06\u5bf9\u89d2\u7ebf\u8bfb\u5165\u5230\u4f18\u5148\u961f\u5217\n45             for (int i = 0; i < graph.vertexsNum; i++)\n46             {\n47                 for (int j = i; j < graph.vertexsNum; j++)\n48                 {\n49                     \/\/\u8bf4\u660e\u8be5\u8fb9\u6709\u6743\u91cd\n50                     if (graph.edges[i, j] != int.MaxValue)\n51                     {\n52                         queue.Eequeue(new Edge()\n53                         {\n54                             startEdge = i,\n55                             endEdge = j,\n56                             weight = graph.edges[i, j]\n57                         }, graph.edges[i, j]);\n58                     }\n59                 }\n60             }\n61         }\n62         #endregion<\/pre>\n
 <\/div>\n<\/div>\n\n\n\n
2\uff1aKruskal\u7b97\u6cd5<\/p>\n\n\n\n
\u5e76\u67e5\u96c6\uff0c\u4f18\u5148\u961f\u5217\u90fd\u6709\u6570\u636e\u4e86\uff0c\u4e0b\u9762\u6211\u4eec\u53ea\u8981\u51fa\u961f\u64cd\u4f5c\u5c31\u884c\u4e86\uff0c\u5982\u679c\u8fb9\u7684\u9876\u70b9\u4e0d\u5728\u4e00\u4e2a\u96c6\u5408\u4e2d\uff0c\u6211\u4eec\u5c06\u5176\u6536\u96c6\u4f5c\u4e3a\u6700\u5c0f\u751f\u6210\u6811\u7684\u4e00\u6761\u8fb9\uff0c<\/p>\n\n\n\n
\u6309\u7740\u8fd9\u6837\u7684\u65b9\u5f0f\uff0c\u6700\u7ec8\u751f\u6210\u6811\u6784\u5efa\u5b8c\u6bd5\uff0c\u600e\u4e48\u6837\uff0c\u7ec4\u5408\u62f3\u6253\u7684\u723d\u4e0d\u723d\uff1f<\/p>\n\n\n\n
\n
 <\/div>\n
 1 #region Kruskal\u7b97\u6cd5\n 2         \/\/\/ <summary>\n 3         \/\/\/ Kruskal\u7b97\u6cd5\n 4         \/\/\/ <\/summary>\n 5         public List<Edge> Kruskal()\n 6         {\n 7             \/\/\u6700\u540e\u6536\u96c6\u5230\u7684\u6700\u5c0f\u751f\u6210\u6811\u7684\u8fb9\n 8             List<Edge> list = new List<Edge>();\n 9 \n10             \/\/\u5faa\u73af\u961f\u5217\n11             while (queue.Count() > 0)\n12             {\n13                 var edge = queue.Dequeue();\n14 \n15                 \/\/\u5982\u679c\u8be5\u4e24\u70b9\u662f\u540c\u4e00\u4e2a\u96c6\u5408\uff0c\u5219\u5254\u9664\u8be5\u96c6\u5408\n16                 if (set.IsSameSet(edge.t.startEdge, edge.t.endEdge))\n17                     continue;\n18 \n19                 list.Add(edge.t);\n20 \n21                 \/\/\u7136\u540e\u5c06startEdge \u548c endEdge Union\u8d77\u6765\uff0c\u8868\u793a\u4e00\u4e2a\u96c6\u5408\n22                 set.Union(edge.t.startEdge, edge.t.endEdge);\n23 \n24                 \/\/\u5982\u679cn\u4e2a\u8282\u70b9\u6709n-1\u8fb9\u7684\u65f6\u5019\uff0c\u6b64\u65f6\u751f\u6210\u6811\u5df2\u7ecf\u6784\u5efa\u5b8c\u6bd5\uff0c\u63d0\u524d\u9000\u51fa\n25                 if (list.Count == graph.vertexsNum - 1)\n26                     break;\n27             }\n28 \n29             return list;\n30         }\n31         #endregion<\/pre>\n
 <\/div>\n<\/div>\n\n\n\n
\u6700\u540e\u662f\u603b\u7684\u4ee3\u7801\uff1a<\/p>\n\n\n\n
<\/div>\n\n\n\n
\u5e76\u67e5\u96c6\uff1a<\/p>\n\n\n\n
\n\n
\n
 <\/div>\n
  1 using System;\n  2 using System.Collections.Generic;\n  3 using System.Linq;\n  4 using System.Text;\n  5 \n  6 namespace ConsoleApplication2\n  7 {\n  8     \/\/\/ <summary>\n  9     \/\/\/ \u5e76\u67e5\u96c6\n 10     \/\/\/ <\/summary>\n 11     public class DisjointSet<T> where T : IComparable\n 12     {\n 13         #region \u6811\u8282\u70b9\n 14         \/\/\/ <summary>\n 15         \/\/\/ \u6811\u8282\u70b9\n 16         \/\/\/ <\/summary>\n 17         public class Node\n 18         {\n 19             \/\/\/ <summary>\n 20             \/\/\/ \u7236\u8282\u70b9\n 21             \/\/\/ <\/summary>\n 22             public T parent;\n 23 \n 24             \/\/\/ <summary>\n 25             \/\/\/ \u8282\u70b9\u7684\u79e9\n 26             \/\/\/ <\/summary>\n 27             public int rank;\n 28         }\n 29         #endregion\n 30 \n 31         Dictionary<T, Node> dic = new Dictionary<T, Node>();\n 32 \n 33         public DisjointSet(T[] c)\n 34         {\n 35             Init(c);\n 36         }\n 37 \n 38         #region \u505a\u5355\u4e00\u96c6\u5408\u7684\u521d\u59cb\u5316\u64cd\u4f5c\n 39         \/\/\/ <summary>\n 40         \/\/\/ \u505a\u5355\u4e00\u96c6\u5408\u7684\u521d\u59cb\u5316\u64cd\u4f5c\n 41         \/\/\/ <\/summary>\n 42         public void Init(T[] c)\n 43         {\n 44             \/\/\u9ed8\u8ba4\u7684\u4e0d\u60f3\u4ea4\u96c6\u5408\u7684\u7236\u8282\u70b9\u6307\u5411\u81ea\u5df1\n 45             for (int i = 0; i < c.Length; i++)\n 46             {\n 47                 dic.Add(c[i], new Node()\n 48                 {\n 49                     parent = c[i],\n 50                     rank = 0\n 51                 });\n 52             }\n 53         }\n 54         #endregion\n 55 \n 56         #region \u5224\u65ad\u4e24\u5143\u7d20\u662f\u5426\u5c5e\u4e8e\u540c\u4e00\u4e2a\u96c6\u5408\n 57         \/\/\/ <summary>\n 58         \/\/\/ \u5224\u65ad\u4e24\u5143\u7d20\u662f\u5426\u5c5e\u4e8e\u540c\u4e00\u4e2a\u96c6\u5408\n 59         \/\/\/ <\/summary>\n 60         \/\/\/ <param name=\"root1\"><\/param>\n 61         \/\/\/ <param name=\"root2\"><\/param>\n 62         \/\/\/ <returns><\/returns>\n 63         public bool IsSameSet(T root1, T root2)\n 64         {\n 65             return Find(root1).CompareTo(Find(root2)) == 0;\n 66         }\n 67         #endregion\n 68 \n 69         #region  \u67e5\u627ex\u6240\u5c5e\u7684\u96c6\u5408\n 70         \/\/\/ <summary>\n 71         \/\/\/ \u67e5\u627ex\u6240\u5c5e\u7684\u96c6\u5408\n 72         \/\/\/ <\/summary>\n 73         \/\/\/ <param name=\"x\"><\/param>\n 74         \/\/\/ <returns><\/returns>\n 75         public T Find(T x)\n 76         {\n 77             \/\/\u5982\u679c\u76f8\u7b49\uff0c\u5219\u8bf4\u660e\u5df2\u7ecf\u5230\u6839\u8282\u70b9\u4e86\uff0c\u8fd4\u56de\u6839\u8282\u70b9\u5143\u7d20\n 78             if (dic[x].parent.CompareTo(x) == 0)\n 79                 return x;\n 80 \n 81             \/\/\u8def\u5f84\u538b\u7f29(\u56de\u6eaf\u7684\u65f6\u5019\u8d4b\u503c\uff0c\u6700\u7ec8\u7684\u503c\u5c31\u662f\u4e0a\u9762\u8fd4\u56de\u7684\"x\"\uff0c\u4e5f\u5c31\u662f\u4e00\u6761\u8def\u5f84\u4e0a\u5168\u90e8\u88ab\u4fee\u6539\u4e86)\n 82             return dic[x].parent = Find(dic[x].parent);\n 83         }\n 84         #endregion\n 85 \n 86         #region \u5408\u5e76\u4e24\u4e2a\u4e0d\u76f8\u4ea4\u96c6\u5408\n 87         \/\/\/ <summary>\n 88         \/\/\/ \u5408\u5e76\u4e24\u4e2a\u4e0d\u76f8\u4ea4\u96c6\u5408\n 89         \/\/\/ <\/summary>\n 90         \/\/\/ <param name=\"root1\"><\/param>\n 91         \/\/\/ <param name=\"root2\"><\/param>\n 92         \/\/\/ <returns><\/returns>\n 93         public void Union(T root1, T root2)\n 94         {\n 95             T x1 = Find(root1);\n 96             T y1 = Find(root2);\n 97 \n 98             \/\/\u5982\u679c\u6839\u8282\u70b9\u76f8\u540c\u5219\u8bf4\u660e\u662f\u540c\u4e00\u4e2a\u96c6\u5408\n 99             if (x1.CompareTo(y1) == 0)\n100                 return;\n101 \n102             \/\/\u8bf4\u660e\u5de6\u96c6\u5408\u7684\u6df1\u5ea6 < \u53f3\u96c6\u5408\n103             if (dic[x1].rank < dic[y1].rank)\n104             {\n105                 \/\/\u5c06\u5de6\u96c6\u5408\u6307\u5411\u53f3\u96c6\u5408\n106                 dic[x1].parent = y1;\n107             }\n108             else\n109             {\n110                 \/\/\u5982\u679c \u79e9 \u76f8\u7b49\uff0c\u5219\u5c06 y1 \u5e76\u5165\u5230 x1 \u4e2d\uff0c\u5e76\u5c06x1++\n111                 if (dic[x1].rank == dic[y1].rank)\n112                     dic[x1].rank++;\n113 \n114                 dic[y1].parent = x1;\n115             }\n116         }\n117         #endregion\n118     }\n119 }<\/pre>\n
 <\/div>\n<\/div>\n<\/div>\n\n\n\n
\u4f18\u5148\u961f\u5217\uff1a<\/p>\n\n\n\n
\n\n
\n
 <\/div>\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 \n  9 namespace ConsoleApplication2\n 10 {\n 11     public class PriorityQueue<T> where T : class\n 12     {\n 13         \/\/\/ <summary>\n 14         \/\/\/ \u5b9a\u4e49\u4e00\u4e2a\u6570\u7ec4\u6765\u5b58\u653e\u8282\u70b9\n 15         \/\/\/ <\/summary>\n 16         private List<HeapNode> nodeList = new List<HeapNode>();\n 17 \n 18         #region \u5806\u8282\u70b9\u5b9a\u4e49\n 19         \/\/\/ <summary>\n 20         \/\/\/ \u5806\u8282\u70b9\u5b9a\u4e49\n 21         \/\/\/ <\/summary>\n 22         public class HeapNode\n 23         {\n 24             \/\/\/ <summary>\n 25             \/\/\/ \u5b9e\u4f53\u6570\u636e\n 26             \/\/\/ <\/summary>\n 27             public T t { get; set; }\n 28 \n 29             \/\/\/ <summary>\n 30             \/\/\/ \u4f18\u5148\u7ea7\u522b 1-10\u4e2a\u7ea7\u522b (\u4f18\u5148\u7ea7\u522b\u9012\u589e)\n 31             \/\/\/ <\/summary>\n 32             public int level { get; set; }\n 33 \n 34             public HeapNode(T t, int level)\n 35             {\n 36                 this.t = t;\n 37                 this.level = level;\n 38             }\n 39 \n 40             public HeapNode() { }\n 41         }\n 42         #endregion\n 43 \n 44         #region  \u6dfb\u52a0\u64cd\u4f5c\n 45         \/\/\/ <summary>\n 46         \/\/\/ \u6dfb\u52a0\u64cd\u4f5c\n 47         \/\/\/ <\/summary>\n 48         public void Eequeue(T t, int level = 1)\n 49         {\n 50             \/\/\u5c06\u5f53\u524d\u8282\u70b9\u8ffd\u52a0\u5230\u5806\u5c3e\n 51             nodeList.Add(new HeapNode(t, level));\n 52 \n 53             \/\/\u5982\u679c\u53ea\u6709\u4e00\u4e2a\u8282\u70b9\uff0c\u5219\u4e0d\u9700\u8981\u8fdb\u884c\u7b5b\u64cd\u4f5c\n 54             if (nodeList.Count == 1)\n 55                 return;\n 56 \n 57             \/\/\u83b7\u53d6\u6700\u540e\u4e00\u4e2a\u975e\u53f6\u5b50\u8282\u70b9\n 58             int parent = nodeList.Count \/ 2 - 1;\n 59 \n 60             \/\/\u5806\u8c03\u6574\n 61             UpHeapAdjust(nodeList, parent);\n 62         }\n 63         #endregion\n 64 \n 65         #region \u5bf9\u5806\u8fdb\u884c\u4e0a\u6ee4\u64cd\u4f5c\uff0c\u4f7f\u5f97\u6ee1\u8db3\u5806\u6027\u8d28\n 66         \/\/\/ <summary>\n 67         \/\/\/ \u5bf9\u5806\u8fdb\u884c\u4e0a\u6ee4\u64cd\u4f5c\uff0c\u4f7f\u5f97\u6ee1\u8db3\u5806\u6027\u8d28\n 68         \/\/\/ <\/summary>\n 69         \/\/\/ <param name=\"nodeList\"><\/param>\n 70         \/\/\/ <param name=\"index\">\u975e\u53f6\u5b50\u8282\u70b9\u7684\u4e4b\u540e\u6307\u9488\uff08\u8fd9\u91cc\u8981\u6ce8\u610f\uff1a\u6211\u4eec\n 71         \/\/\/ \u7684\u7b5b\u64cd\u4f5c\u65f6\u9488\u5bf9\u975e\u53f6\u8282\u70b9\u7684\uff09\n 72         \/\/\/ <\/param>\n 73         public void UpHeapAdjust(List<HeapNode> nodeList, int parent)\n 74         {\n 75             while (parent >= 0)\n 76             {\n 77                 \/\/\u5f53\u524dindex\u8282\u70b9\u7684\u5de6\u5b69\u5b50\n 78                 var left = 2 * parent + 1;\n 79 \n 80                 \/\/\u5f53\u524dindex\u8282\u70b9\u7684\u53f3\u5b69\u5b50\n 81                 var right = left + 1;\n 82 \n 83                 \/\/parent\u5b50\u8282\u70b9\u4e2d\u6700\u5927\u7684\u5b69\u5b50\u8282\u70b9\uff0c\u65b9\u4fbf\u4e8eparent\u8fdb\u884c\u6bd4\u8f83\n 84                 \/\/\u9ed8\u8ba4\u4e3aleft\u8282\u70b9\n 85                 var min = left;\n 86 \n 87                 \/\/\u5224\u65ad\u5f53\u524d\u8282\u70b9\u662f\u5426\u6709\u53f3\u5b69\u5b50\n 88                 if (right < nodeList.Count)\n 89                 {\n 90                     \/\/\u5224\u65adparent\u8981\u6bd4\u8f83\u7684\u6700\u5927\u5b50\u8282\u70b9\n 91                     min = nodeList[left].level < nodeList[right].level ? left : right;\n 92                 }\n 93 \n 94                 \/\/\u5982\u679cparent\u8282\u70b9\u5927\u4e8e\u5b83\u7684\u67d0\u4e2a\u5b50\u8282\u70b9\u7684\u8bdd\uff0c\u6b64\u65f6\u7b5b\u64cd\u4f5c\n 95                 if (nodeList[parent].level > nodeList[min].level)\n 96                 {\n 97                     \/\/\u5b50\u8282\u70b9\u548c\u7236\u8282\u70b9\u8fdb\u884c\u4ea4\u6362\u64cd\u4f5c\n 98                     var temp = nodeList[parent];\n 99                     nodeList[parent] = nodeList[min];\n100                     nodeList[min] = temp;\n101 \n102                     \/\/\u7ee7\u7eed\u8fdb\u884c\u66f4\u4e0a\u4e00\u5c42\u7684\u8fc7\u6ee4\n103                     parent = (int)Math.Ceiling(parent \/ 2d) - 1;\n104                 }\n105                 else\n106                 {\n107                     break;\n108                 }\n109             }\n110         }\n111         #endregion\n112 \n113         #region \u4f18\u5148\u961f\u5217\u7684\u51fa\u961f\u64cd\u4f5c\n114         \/\/\/ <summary>\n115         \/\/\/ \u4f18\u5148\u961f\u5217\u7684\u51fa\u961f\u64cd\u4f5c\n116         \/\/\/ <\/summary>\n117         \/\/\/ <returns><\/returns>\n118         public HeapNode Dequeue()\n119         {\n120             if (nodeList.Count == 0)\n121                 return null;\n122 \n123             \/\/\u51fa\u961f\u5217\u64cd\u4f5c\uff0c\u5f39\u51fa\u6570\u636e\u5934\u5143\u7d20\n124             var pop = nodeList[0];\n125 \n126             \/\/\u7528\u5c3e\u5143\u7d20\u586b\u5145\u5934\u5143\u7d20\n127             nodeList[0] = nodeList[nodeList.Count - 1];\n128 \n129             \/\/\u5220\u9664\u5c3e\u8282\u70b9\n130             nodeList.RemoveAt(nodeList.Count - 1);\n131 \n132             \/\/\u7136\u540e\u4ece\u6839\u8282\u70b9\u4e0b\u6ee4\u5806\n133             DownHeapAdjust(nodeList, 0);\n134 \n135             return pop;\n136         }\n137         #endregion\n138 \n139         #region  \u5bf9\u5806\u8fdb\u884c\u4e0b\u6ee4\u64cd\u4f5c\uff0c\u4f7f\u5f97\u6ee1\u8db3\u5806\u6027\u8d28\n140         \/\/\/ <summary>\n141         \/\/\/ \u5bf9\u5806\u8fdb\u884c\u4e0b\u6ee4\u64cd\u4f5c\uff0c\u4f7f\u5f97\u6ee1\u8db3\u5806\u6027\u8d28\n142         \/\/\/ <\/summary>\n143         \/\/\/ <param name=\"nodeList\"><\/param>\n144         \/\/\/ <param name=\"index\">\u975e\u53f6\u5b50\u8282\u70b9\u7684\u4e4b\u540e\u6307\u9488\uff08\u8fd9\u91cc\u8981\u6ce8\u610f\uff1a\u6211\u4eec\n145         \/\/\/ \u7684\u7b5b\u64cd\u4f5c\u65f6\u9488\u5bf9\u975e\u53f6\u8282\u70b9\u7684\uff09\n146         \/\/\/ <\/param>\n147         public void DownHeapAdjust(List<HeapNode> nodeList, int parent)\n148         {\n149             while (2 * parent + 1 < nodeList.Count)\n150             {\n151                 \/\/\u5f53\u524dindex\u8282\u70b9\u7684\u5de6\u5b69\u5b50\n152                 var left = 2 * parent + 1;\n153 \n154                 \/\/\u5f53\u524dindex\u8282\u70b9\u7684\u53f3\u5b69\u5b50\n155                 var right = left + 1;\n156 \n157                 \/\/parent\u5b50\u8282\u70b9\u4e2d\u6700\u5927\u7684\u5b69\u5b50\u8282\u70b9\uff0c\u65b9\u4fbf\u4e8eparent\u8fdb\u884c\u6bd4\u8f83\n158                 \/\/\u9ed8\u8ba4\u4e3aleft\u8282\u70b9\n159                 var min = left;\n160 \n161                 \/\/\u5224\u65ad\u5f53\u524d\u8282\u70b9\u662f\u5426\u6709\u53f3\u5b69\u5b50\n162                 if (right < nodeList.Count)\n163                 {\n164                     \/\/\u5224\u65adparent\u8981\u6bd4\u8f83\u7684\u6700\u5927\u5b50\u8282\u70b9\n165                     min = nodeList[left].level < nodeList[right].level ? left : right;\n166                 }\n167 \n168                 \/\/\u5982\u679cparent\u8282\u70b9\u5c0f\u4e8e\u5b83\u7684\u67d0\u4e2a\u5b50\u8282\u70b9\u7684\u8bdd\uff0c\u6b64\u65f6\u7b5b\u64cd\u4f5c\n169                 if (nodeList[parent].level > nodeList[min].level)\n170                 {\n171                     \/\/\u5b50\u8282\u70b9\u548c\u7236\u8282\u70b9\u8fdb\u884c\u4ea4\u6362\u64cd\u4f5c\n172                     var temp = nodeList[parent];\n173                     nodeList[parent] = nodeList[min];\n174                     nodeList[min] = temp;\n175 \n176                     \/\/\u7ee7\u7eed\u8fdb\u884c\u66f4\u4e0b\u4e00\u5c42\u7684\u8fc7\u6ee4\n177                     parent = min;\n178                 }\n179                 else\n180                 {\n181                     break;\n182                 }\n183             }\n184         }\n185         #endregion\n186 \n187         #region \u83b7\u53d6\u5143\u7d20\u5e76\u4e0b\u964d\u5230\u6307\u5b9a\u7684level\u7ea7\u522b\n188         \/\/\/ <summary>\n189         \/\/\/ \u83b7\u53d6\u5143\u7d20\u5e76\u4e0b\u964d\u5230\u6307\u5b9a\u7684level\u7ea7\u522b\n190         \/\/\/ <\/summary>\n191         \/\/\/ <returns><\/returns>\n192         public HeapNode GetAndDownPriority(int level)\n193         {\n194             if (nodeList.Count == 0)\n195                 return null;\n196 \n197             \/\/\u83b7\u53d6\u5934\u5143\u7d20\n198             var pop = nodeList[0];\n199 \n200             \/\/\u8bbe\u7f6e\u6307\u5b9a\u4f18\u5148\u7ea7\uff08\u5982\u679c\u4e3a MinValue \u5219\u4e3a -- \u64cd\u4f5c\uff09\n201             nodeList[0].level = level == int.MinValue ? --nodeList[0].level : level;\n202 \n203             \/\/\u4e0b\u6ee4\u5806\n204             DownHeapAdjust(nodeList, 0);\n205 \n206             return nodeList[0];\n207         }\n208         #endregion\n209 \n210         #region \u83b7\u53d6\u5143\u7d20\u5e76\u4e0b\u964d\u4f18\u5148\u7ea7\n211         \/\/\/ <summary>\n212         \/\/\/ \u83b7\u53d6\u5143\u7d20\u5e76\u4e0b\u964d\u4f18\u5148\u7ea7\n213         \/\/\/ <\/summary>\n214         \/\/\/ <returns><\/returns>\n215         public HeapNode GetAndDownPriority()\n216         {\n217             \/\/\u4e0b\u964d\u4e00\u4e2a\u4f18\u5148\u7ea7\n218             return GetAndDownPriority(int.MinValue);\n219         }\n220         #endregion\n221 \n222         #region \u8fd4\u56de\u5f53\u524d\u4f18\u5148\u961f\u5217\u4e2d\u7684\u5143\u7d20\u4e2a\u6570\n223         \/\/\/ <summary>\n224         \/\/\/ \u8fd4\u56de\u5f53\u524d\u4f18\u5148\u961f\u5217\u4e2d\u7684\u5143\u7d20\u4e2a\u6570\n225         \/\/\/ <\/summary>\n226         \/\/\/ <returns><\/returns>\n227         public int Count()\n228         {\n229             return nodeList.Count;\n230         }\n231         #endregion\n232     }\n233 }\n\n\u6587\u7ae0\u6765\u81ea\u7f51\u7edc\u535a\u5ba2\uff1ahttps:\/\/www.cnblogs.com\/huangxincheng\/archive\/2012\/12\/17\/2821132.html\uff0c\u7248\u6743\u5f52\u4f5c\u8005\u6240\u6709\u3002<\/pre>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
\u8fd9\u7bc7\u6211\u4eec\u770b\u770b\u7b2c\u4e8c\u79cd\u751f\u6210\u6811\u7684Kruskal\u7b97\u6cd5\uff0c\u8fd9\u4e2a\u7b97\u6cd5\u7684\u9b45\u529b\u5728\u4e8e\u6211\u4eec\u53ef\u4ee5\u6253\u4e00\u4e0b\u7b97\u6cd5\u548c\u6570\u636e\u7ed3\u6784\u7684\u7ec4\u5408\u62f3\uff0c\u5f88\u6709\u610f\u601d … \u9605\u8bfb\u66f4\u591a<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[5],"tags":[627],"class_list":["post-2075","post","type-post","status-publish","format-standard","hentry","category-jishu","tag-kruskal"],"aioseo_notices":[],"jetpack_featured_media_url":"","jetpack-related-posts":[],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/posts\/2075","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/comments?post=2075"}],"version-history":[{"count":4,"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/posts\/2075\/revisions"}],"predecessor-version":[{"id":9096,"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/posts\/2075\/revisions\/9096"}],"wp:attachment":[{"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/media?parent=2075"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/categories?post=2075"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/tags?post=2075"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}