{"id":177,"date":"2021-11-21T12:56:13","date_gmt":"2021-11-21T12:56:13","guid":{"rendered":"http:\/\/47.103.123.166\/?p=177"},"modified":"2021-11-21T12:56:13","modified_gmt":"2021-11-21T12:56:13","slug":"%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%e5%ad%a6%e4%b9%a04-%e5%9b%be","status":"publish","type":"post","link":"http:\/\/47.103.123.166\/?p=177","title":{"rendered":"\u6570\u636e\u7ed3\u6784\u5b66\u4e604\u2014\u2014\u56fe"},"content":{"rendered":"

1 \u56fe\u7684\u7ed3\u6784<\/h1>\n

1.1 \u56fe\u7684\u903b\u8f91\u7ed3\u6784<\/h2>\n
    \n
  1. \u56fe\uff08graph\uff09\u7531\u9876\u70b9\uff08vertex\uff09\u7684\u975e\u7a7a\u96c6\u5408\u548c\u9876\u70b9\u4e4b\u95f4\u7684\u8fb9\uff08edge\uff09\u7684\u96c6\u5408\u7ec4\u6210\u3002<\/li>\n<\/ol>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
    <\/th>\n<\/th>\n<\/tr>\n<\/thead>\n
    \u8fb9<\/td>\n\u65e0\u5411(undirected)\u8fb9\u3001\u6709\u5411\u8fb9<\/td>\n<\/tr>\n
    \u56fe<\/td>\n\u65e0\u5411\u56fe\u3001\u6709\u5411\u56fe\u3001\u7a20\u5bc6(dense)\u56fe\u3001\u7a00\u758f(sparse)\u56fe \u3001\u5b50\u56fe(subgraph)<\/td>\n<\/tr>\n
    \u7b80\u5355\u56fe<\/td>\n\u4e0d\u5b58\u5728\u9876\u70b9\u5230\u81ea\u8eab\u7684\u8fb9\uff0c\u4e0d\u5b58\u5728\u91cd\u590d\u51fa\u73b0\u7684\u8fb9<\/td>\n<\/tr>\n
    \u5b8c\u5168\u56fe<\/td>\n\u4efb\u610f\u4e24\u9876\u70b9\u5b58\u5728\u8fb9\uff0c\u65e0\u5411\u5b8c\u5168\u56fe\uff08\u6570\u91cf\u4e3a (n-1)n\/2 \uff09\u3001\u6709\u5411\u5b8c\u5168\u56fe\uff08\u53cc\u5411 \u6570\u91cf\u4e3a (n-1)n \uff09<\/td>\n<\/tr>\n
    \u90bb\u63a5\u4e0e\u4f9d\u9644<\/td>\n\u65e0\u5411\uff1a\u9876\u70b9\u4e92\u4e3a\u90bb\u63a5(adjacent)\u70b9\uff0c\u8fb9\u4f9d\u9644(adhere)\u4e8e\u4e24\u9876\u70b9\uff1b\u6709\u5411\uff1a\u8d77\u70b9\u90bb\u63a5\u5230\u7ec8\u70b9\uff0c\u7ec8\u70b9\u662f\u8d77\u70b9\u7684\u90bb\u63a5\u70b9<\/td>\n<\/tr>\n
    \u5ea6<\/td>\n\u65e0\u5411\uff1a\u4f9d\u9644\u4e8e\u9876\u70b9\u7684\u8fb9\u7684\u6570\u91cf\uff1b\u6709\u5411\uff1a\u51fa\u5ea6\uff08\u4f5c\u4e3a\u8d77\u70b9\uff09\u3001\u5165\u5ea6\uff08\u4f5c\u4e3a\u7ec8\u70b9\uff09<\/td>\n<\/tr>\n
    \u6743\u503c\u4e0e\u7f51<\/td>\n\u6743\u503c(weight)\uff1a\u8fb9\u7684\u610f\u4e49\uff1b\u7f51\uff1a\u5e26\u6743\u503c\u7684\u56fe\uff08\u6709\u5411\u7f51\u3001\u65e0\u5411\u7f51\uff09<\/td>\n<\/tr>\n
    \u8def\u5f84<\/td>\n\u8def\u5f84\u3001\u8def\u5f84\u957f\u5ea6\u3001\u56de\u8def\uff08\u8def\u5f84\u8d77\u7ec8\u70b9\u76f8\u540c\uff09\u3001\u7b80\u5355\u8def\u5f84\uff08\u65e0\u91cd\u590d\u9876\u70b9\uff09\u3001\u7b80\u5355\u56de\u8def\uff08\u53ea\u91cd\u590d\u8d77\u7ec8\u70b9\uff09<\/td>\n<\/tr>\n
    \u8fde\u901a\u56fe \u8fde\u901a\u5206\u91cf<\/td>\n\u65e0\u5411\u56fe\u4e2d\uff0c\u4efb\u610f\u4e24\u9876\u70b9\u5b58\u5728\u8def\u5f84\uff1b\u975e\u8fde\u901a\u56fe\u7684\u6781\u5927\u8fde\u901a\u5b50\u56fe\u4e3a\u8fde\u901a\u5206\u91cf<\/td>\n<\/tr>\n
    \u5f3a\u8fde\u901a\u56fe \u5f3a\u8fde\u901a\u5206\u91cf<\/td>\n\u6709\u5411\u56fe\u4e2d\uff0c\u4efb\u610f\u4e24\u9876\u70b9\u53cc\u5411\u5b58\u5728\u8def\u5f84\uff1b\u975e\u5f3a\u8fde\u901a\u56fe\u7684\u6781\u5927\u5f3a\u8fde\u901a\u5b50\u56fe\u4e3a\u5f3a\u8fde\u901a\u5206\u91cf<\/td>\n<\/tr>\n
    \u751f\u6210\u6811<\/td>\n\u8fde\u901a\u56fe\u7684\u6781\u5c0f\u8fde\u901a\u5b50\u56fe\uff08n\u4e2a\u9876\u70b9\u548c\u6700\u5c11\u7684\u8fb9\uff09\u3001\u6709\u5411\u56fe\u7684\u5b50\u56fe\uff08\u5168\u90e8\u9876\u70b9\u4e14\u4ec5\u4e00\u9876\u70b9\u5165\u5ea6\u4e3a0\uff0c\u5176\u4f59\u5165\u5ea6\u4e3a1\uff09<\/td>\n<\/tr>\n
    \u751f\u6210\u68ee\u6797<\/td>\n\u8fde\u901a\u5206\u91cf\u7684\u751f\u6210\u6811\uff0c\u7ec4\u6210\u68ee\u6797<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
      \n
    1. \u904d\u5386\u7684\u65b9\u5f0f
      \n♥ \u5bfb\u627e\u90bb\u63a5\u70b9
      \n♥ \u8bbe\u7f6e\u8bbf\u95ee\u6807\u5fd7\uff0c\u907f\u514d\u91cd\u590d\u8bbf\u95ee
      \n♥ \u591a\u4e2a\u90bb\u63a5\u70b9\u9009\u62e9\u65b9\u5f0f\u4e0d\u540c\uff0c\u5206\u4e3a\u6df1\u5ea6\u4f18\u5148\uff08\u63a8\u8350\u4f7f\u7528\u6808\uff09\u548c\u5e7f\u5ea6\u4f18\u5148\uff08\u63a8\u8350\u4f7f\u7528\u961f\u5217\uff09<\/li>\n<\/ol>\n

      1.2 \u56fe\u7684\u5b58\u50a8\u7ed3\u6784<\/h2>\n

      \u90bb\u63a5\u77e9\u9635\uff08\u6805\u683c\uff09<\/h3>\n
        \n
      1. \u6df1\u5ea6\u4f18\u5148\u904d\u5386\n
        \/\/1\u3001\u521d\u59cb\u5316\u5404\u9876\u70b9\u672a\u88ab\u8bbf\u95ee\n    for(int i=0;i<vertexNum;i++)\n        visited[i]=0;\n\/\/2\u3001\u7b2c\u4e00\u4e2a\u9876\u70b9\u5165\u6808\n    stack<int> st;\n    for(int i=0;i<vertexNum;i++)\n        if(visited[i]==0)\n        {\n            st.push(i);     \n            DFS(st.top());\n            st.pop();\n        }\n\/\/3\u3001\u9012\u5f52\n    void DFS(int v)\n    {\n        visited[v]=1;               \/\/\u786e\u8ba4\u5df2\u904d\u5386\n        for(int i=0;i<vertexNum;i++)\n        {\n            if((visited[i]==0) && (arc[v][i]==1))\/\/\u627e\u5230\u8be5\u9876\u70b9\u7684\u90bb\u63a5\u70b9\n            {\n                st.push(i);\n                DFS(st.top());\n                st.pop();\n            }\n        }\n    }<\/code><\/pre>\n<\/li>\n
      2. \u5e7f\u5ea6\u4f18\u5148\u904d\u5386\n
        \/\/1\u3001\u521d\u59cb\u5316\u5404\u9876\u70b9\u672a\u88ab\u8bbf\u95ee\n    for(int i=0;i<vertexNum;i++)\n        visited[i]=0;\n\/\/2\u3001\u7b2c\u4e00\u4e2a\u9876\u70b9\u5165\u961f\n    queue<int> que;\n    for(int i=0;i<vertexNum;i++)\n        if(visited[i]==0)\n        {\n            que.push(i);\n            visited[i]=1;\n            break;\n        }\n\/\/3\u3001\u5faa\u73af\uff1a\u4f9d\u6b21\u5165\u961f\uff0c\u4f9d\u6b21\u5904\u7406\n    while(!que.empty()) \n    {\n        int v = que.front();\n        for(int i=0;i<vertexNum;i++)\n        {\n            if((visited[i]==0) && (arc[v][i]==1))\/\/\u627e\u5230\u8be5\u9876\u70b9\u7684\u90bb\u63a5\u70b9\n            {\n                que.push(i);\n                visited[i]=1;\n            }\n        }\n        que.pop();\n    }<\/code><\/pre>\n<\/li>\n<\/ol>\n
        1.3 \u6d4b\u8bd5\u7a0b\u5e8f<\/h2>\n
        \u90bb\u63a5\u77e9\u9635 \u6df1\u5ea6\u4f18\u5148\u904d\u5386<\/h3>\n
        \u9488\u5bf9\u65e0\u5411\u8fde\u901a\u56fe\u3002<\/p>\n
        #include <iostream>\n#include <stack>\n\nusing namespace std;\n\nint vertexNum=5;\nint visited[5]={0};\nint arc[5][5]={0,1,0,1,1,   \/\/\u90bb\u63a5\u77e9\u9635\n               1,0,1,0,1,\n               0,1,0,0,0,\n               1,0,0,0,0,\n               1,1,0,0,0};\nstack<int> st;\n\nvoid DFS(int v)\n{\n    visited[v]=1;               \/\/\u786e\u8ba4\u5df2\u904d\u5386\n    for(int i=0;i<vertexNum;i++)\n    {\n        if((visited[i]==0) && (arc[v][i]==1))\/\/\u627e\u5230\u8be5\u9876\u70b9\u7684\u90bb\u63a5\u70b9\n        {\n            st.push(i);\n            cout<<\"push:\"<<i<<\" \"<<st.size()<<endl; \n            DFS(st.top());\n            st.pop();\n            cout<<\"pop:\"<<i<<\" \"<<st.size()<<endl;\n        }\n    }\n}\n\nint main()\n{\n    \/\/1\u3001\u521d\u59cb\u5316\u5404\u9876\u70b9\u672a\u88ab\u8bbf\u95ee\n        for(int i=0;i<vertexNum;i++)\n            visited[i]=0;\n    \/\/2\u3001\u7b2c\u4e00\u4e2a\u9876\u70b9\u5165\u6808\n        for(int i=0;i<vertexNum;i++)\n        {\n            if(visited[i]==0)\n            {\n                st.push(i); \n                cout<<\"push:\"<<i<<\" \"<<st.size()<<endl; \n                DFS(st.top());\n                st.pop();\n                cout<<\"pop:\"<<i<<\" \"<<st.size()<<endl;  \n            }\n        }\n\n}<\/code><\/pre>\n
        \u90bb\u63a5\u77e9\u9635 \u5e7f\u5ea6\u4f18\u5148\u904d\u5386<\/h3>\n
        \u9488\u5bf9\u65e0\u5411\u8fde\u901a\u56fe\u3002<\/p>\n
        #include <iostream>\n#include <queue>\n\nusing namespace std;\n\nint vertexNum=5;\nint visited[5]={0};\nint arc[5][5]={0,1,0,1,1,   \/\/\u90bb\u63a5\u77e9\u9635\n               1,0,1,0,1,\n               0,1,0,0,0,\n               1,0,0,0,0,\n               1,1,0,0,0};\n\nint main()\n{\n    \/\/1\u3001\u521d\u59cb\u5316\u5404\u9876\u70b9\u672a\u88ab\u8bbf\u95ee\n        for(int i=0;i<vertexNum;i++)\n            visited[i]=0;\n    \/\/2\u3001\u7b2c\u4e00\u4e2a\u9876\u70b9\u5165\u961f\n        queue<int> que;\n        for(int i=0;i<vertexNum;i++)\n            if(visited[i]==0)\n            {\n                que.push(i);\n                visited[i]=1;\n                cout<<\"push:\"<<i<<\" \"<<que.size()<<endl;\n                break;\n            }\n\n    \/\/3\u3001\u5faa\u73af:\u4f9d\u6b21\u5165\u961f\uff0c\u4f9d\u6b21\u5904\u7406\n        while(!que.empty()) \n        {\n            int v = que.front();\n            cout<<\"front:\"<<que.front()<<\" \"<<que.size()<<endl; \n\n            for(int i=0;i<vertexNum;i++)\n            {\n                if((visited[i]==0) && (arc[v][i]==1))\/\/\u627e\u5230\u8be5\u9876\u70b9\u7684\u90bb\u63a5\u70b9\n                {\n                    que.push(i);\n                    visited[i]=1;\n                    cout<<\"push:\"<<i<<\" \"<<que.size()<<endl;    \n                }\n            }\n            que.pop();\n        }        \n}<\/code><\/pre>\n
        2 \u6700\u5c0f\u751f\u6210\u6811<\/h1>\n
        2.1 \u6700\u5c0f\u751f\u6210\u6811\uff08MST\uff0cminimal spanning tree\uff09<\/h2>\n
        \u65e0\u5411\u8fde\u901a\u7f51\u7684\u751f\u6210\u6811\u4e2d\uff0c\u6743\u503c\u4ee3\u4ef7\u6700\u5c0f\u7684\u751f\u6210\u6811\uff0c\u79f0\u4e3a\u6700\u5c0f\u6743\u91cd\u751f\u6210\u6811\uff0c\u7b80\u79f0\u6700\u5c0f\u751f\u6210\u6811<\/strong>\u3002
        \n\uff08\u65e0\u5411\u56fe\uff0c\u8fde\u901a\u56fe\uff0c\u6743\u503c\u4e0e\u7f51\uff0c\u751f\u6210\u6811\uff09
        \n\u5e94\u7528\uff1an\u4e2a\u57ce\u5e02\u4e4b\u95f4\u94fa\u8bbe\u7535\u7f06\uff0c\u76ee\u6807\u4f7f\u5f97\u4efb\u610f\u4e24\u4e2a\u57ce\u5e02\u4e92\u901a\uff0c\u4e0d\u540c\u57ce\u5e02\u4e4b\u95f4\u94fa\u8bbe\u7535\u7f06\u4ee3\u4ef7\u4e0d\u540c\uff0c\u6c42\u4ee3\u4ef7\u6700\u5c0f\u7684\u94fa\u8bbe\u65b9\u6cd5\u3002\u8fd9\u662f\u4e00\u9053\u9762\u8bd5\u9898:(<\/p>\n
        2.2 Prim\u7b97\u6cd5<\/h2>\n
        \u57fa\u672c\u601d\u60f3<\/h3>\n
          \n
        1. \u8bbe\u65e0\u5411\u8fde\u901a\u7f51 G=(V,E)<\/em><\/strong> \uff0c\u6700\u5c0f\u751f\u6210\u6811 T=(U,TE)<\/em><\/strong><\/li>\n
        2. T<\/em><\/strong> \u521d\u503c\uff1a U={v0}<\/em><\/strong> \uff0cv0\u2208V<\/em><\/strong>\uff0cTE<\/em><\/strong> \u4e3a\u7a7a<\/li>\n
        3. \u91cd\u590d\uff1a
          \n\u5bf9\u6bcf\u4e00\u4e2a V-U<\/em><\/strong> \u4e2d\u7684\u9876\u70b9\uff08\u8bben\u4e2a\u9876\u70b9\uff09\uff0c\u904d\u5386 U<\/em><\/strong> \u4e2d\u9876\u70b9\uff0c\u627e\u5230\u4e00\u6761\u6700\u77ed\u8fb9\uff0cn\u4e2a\u9876\u70b9\u5f62\u6210\u4e00\u4e2a\u5019\u9009\u6700\u77ed\u8fb9\u96c6<\/strong>
          \n\u5728\u5019\u9009\u6700\u77ed\u8fb9\u96c6\u4e2d\uff0c\u627e\u5230\u6700\u6700\u77ed\u7684\u4e00\u6761\u8fb9
          \n\u628a V-U<\/em><\/strong>  \u4e2d\u7684\u8fd9\u4e00\u70b9\uff0c\u653e\u5165 U<\/em><\/strong> \uff0c\u540c\u65f6\uff0c\u628a\u5bf9\u5e94\u8fb9\u653e\u5165 TE<\/em><\/strong>  \uff0c\u76f4\u5230 V<\/em><\/strong>  \u548c U<\/em><\/strong>  \u76f8\u7b49\u3002<\/li>\n
        4. \u7b97\u6cd5\u590d\u6742\u5ea6O(n2)\uff0c\u9002\u4e8e\u7a20\u5bc6\u8fde\u901a\u7f51\u3002<\/li>\n
        5. \u5173\u952e\uff1a\u5019\u9009\u6700\u77ed\u8fb9\u96c6\uff08\u57fa\u672c\u8fc7\u7a0b\u7684case\u548c\u4ee3\u7801\u7684shortEdge\u6570\u7ec4\uff09<\/li>\n<\/ol>\n
          \u57fa\u672c\u8fc7\u7a0b<\/h3>\n
          \"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"————————->\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n
            \n
          1. \u521d\u59cb\u72b6\u6001
            \n\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/li>\n
          2. \u5c06\u70b9 v5<\/strong> \u548c\u8fb9 (v0,v5)2<\/strong> \u52a0\u5165\u6700\u5c0f\u751f\u6210\u6811
            \n\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/li>\n
          3. \u5c06\u70b9 v1<\/strong> \u548c\u8fb9 (v5,v1)1<\/strong> \u52a0\u5165\u6700\u5c0f\u751f\u6210\u6811
            \n\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/li>\n
          4. \u5c06\u70b9 v2<\/strong> \u548c\u8fb9 (v1,v2)2<\/strong> \u52a0\u5165\u6700\u5c0f\u751f\u6210\u6811
            \n\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/li>\n
          5. \u5c06\u70b9 v3<\/strong> \u548c\u8fb9 (v5,v3)4<\/strong> \u52a0\u5165\u6700\u5c0f\u751f\u6210\u6811
            \n\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/li>\n
          6. \u5c06\u70b9 v4<\/strong> \u548c\u8fb9 (v3,v4)1<\/strong> \u52a0\u5165\u6700\u5c0f\u751f\u6210\u6811
            \n\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/li>\n<\/ol>\n
            \u4ee3\u7801\uff08\u975e\u6d4b\u8bd5\uff09<\/h3>\n
            \/\/1\u3001\u521d\u59cb\u5316\u8f85\u52a9\u6570\u7ec4\uff0c\u8f85\u52a9\u6570\u7ec4\u7528\u4e8e\u6807\u8bb0 V-U\u4e2d\u9876\u70b9 \u5230 U\u4e2d\u9876\u70b9 \u7684 \u6700\u77ed\u4ee3\u4ef7\u548c\u5bf9\u5e94\u9876\u70b9\uff0c\u529f\u80fd\u7c7b\u4f3c\u4e8e\u57fa\u672c\u8fc7\u7a0b\u4e2d\u7684cost\nfor(int i=1;i<vertexNum;i++)\n{\n    \/\/\u521d\u59cb\u53d6v0\u52a0\u5165\u96c6\u5408U\uff0c\u56e0\u6b64\u6700\u77ed\u4ee3\u4ef7\u4f9d\u6b21\u662f\u4e0ev0\u7684\u4ee3\u4ef7\u503c\uff0c\u5bf9\u5e94\u9876\u70b9\u4e3ai\u548cv0\n    shortEdge[i].lowcost = arc[0][i];   \/\/V-U\u4e2d\u9876\u70b9 \u5230 U\u4e2d\u9876\u70b9 \u7684\u6700\u77ed\u4ee3\u4ef7\n    shortEdge[i].adjvex = 0;            \/\/V-U\u4e2d\u9876\u70b9 \u5230 U\u4e2d\u9876\u70b9 \u7684\u5bf9\u5e94\u9876\u70b9\n}\n\n\/\/2\u3001\u52a0\u5165\u96c6\u5408\u7684\u65b9\u5f0f\nshortEdge[0].lowcost = 0;               \/\/\u4ee3\u4ef7\u4e3a0\u65f6\uff0c\u8ba4\u4e3a\u6539\u9876\u70b9\u5df2\u7ecf\u5728\u6700\u5c0f\u751f\u6210\u6811\u4e2d\u4e86\uff0c\u8fd9\u91ccv0\u5df2\u7ecf\u5728\u5176\u4e2d\u4e86\n\n\/\/3\u3001\u5faa\u73af\nfor(int i=1;i<vertexNum;i++)            \/\/\u8fd9\u91cc\u662f\u5faa\u73afvertexNum-1\u6b21\uff0c\u6bcf\u6b21\u6dfb\u52a0\u4e00\u4e2a\u9876\u70b9\u5230U\n{\n    \/\/3.1\u3001\u6839\u636e\u8f85\u52a9\u6570\u7ec4\u786e\u5b9a\u6700\u6700\u77ed\u8fb9\n    int k;                              \/\/\u6700\u6700\u77ed\u8fb9\u5bf9\u5e94\u7684 V-U\u4e2d\u9876\u70b9\n    for(int j=1;j<vertexNum;j++)        \/\/\u521d\u59cb\u5316k\n        if(shortEdge[j].lowcost != 0)\n        { k=j; break; }\n    for(int j=1;j<vertexNum;j++)        \/\/\u66f4\u65b0k\n        if(shortEdge[j].lowcost != 0 && shortEdge[j].lowcost < shortEdge[k].lowcost)\n            k=j;\n\n    \/\/3.2\u3001\u52a0\u5165\u96c6\u5408\n    shortEdge[k].lowcost = 0;\n\n    \/\/3.3\u3001\u66f4\u65b0\u8f85\u52a9\u6570\u7ec4\n    for(int j=1;j<vertexNum;j++)\n        if(shortEdge[j].lowcost > arc[k][j])\/\/\u6bd4\u8f83\u65b0\u52a0\u5165\u7684\u9876\u70b9\uff0c\u662f\u5426\u4ee3\u4ef7\u66f4\u5c0f\uff08\u7c7b\u4f3c\u4e8eRRT*\u7684\u91cd\u9009\u7236\u8282\u70b9\uff09\n        {\n            shortEdge[j].lowcost = arc[k][j];   \/\/V-U\u4e2d\u9876\u70b9 \u5230 U\u4e2d\u9876\u70b9 \u7684\u6700\u77ed\u4ee3\u4ef7\n            shortEdge[j].adjvex = k;            \/\/V-U\u4e2d\u9876\u70b9 \u5230 U\u4e2d\u9876\u70b9 \u7684\u5bf9\u5e94\u9876\u70b9\n        }\n\n}\n<\/code><\/pre>\n
            2.3 Kruscal\u7b97\u6cd5<\/h2>\n
            \u57fa\u672c\u601d\u60f3<\/h3>\n
              \n
            1. \u8bbe\u65e0\u5411\u8fde\u901a\u7f51 G=(V,E)<\/em><\/strong> \uff0c\u6700\u5c0f\u751f\u6210\u6811 T=(U,TE)<\/em><\/strong><\/li>\n
            2. T<\/em><\/strong> \u521d\u503c\uff1a U=V<\/em><\/strong> \uff0cTE<\/em><\/strong> \u4e3a\u7a7a\uff0c\u5373\u6bcf\u4e2a\u9876\u70b9\u81ea\u6210\u4e00\u4e2a\u8fde\u901a\u5206\u91cf<\/li>\n
            3. \u5c06  E<\/em><\/strong> \u4e2d\u6743\u503c\u6709\u5c0f\u5230\u5927\u6392\u5e8f<\/li>\n
            4. \u91cd\u590d\uff1a
              \n\u5728  E<\/em><\/strong>  \u4e2d\u9009\u62e9\u6700\u77ed\u8fb9\uff0c\u5224\u65ad\u8be5\u8fb9\u7684\u4e24\u9876\u70b9\u662f\u5426\u5728\u4e24\u4e2a\u8fde\u901a\u5206\u91cf\u4e0a\u2014\u2014\u8fb9\u96c6\u6570\u7ec4<\/strong>
              \n\u662f\uff1a\u52a0\u5165 TE<\/em><\/strong>
              \n\u5426\uff1a\u820d\u5f03\u6b64\u8fb9<\/li>\n
            5. \u7b97\u6cd5\u590d\u6742\u5ea6O(elbe)\uff0c\u9002\u4e8e\u7a00\u758f\u8fde\u901a\u7f51\u3002<\/li>\n
            6. \u5173\u952e\uff1a\u8fb9\u96c6\u6570\u7ec4\uff0c\u5982\u4f55\u5224\u65ad\u4e24\u4e2a\u70b9\u662f\u5426\u5728\u4e0d\u540c\u7684\u8fde\u901a\u5206\u91cf\uff08\u5229\u7528\u8fb9\u96c6\u6570\u7ec4\uff09\u3002<\/li>\n<\/ol>\n
              \u57fa\u672c\u8fc7\u7a0b<\/h3>\n
              \"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"—\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\" —\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"
              \n\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"—\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"—\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n
              \u4ee3\u7801\uff08\u975e\u6d4b\u8bd5\uff09<\/h3>\n
              \/\/1\u3001\u5b9a\u4e49\u3001\u521d\u59cb\u5316\u3001\u6392\u5e8f\u4ece\u5c0f\u5230\u5927\u7684\u8fb9\u96c6\u6570\u7ec4\nstruct Edge\n{\n    Edge(){}\n    Edge(int from_,int to_,int cost_,bool ok_):from(from_),to(to_),cost(cost_),ok(ok_){}\n    int from;\n    int to;\n    int cost;\n    bool ok;\n};\n\nEdge edges[edgeNum];\nedges[0]=Edge{0,1,4,false};\/\/...\n\nbool cmp(const Edge &a,const Edge &b)\n    return a.cost<b.cost;\nsort(edges,edges+edgeNum,cmp);\/\/\u6309\u6743\u503c\u6392\u5e8f\n\n\/\/2\u3001\u904d\u5386\u8fb9\u96c6\u6570\u7ec4\nfor(int i=0;i<edgeNum;i++)\n{\n    \/\/2.1\u3001\u5224\u65ad\u8be5\u8fb9\u7684\u4e24\u4e2a\u9876\u70b9\u662f\u5426\u5728\u4e00\u4e2a\u8fde\u901a\u5206\u91cf\u4e2d\n    \/\/2.2\u3001\u5408\u5e76\u4e24\u4e2a\u8fde\u901a\u5206\u91cf\n    if(find_parent(edges[i].from)!=find_parent(edges[i].to))\n    {\n        merge(edges[i].from, edges[i].to); \n        edges[i].ok=true;\n    }\n    else\n        edges[i].ok=false;\n}\n<\/code><\/pre>\n
              2.4 \u6d4b\u8bd5\u7a0b\u5e8f<\/h2>\n
              Prim\u7b97\u6cd5<\/h3>\n
              #include <iostream>\n\nint vertexNum=6;\nint arc[6][6]={100,4,100,100,5,2,   \/\/\u90bb\u63a5\u77e9\u9635\n               4,100,2,100,100,1,\n               100,2,100,10,100,3,\n               100,100,10,100,1,4,\n               5,100,100,1,100,8,\n               2,1,3,4,8,100};\n\nstruct Cost\n{\n    int lowcost;\n    int adjvex;\n};\n\nint main()\n{\n\n    Cost shortEdge[vertexNum];\n\n    \/\/1\u3001\u521d\u59cb\u5316\u8f85\u52a9\u6570\u7ec4\uff0c\u8f85\u52a9\u6570\u7ec4\u7528\u4e8e\u6807\u8bb0 V-U\u4e2d\u9876\u70b9 \u5230 U\u4e2d\u9876\u70b9 \u7684 \u6700\u77ed\u4ee3\u4ef7\u548c\u5bf9\u5e94\u9876\u70b9\uff0c\u529f\u80fd\u7c7b\u4f3c\u4e8e\u57fa\u672c\u8fc7\u7a0b\u4e2d\u7684cost\n    for(int i=1;i<vertexNum;i++)\n    {\n        \/\/\u521d\u59cb\u53d6v0\u52a0\u5165\u96c6\u5408U\uff0c\u56e0\u6b64\u6700\u77ed\u4ee3\u4ef7\u4f9d\u6b21\u662f\u4e0ev0\u7684\u4ee3\u4ef7\u503c\uff0c\u5bf9\u5e94\u9876\u70b9\u4e3ai\u548cv0\n        shortEdge[i].lowcost = arc[0][i];               \/\/V-U\u4e2d\u9876\u70b9 \u5230 U\u4e2d\u9876\u70b9 \u7684\u6700\u77ed\u4ee3\u4ef7\n        shortEdge[i].adjvex = 0;                        \/\/V-U\u4e2d\u9876\u70b9 \u5230 U\u4e2d\u9876\u70b9 \u7684\u5bf9\u5e94\u9876\u70b9\n    }\n\n    \/\/2\u3001\u52a0\u5165\u96c6\u5408\u7684\u65b9\u5f0f\n    shortEdge[0].lowcost = 0;                           \/\/\u4ee3\u4ef7\u4e3a0\u65f6\uff0c\u8ba4\u4e3a\u6539\u9876\u70b9\u5df2\u7ecf\u5728\u6700\u5c0f\u751f\u6210\u6811\u4e2d\u4e86\uff0c\u8fd9\u91ccv0\u5df2\u7ecf\u5728\u5176\u4e2d\u4e86\n\n    \/\/3\u3001\u5faa\u73af\n    for(int i=1;i<vertexNum;i++)                        \/\/\u8fd9\u91cc\u662f\u5faa\u73afvertexNum-1\u6b21\uff0c\u6bcf\u6b21\u6dfb\u52a0\u4e00\u4e2a\u9876\u70b9\u5230U\n    {\n        \/\/3.1\u3001\u6839\u636e\u8f85\u52a9\u6570\u7ec4\u786e\u5b9a\u6700\u6700\u77ed\u8fb9\n        int k;                                          \/\/\u6700\u6700\u77ed\u8fb9\u5bf9\u5e94\u7684 V-U\u4e2d\u9876\u70b9\n        for(int j=1;j<vertexNum;j++)                    \/\/\u521d\u59cb\u5316k\n            if(shortEdge[j].lowcost != 0)\n            { \n                k=j; break; \n            }\n        for(int j=1;j<vertexNum;j++)                    \/\/\u66f4\u65b0k\n            if(shortEdge[j].lowcost != 0 && shortEdge[j].lowcost < shortEdge[k].lowcost)\n                k=j;\n\n        std::cout<<\"get vertex=\"<<k<<\" with \"<<shortEdge[k].adjvex<<\",cost=\"<<shortEdge[k].lowcost<<std::endl;\n        \/\/3.2\u3001\u52a0\u5165\u96c6\u5408\n        shortEdge[k].lowcost = 0;\n\n        \/\/3.3\u3001\u66f4\u65b0\u8f85\u52a9\u6570\u7ec4\n        for(int j=1;j<vertexNum;j++)\n            if(shortEdge[j].lowcost > arc[k][j])        \/\/\u6bd4\u8f83\u65b0\u52a0\u5165\u7684\u9876\u70b9\uff0c\u662f\u5426\u4ee3\u4ef7\u66f4\u5c0f\uff08\u7c7b\u4f3c\u4e8eRRT*\u7684\u91cd\u9009\u7236\u8282\u70b9\uff09\n            {\n                shortEdge[j].lowcost = arc[k][j];       \/\/V-U\u4e2d\u9876\u70b9 \u5230 U\u4e2d\u9876\u70b9 \u7684\u6700\u77ed\u4ee3\u4ef7\n                shortEdge[j].adjvex = k;                \/\/V-U\u4e2d\u9876\u70b9 \u5230 U\u4e2d\u9876\u70b9 \u7684\u5bf9\u5e94\u9876\u70b9\n            }\n\n    }\n\n    return 0;\n\n}<\/code><\/pre>\n
              Kruscal\u7b97\u6cd5<\/h3>\n
              #include <iostream>\n#include <algorithm>\n\nint vertexNum=6;\nint edgeNum=10;\nint arc[6][6]={100,4,100,100,5,2,   \/\/\u90bb\u63a5\u77e9\u9635\n               4,100,2,100,100,1,\n               100,2,100,10,100,3,\n               100,100,10,100,1,4,\n               5,100,100,1,100,8,\n               2,1,3,4,8,100};\nint parent[6];\n\n\/\/\u8fb9\u96c6\u6570\u7ec4\nstruct Edge\n{\n    Edge(){}\n    Edge(int from_,int to_,int cost_,bool ok_):from(from_),to(to_),cost(cost_),ok(ok_){}\n    int from;\n    int to;\n    int cost;\n    bool ok;\n};\n\n\/\/\u8fb9\u96c6\u6570\u7ec4\uff1a\u6210\u5458\u6392\u5e8f\u65b9\u5f0f\nbool cmp(const Edge &a,const Edge &b)\n{\n    return (a.cost) < (b.cost);\n}\n\n\/\/\u5e77\u67e5\u96c6\uff1a\u67e5\u627e\u9876\u5c42\u53cc\u4eb2\nint find_parent(int v)\n{\n    return parent[v]==v ? v : find_parent(parent[v]);\n}\n\n\/\/\u5e77\u67e5\u96c6\uff1a\u4fee\u6539\u9876\u5c42\u53cc\u4eb2\nvoid merge(int from,int to)\n{\n    parent[find_parent(to)]=find_parent(from);\n}\n\nint main()\n{\n\/\/1\u3001\u5b9a\u4e49\u3001\u521d\u59cb\u5316\u3001\u6392\u5e8f\u4ece\u5c0f\u5230\u5927\u7684\u8fb9\u96c6\u6570\u7ec4\n    Edge edges[edgeNum];\n    edges[0]=Edge{0,1,4,false};\n    edges[1]=Edge{0,4,5,false};\n    edges[2]=Edge{0,5,2,false};\n    edges[3]=Edge{1,2,2,false};\n    edges[4]=Edge{1,5,1,false};\n    edges[5]=Edge{2,3,10,false};\n    edges[6]=Edge{2,5,3,false};\n    edges[7]=Edge{3,4,1,false};\n    edges[8]=Edge{3,5,4,false};\n    edges[9]=Edge{4,5,8,false};\n\n    std::sort(edges,edges+edgeNum,cmp);\/\/\u6309\u6743\u503c\u6392\u5e8f\n\n\/\/2\u3001\u521d\u59cb\u5316\u6bcf\u4e2a\u9876\u70b9\u7684\u9876\u5c42\u53cc\u4eb2\u8282\u70b9\uff0c\u7528\u4e8e\u5224\u65ad\u662f\u5426\u5728\u4e00\u4e2a\u96c6\u5408\n    for(int i=0;i<vertexNum;i++)\n        parent[i]=i;\n\n\/\/3\u3001\u904d\u5386\u8fb9\u96c6\u6570\u7ec4\n    for(int i=0;i<edgeNum;i++)\n    {\n        \/\/3.1\u3001\u5224\u65ad\u8be5\u8fb9\u7684\u4e24\u4e2a\u9876\u70b9\u662f\u5426\u5728\u4e00\u4e2a\u8fde\u901a\u5206\u91cf\u4e2d\n        \/\/3.2\u3001\u5408\u5e76\u4e24\u4e2a\u8fde\u901a\u5206\u91cf\n        if(find_parent(edges[i].from)!=find_parent(edges[i].to))\n        {\n            merge(edges[i].from, edges[i].to); \n            edges[i].ok=true;\n        }\n        else\n            edges[i].ok=false;\n\n        std::cout<<\"get edge: from \"<<edges[i].from<<\" to \"<<edges[i].to\n                 <<\" cost:\"<<edges[i].cost<<\" ok:\"<<edges[i].ok<<std::endl;\n        for(int i=0;i<vertexNum;i++)\n            std::cout<<i<<\" parent:\"<<find_parent(i)<<std::endl;\n    }\n\n    return 0;\n}<\/code><\/pre>\n
              3 \u6700\u77ed\u8def\u5f84\u95ee\u9898<\/h1>\n
              3.1 Dijkstra\u7b97\u6cd5<\/h2>\n
                \n
              1. \u79fb\u6b65\u8fd9\u91cchttps:\/\/blog.csdn.net\/fangfang12138\/article\/details\/107949923<\/a><\/a><\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"
                1 \u56fe\u7684\u7ed3\u6784 1.1 \u56fe\u7684\u903b\u8f91\u7ed3\u6784 \u56fe\uff08graph\uff09\u7531\u9876\u70b9\uff08vertex\uff09\u7684\u975e\u7a7a\u96c6\u5408\u548c\u9876\u70b9\u4e4b\u95f4\u7684\u8fb9\uff08edge\uff09\u7684\u96c6\u5408\u7ec4\u6210\u3002 \u8fb9 \u65e0\u5411(undirected)\u8fb9\u3001\u6709\u5411\u8fb9 \u56fe \u65e0\u5411\u56fe\u3001\u6709\u5411\u56fe\u3001\u7a20\u5bc6(dense)\u56fe\u3001\u7a00\u758f(sparse)\u56fe \u3001\u5b50\u56fe(subgraph) \u7b80\u5355\u56fe \u4e0d\u5b58\u5728\u9876\u70b9\u5230\u81ea\u8eab\u7684\u8fb9\uff0c\u4e0d\u5b58\u5728\u91cd\u590d\u51fa\u73b0\u7684\u8fb9 \u5b8c\u5168\u56fe \u4efb\u610f\u4e24\u9876\u70b9\u5b58\u5728\u8fb9\uff0c\u65e0\u5411\u5b8c\u5168\u56fe\uff08\u6570\u91cf\u4e3a (n-1)n\/2 \uff09\u3001\u6709\u5411\u5b8c\u5168\u56fe\uff08\u53cc\u5411 \u6570\u91cf\u4e3a (n-1)n \uff09 \u90bb\u63a5\u4e0e\u4f9d\u9644 \u65e0\u5411\uff1a\u9876\u70b9\u4e92\u4e3a\u90bb\u63a5(adjacent)\u70b9\uff0c\u8fb9\u4f9d\u9644(adhere)\u4e8e\u4e24\u9876\u70b9\uff1b\u6709\u5411\uff1a\u8d77\u70b9\u90bb\u63a5\u5230\u7ec8\u70b9\uff0c\u7ec8\u70b9\u662f\u8d77\u70b9\u7684\u90bb\u63a5\u70b9 \u5ea6 \u65e0\u5411\uff1a\u4f9d\u9644\u4e8e\u9876\u70b9\u7684\u8fb9\u7684\u6570\u91cf\uff1b\u6709\u5411\uff1a\u51fa\u5ea6\uff08\u4f5c\u4e3a\u8d77\u70b9\uff09\u3001\u5165\u5ea6\uff08\u4f5c\u4e3a\u7ec8\u70b9\uff09 \u6743\u503c\u4e0e\u7f51 \u6743\u503c(weight)\uff1a\u8fb9\u7684\u610f\u4e49\uff1b\u7f51\uff1a\u5e26\u6743\u503c\u7684\u56fe\uff08\u6709\u5411\u7f51\u3001\u65e0\u5411\u7f51\uff09 \u8def\u5f84 \u8def\u5f84\u3001\u8def\u5f84\u957f\u5ea6\u3001\u56de\u8def\uff08\u8def\u5f84\u8d77\u7ec8\u70b9\u76f8\u540c\uff09\u3001\u7b80\u5355\u8def\u5f84\uff08\u65e0\u91cd\u590d\u9876\u70b9\uff09\u3001\u7b80\u5355\u56de\u8def\uff08\u53ea\u91cd\u590d\u8d77\u7ec8\u70b9\uff09 \u8fde\u901a\u56fe \u8fde\u901a\u5206\u91cf \u65e0\u5411\u56fe\u4e2d\uff0c\u4efb\u610f\u4e24\u9876\u70b9\u5b58\u5728\u8def\u5f84\uff1b\u975e\u8fde\u901a\u56fe\u7684\u6781\u5927\u8fde\u901a\u5b50\u56fe\u4e3a\u8fde\u901a\u5206\u91cf \u5f3a\u8fde\u901a\u56fe \u5f3a\u8fde\u901a\u5206\u91cf \u6709\u5411\u56fe\u4e2d\uff0c\u4efb\u610f\u4e24\u9876\u70b9\u53cc\u5411\u5b58\u5728\u8def\u5f84\uff1b\u975e\u5f3a\u8fde\u901a\u56fe\u7684\u6781\u5927\u5f3a\u8fde\u901a\u5b50\u56fe\u4e3a\u5f3a\u8fde\u901a\u5206\u91cf \u751f\u6210\u6811 \u8fde\u901a\u56fe\u7684\u6781\u5c0f\u8fde\u901a\u5b50\u56fe\uff08n\u4e2a\u9876\u70b9\u548c\u6700\u5c11\u7684\u8fb9\uff09\u3001\u6709\u5411\u56fe\u7684\u5b50\u56fe\uff08\u5168\u90e8\u9876\u70b9\u4e14\u4ec5\u4e00\u9876\u70b9\u5165\u5ea6\u4e3a0\uff0c\u5176\u4f59\u5165\u5ea6\u4e3a1\uff09 \u751f\u6210\u68ee\u6797 \u8fde\u901a\u5206\u91cf\u7684\u751f\u6210\u6811\uff0c\u7ec4\u6210\u68ee\u6797 \u904d\u5386\u7684\u65b9\u5f0f ♥ \u5bfb\u627e\u90bb\u63a5\u70b9 ♥ \u8bbe\u7f6e\u8bbf\u95ee\u6807\u5fd7\uff0c\u907f\u514d\u91cd\u590d\u8bbf\u95ee ♥ \u591a\u4e2a\u90bb\u63a5\u70b9\u9009\u62e9\u65b9\u5f0f\u4e0d\u540c\uff0c\u5206\u4e3a\u6df1\u5ea6\u4f18\u5148\uff08\u63a8\u8350\u4f7f\u7528\u6808\uff09\u548c\u5e7f\u5ea6\u4f18\u5148\uff08\u63a8\u8350\u4f7f\u7528\u961f\u5217\uff09 1.2 \u56fe\u7684\u5b58\u50a8\u7ed3\u6784 \u90bb\u63a5\u77e9\u9635\uff08\u6805\u683c\uff09 \u6df1\u5ea6\u4f18\u5148\u904d\u5386 \/\/1\u3001\u521d\u59cb\u5316\u5404\u9876\u70b9\u672a\u88ab\u8bbf\u95ee for(int i=0;i<vertexNum;i++) visited[i]=0; \/\/2\u3001\u7b2c\u4e00\u4e2a\u9876\u70b9\u5165\u6808 stack<int> st; […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[6],"tags":[],"_links":{"self":[{"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/posts\/177"}],"collection":[{"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/47.103.123.166\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=177"}],"version-history":[{"count":1,"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/posts\/177\/revisions"}],"predecessor-version":[{"id":178,"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/posts\/177\/revisions\/178"}],"wp:attachment":[{"href":"http:\/\/47.103.123.166\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=177"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/47.103.123.166\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=177"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/47.103.123.166\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=177"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}