{"id":301,"date":"2026-03-19T15:17:36","date_gmt":"2026-03-19T07:17:36","guid":{"rendered":"https:\/\/jiangqvweihuan.cn\/?p=301"},"modified":"2026-03-28T16:06:55","modified_gmt":"2026-03-28T08:06:55","slug":"%e5%9b%be%e8%ae%ba%e5%9f%ba%e7%a1%80","status":"publish","type":"post","link":"https:\/\/jiangqvweihuan.cn\/index.php\/2026\/03\/19\/%e5%9b%be%e8%ae%ba%e5%9f%ba%e7%a1%80\/","title":{"rendered":"\u7ed3\u70b9\u5320\u5fc3\u00b7\u56fe\u8bba\u57fa\u7840"},"content":{"rendered":"\n

\u5728ACM\u7b97\u6cd5\u7ade\u8d5b\u4e2d\uff0c\u56fe\u8bba\u95ee\u9898\u5360\u636e\u4e86\u76f8\u5f53\u91cd\u8981\u7684\u5730\u4f4d\u3002\u65e0\u8bba\u662f\u57fa\u7840\u7684\u904d\u5386\u3001\u6700\u77ed\u8def\u3001\u6700\u5c0f\u751f\u6210\u6811\uff0c\u8fd8\u662f\u590d\u6742\u7684\u7f51\u7edc\u6d41\u3001\u8fde\u901a\u5206\u91cf\uff0c\u90fd\u79bb\u4e0d\u5f00\u5bf9\u56fe\u8bba\u77e5\u8bc6\u3002\u672c\u6587\u805a\u7126\u4e8e\u56fe\u8bba\u4e2d\u5e38\u89c1\u672f\u8bed\u7684\u89e3\u91ca\u548c\u56fe\u7684\u51e0\u79cd\u50a8\u5b58\u65b9\u5f0f\u8fdb\u884c\u8be6\u7ec6\u9610\u8ff0\uff0c\u9002\u5408\u5e0c\u671b\u5728\u7b97\u6cd5\u7ade\u8d5b\u56fe\u8bba\u90e8\u5206\u6709\u826f\u597d\u5f00\u59cb\u7684\u8bfb\u8005\u3002<\/p>\n\n\n\n

\u4e00\u3001\u56fe\u7684\u57fa\u672c\u6982\u5ff5<\/h2>\n\n\n\n

1.\u4ec0\u4e48\u662f\u56fe<\/h3>\n\n\n\n

\u56fe<\/strong>\uff08graph\uff09\u662f\u7531\u9876\u70b9\u96c6\u5408\u548c\u9876\u70b9\u4e4b\u95f4\u7684\u5173\u7cfb\uff08\u8fb9\uff09\u7ec4\u6210\u7684\u4e00\u79cd\u6570\u636e\u7ed3\u6784\uff1aG(V, E)\u3002\u5176\u4e2d\u9876\u70b9\u96c6\u5408V={x|x\u5c5e\u4e8e\u67d0\u4e2a\u6570\u636e\u5bf9\u8c61\u96c6}\u662f\u6709\u7a77\u975e\u7a7a\u96c6\u5408\uff1bE = {(x,y)|x,y\u5c5e\u4e8eV}\u6216\u8005E = {<x, y>|x,y\u5c5e\u4e8eV && Path(x, y)}\u662f\u9876\u70b9\u95f4\u5173\u7cfb\u7684\u6709\u7a77\u96c6\u5408\uff0c\u4e5f\u53eb\u505a\u8fb9\u7684\u96c6\u5408\u3002(x, y)\u8868\u793ax\u5230y\u7684\u4e00\u6761\u53cc\u5411\u901a\u8def\uff0c\u5373(x, y)\u662f\u65e0\u65b9\u5411\u7684\uff1bPath(x, y)\u8868\u793a\u4ecex\u5230y\u7684\u4e00\u6761\u5355\u5411\u901a\u8def\uff0c\u5373Path(x, y)\u662f\u6709\u65b9\u5411\u7684\u3002<\/p>\n\n\n\n

\u56fe\u4e2d\u7684\u8282\u70b9\u6210\u4e3a\u9876\u70b9\uff0c\u7b2ci\u4e2a\u9876\u70b9\u8bb0\u4f5cvi\u3002\u4e24\u4e2a\u9876\u70b9vi\u548cvj\u76f8\u5173\u8054\u79f0\u4f5c\u9876\u70b9vi\u548c\u9876\u70b9vj\u4e4b\u95f4\u6709\u4e00\u6761\u8fb9\uff0c\u56fe\u4e2d\u7684\u7b2ck\u6761\u8fb9\u8bb0\u4f5cek\uff0cek = (vi\uff0cvj)\u6216<vi\uff0cvj>\u3002<\/p>\n\n\n\n

2.\u56fe\u7684\u79cd\u7c7b<\/h3>\n\n\n\n

\u56fe\u5206\u4e3a\u6709\u5411\u56fe<\/strong>\u548c\u65e0\u5411\u56fe<\/strong>\u4e24\u79cd\u3002<\/p>\n\n\n\n

\u6709\u5411\u56fe\u4e2d\uff0c\u9876\u70b9\u5bf9<x, y>\u662f\u6709\u5e8f\u7684\uff0c\u9876\u70b9\u5bf9<x\uff0cy>\u79f0\u4e3a\u9876\u70b9x\u5230\u9876\u70b9y\u7684\u4e00\u6761\u8fb9(\u5f27)\uff0c<x, y>\u548c<y, x>\u662f\u4e24\u6761\u4e0d\u540c\u7684\u8fb9\u3002\u65e0\u5411\u56fe\u4e2d\uff0c\u9876\u70b9\u5bf9(x, y)\u662f\u65e0\u5e8f\u7684\uff0c\u9876\u70b9\u5bf9(x,y)\u79f0\u4e3a\u9876\u70b9x\u548c\u9876\u70b9y\u76f8\u5173\u8054\u7684\u4e00\u6761\u8fb9\uff0c\u8fd9\u6761\u8fb9\u6ca1\u6709\u7279\u5b9a\u65b9\u5411\uff0c(x, y)\u548c(y\uff0cx)\u662f\u540c\u4e00\u6761\u8fb9\uff0c\u65e0\u5411\u8fb9(x, y)\u7b49\u4e8e\u6709\u5411\u8fb9<x, y>\u548c<y, x>\u3002<\/p>\n\n\n\n

\u5982\u56fe\u5de6\u4fa7\u662f\u6709\u5411\u56fe\uff0c\u53f3\u4fa7\u662f\u65e0\u5411\u56fe\u3002<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

3.\u5b8c\u5168\u56fe<\/h3>\n\n\n\n

\u5728\u6709n\u4e2a\u9876\u70b9\u7684\u65e0\u5411\u56fe\u4e2d\uff0c\u82e5\u6709n * (n-1)\/2<\/code>\u6761\u8fb9\uff0c\u5373\u4efb\u610f\u4e24\u4e2a\u9876\u70b9\u4e4b\u95f4\u6709\u4e14\u4ec5\u6709\u4e00\u6761\u8fb9\uff0c\u5219\u79f0\u6b64\u56fe\u4e3a\u65e0\u5411\u5b8c\u5168\u56fe\uff0c\u5728n\u4e2a\u9876\u70b9\u7684\u6709\u5411\u56fe\u4e2d\uff0c\u82e5\u6709n * (n-1)<\/code>\u6761\u8fb9\uff0c\u5373\u4efb\u610f\u4e24\u4e2a\u9876\u70b9\u4e4b\u95f4\u6709\u4e14\u4ec5\u6709\u4e24\u6761\u65b9\u5411\u76f8\u53cd\u7684\u8fb9\uff0c\u5219\u79f0\u6b64\u56fe\u4e3a\u6709\u5411\u5b8c\u5168\u56fe\u3002<\/p>\n\n\n\n

\u5982\u56fe\u5de6\u4fa7\u662f\u6709\u5411\u5b8c\u5168\u56fe\uff0c\u53f3\u4fa7\u662f\u65e0\u5411\u5b8c\u5168\u56fe\uff1a<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

4.\u4e34\u63a5\u9876\u70b9<\/h3>\n\n\n\n

\u5728\u65e0\u5411\u56fe<\/strong>\u4e2dG\u4e2d\uff0c\u82e5(u, v)\u662fE(G)\u4e2d\u7684\u4e00\u6761\u8fb9\uff0c\u5219\u79f0u\u548cv\u4e92\u4e3a\u90bb\u63a5\u9876\u70b9<\/strong>\uff0c\u5e76\u79f0\u8fb9(u,v)\u4f9d\u9644\u4e8e\u9876\u70b9u\u548cv\uff1b \u5728\u6709\u5411\u56fe<\/strong>G\u4e2d\uff0c\u82e5<u, v>\u662fE(G)\u4e2d\u7684\u4e00\u6761\u8fb9\uff0c\u5219\u79f0\u9876\u70b9u\u90bb\u63a5\u5230v<\/strong>\uff0c\u9876\u70b9v\u90bb\u63a5\u81ea\u9876\u70b9u\uff0c\u5e76\u79f0\u8fb9<u, v>\u4e0e\u9876\u70b9u\u548c\u9876\u70b9v\u76f8\u5173\u8054\u3002<\/p>\n\n\n\n

5.\u8def\u5f84<\/h3>\n\n\n\n

\u5728\u56feG = (V\uff0c E)\u4e2d\uff0c\u82e5\u4ece\u9876\u70b9vi\u51fa\u53d1\u6709\u4e00\u7ec4\u8fb9\u4f7f\u5176\u53ef\u5230\u8fbe\u9876\u70b9vj\uff0c\u5219\u79f0\u9876\u70b9vi\u5230\u9876\u70b9vj\u7684\u9876\u70b9\u5e8f\u5217\u4e3a\u4ece\u9876\u70b9vi\u5230\u9876\u70b9vj\u7684\u8def\u5f84\u3002<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

\u4e0a\u56fe\u4ece\u9876\u70b90\u5230\u9876\u70b94\u7684\u8def\u5f84\u6709\uff1a
0 2 4
1 1 4
……
\u53ef\u80fd\u6709\u5f88\u591a\u8def\u5f84<\/p>\n\n\n\n

6.\u8def\u5f84\u957f\u5ea6<\/h3>\n\n\n\n

\u5bf9\u4e8e\u4e0d\u5e26\u6743\u7684\u56fe\uff0c\u4e00\u6761\u8def\u5f84\u7684\u8def\u5f84\u957f\u5ea6\u662f\u6307\u8be5\u8def\u5f84\u4e0a\u7684\u8fb9\u7684\u6761\u6570\uff1b\u5bf9\u4e8e\u5e26\u6743\u7684\u56fe\uff0c\u4e00\u6761\u8def\u5f84\u7684\u8def\u5f84\u957f\u5ea6\u662f\u6307\u8be5\u8def\u5f84\u4e0a\u5404\u4e2a\u8fb9\u6743\u503c\u7684\u603b\u548c\u3002<\/p>\n\n\n\n

7.\u7b80\u5355\u8def\u5f84\u548c\u56de\u8def<\/h3>\n\n\n\n

\u82e5\u8def\u5f84\u4e0a\u5404\u9876\u70b9v1\uff0cv2\uff0cv3\uff0c\u2026\uff0cvm\u5747\u4e0d\u91cd\u590d\uff0c\u5219\u79f0\u8fd9\u6837\u7684\u8def\u5f84\u4e3a\u7b80\u5355\u8def\u5f84\u3002 \u82e5\u8def\u5f84\u4e0a\u7b2c\u4e00\u4e2a\u9876\u70b9v1\u548c\u6700\u540e\u4e00\u4e2a\u9876\u70b9vm\u91cd\u5408\uff0c\u5219\u79f0\u8fd9\u6837\u7684\u8def\u5f84\u4e3a\u56de\u8def\u6216\u73af\u3002<\/p>\n\n\n\n

8.\u5b50\u56fe<\/h3>\n\n\n\n

\u8bbe\u56feG = {V, E}\u548c\u56feG1 = {V1\uff0cE1}\uff0c\u82e5V1\u5c5e\u4e8eV\u4e14E1\u5c5e\u4e8eE\uff0c\u5219\u79f0G1\u662fG\u7684\u5b50\u56fe\uff08\u5373G1\u7684\u9876\u70b9\u548c\u8fb9\u90fd\u662f\u539f\u56fe\u7684\u4e00\u90e8\u5206\uff09\u3002<\/p>\n\n\n\n

9.\u8fde\u901a\u56fe<\/h3>\n\n\n\n

\u5728\u65e0\u5411\u56fe\u4e2d<\/strong>\uff0c\u82e5\u4ece\u9876\u70b9v1\u5230\u9876\u70b9v2\u6709\u8def\u5f84\uff0c\u5219\u79f0\u9876\u70b9v1\u4e0e\u9876\u70b9v2\u662f\u8fde\u901a\u7684\uff1b \u5982\u679c\u56fe\u4e2d\u4efb\u610f\u4e00\u5bf9\u9876\u70b9\u90fd\u662f\u8fde\u901a\u7684\uff0c\u5219\u79f0\u6b64\u56fe\u4e3a\u8fde\u901a\u56fe<\/strong>\u3002<\/p>\n\n\n\n

10.\u5f3a\u8fde\u901a\u56fe\u548c\u5f31\u8fde\u901a\u56fe<\/h3>\n\n\n\n

\u5728\u6709\u5411\u56fe\u4e2d<\/strong>\uff0c\u82e5\u6bcf\u4e00\u5bf9\u9876\u70b9vi\u548cvj\u4e4b\u95f4\u90fd\u5b58\u5728\u4e00\u6761\u4ecevi\u5230vj\u7684\u8def\u5f84\uff0c\u4e5f\u5b58\u5728\u4e00\u6761\u4ecevj\u5230vi\u7684\u8def\u5f84\uff0c\u5219\u79f0\u6b64\u56fe\u662f\u5f3a\u8fde\u901a\u56fe<\/strong>\uff0c\u82e5\u6bcf\u4e00\u5bf9\u9876\u70b9vi\u548cvj\u4e4b\u95f4\u90fd\u5ffd\u7565\u65b9\u5411\u540e\u8fde\u901a\u5219\u79f0\u6b64\u56fe\u662f\u5f31\u8fde\u901a\u56fe<\/strong>\u3002<\/p>\n\n\n\n

11.\u751f\u6210\u6811<\/h3>\n\n\n\n

\u65e0\u5411\u56fe\u4e2d<\/strong>\uff0c\u4e00\u4e2a\u8fde\u901a\u56fe\u7684\u6700\u5c0f\u8fde\u901a\u5b50\u56fe\u79f0\u4f5c\u8be5\u56fe\u7684\u751f\u6210\u6811\u3002
\u6709n\u4e2a\u9876\u70b9\u7684\u8fde\u901a\u56fe\u7684\u751f\u6210\u6811\u6709n\u4e2a\u9876\u70b9\u548cn-1\u6761\u8fb9\u3002
\u5982\u4e0b\u56fe\u6240\u793a\uff1a<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

\u53f3\u4fa7\u4e24\u56fe\u5c31\u662f\u5de6\u4fa7\u65e0\u5411\u56fe\u7684\u751f\u6210\u6811\u3002<\/p>\n\n\n\n

12.\u9876\u70b9\u7684\u5ea6<\/h3>\n\n\n\n

\u5bf9\u4e8e\u65e0\u5411\u56fe\uff0c\u9876\u70b9\u7684\u5ea6\u4e3a\u4f9d\u9644\u4e8e\u8be5\u9876\u70b9\u8fb9\u7684\u6761\u6570\uff0c\u7528TD(v)\u6765\u8868\u793a\uff0c\u800c\u5bf9\u4e8e\u6709\u5411\u56fe\uff0c\u9876\u70b9\u7684\u5ea6\u53c8\u5206\u4e3a\u5165\u5ea6\u548c\u51fa\u5ea6\uff0c\u5165\u5ea6\u662f\u6307\u4ee5\u8be5\u9876\u70b9\u4e3a\u7ec8\u70b9\u7684\u8fb9\u7684\u6761\u6570\uff0c\u8868\u793a\u4e3aID(v)\uff1b\u800c\u51fa\u5ea6\u6307\u7684\u662f\u4ee5\u8be5\u9876\u70b9\u4e3a\u8d77\u70b9\u7684\u8fb9\u7684\u6761\u6570\uff0c\u8868\u793a\u4e3aOD(v)\uff0c\u6709\u5411\u56fe\u7684\u9876\u70b9\u7684\u5ea6\u7684\u5927\u5c0f\u5c31\u662f\u8be5\u9876\u70b9\u7684\u5165\u5ea6\u548c\u51fa\u5ea6\u4e4b\u548c\u3002<\/p>\n\n\n\n

13.\u5e26\u6743\u56fe<\/h3>\n\n\n\n

\u5e26\u6743\u56fe\u5373\u56fe\u4e0a\u4e24\u4e2a\u8fde\u901a\u7684\u9876\u70b9\u7684\u8fb9\u4e0a\u6709\u5bf9\u5e94\u6743\u503c\u7684\u56fe\uff0c\u6743\u503c\u53ef\u4ee5\u662f\u957f\u5ea6\u4e5f\u53ef\u4ee5\u662f\u4efb\u4f55\u76f8\u5173\u7684\u5355\u4f4d\u3002<\/p>\n\n\n\n

\u4e8c\u3001\u56fe\u7684\u50a8\u5b58<\/h2>\n\n\n\n

1.\u90bb\u63a5\u77e9\u9635<\/h3>\n\n\n\n

\u90bb\u63a5\u77e9\u9635\uff08Adjacency Matrix\uff09\u9002\u7528\u4e8e\u7a20\u5bc6\u56fe\uff08\u5982n\u22641000\uff09\u3001\u9700\u8981\u5feb\u901f\u67e5\u8be2\u4e24\u70b9\u95f4\u662f\u5426\u6709\u8fb9\u3002\u7a7a\u95f4\u590d\u6742\u5ea6\u662fO(n2<\/sup>)\uff0c\u67e5\u8be2\u4e24\u9876\u70b9\u662f\u5426\u6709\u8fb9\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(1)\uff0c\u7531\u4e8e\u5360\u7528\u7a7a\u95f4\u592a\u5927\uff0c\u4e0d\u9002\u7528\u4e8e\u5927\u89c4\u6a21\u56fe\u3002<\/p>\n\n\n\n

\u5177\u4f53\u6838\u5fc3\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\u56fe\u6240\u793a\uff1a<\/p>\n\n\n\n

#include <iostream>\n#include <cstring>\nusing namespace std;\n\nconst int N = 1005; \/\/ \u6700\u5927\u9876\u70b9\u6570\nint g[N][N];        \/\/ \u90bb\u63a5\u77e9\u9635\uff0cg[u][v] = \u6743\u503c\uff08\u65e0\u6743\u56fe\u53ef\u7528 0\/1\uff09\nint n, m;           \/\/ \u9876\u70b9\u6570\uff0c\u8fb9\u6570\n\nvoid add(int u, int v, int w) { \/\/ \u6dfb\u52a0\u4e00\u6761\u6709\u5411\u8fb9 u->v\uff0c\u6743\u503c\u4e3a w\n    g[u][v] = w;                 \/\/ \u65e0\u5411\u56fe\u9700\u52a0 g[v][u] = w\n}\n\nint main() {\n    memset(g, 0, sizeof g);      \/\/ \u521d\u59cb\u5316\u4e3a 0\uff08\u8868\u793a\u65e0\u8fb9\uff09\n    cin >> n >> m;\n    for (int i = 0; i < m; i++) {\n        int u, v, w;\n        cin >> u >> v >> w;\n        add(u, v, w);\n        \/\/ \u5982\u679c\u662f\u65e0\u5411\u56fe\uff0c\u53d6\u6d88\u4e0b\u9762\u6ce8\u91ca\uff1a\n        \/\/ add(v, u, w);\n    }\n    \/\/ \u904d\u5386\u9876\u70b9 u \u7684\u6240\u6709\u90bb\u63a5\u70b9\n    int u = 1; \/\/ \u793a\u4f8b\u9876\u70b9\n    for (int v = 1; v <= n; v++) {\n        if (g[u][v] != 0) {\n            cout << \"\u8fb9 \" << u << \" -> \" << v << \" \u6743\u503c: \" << g[u][v] << endl;\n        }\n    }\n    return 0;\n}<\/code><\/pre>\n\n\n\n
2.\u90bb\u63a5\u8868<\/h3>\n\n\n\n
\u90bb\u63a5\u8868\uff08Adjacency List\uff09\u9002\u7528\u4e8e\u5927\u591a\u6570\u7a00\u758f\u56fe\uff0c\u52a8\u6001\u52a0\u8fb9\u65b9\u4fbf\uff0c\u4ee3\u7801\u7b80\u6d01\u3002\u5bf9\u4e8e\u6709\u6743\u56fe\u91c7\u7528vector<pair<int,int>> g[N]\uff0c\u65e0\u6743\u56fevector<int> g[N]\u3002<\/p>\n\n\n\n
\u65e0\u8fb9\u6743\u7248\uff1a<\/p>\n\n\n\n
#include <iostream>\n#include <vector>\nusing namespace std;\n\nconst int N = 100005;           \/\/ \u6700\u5927\u9876\u70b9\u6570\nvector<int> g[N];               \/\/ g[u] \u5b58\u50a8 u \u7684\u6240\u6709\u90bb\u63a5\u70b9\u7f16\u53f7\nint n, m;\n\nvoid add(int u, int v) {        \/\/ \u6dfb\u52a0\u6709\u5411\u8fb9 u->v\n    g[u].push_back(v);\n    \/\/ \u65e0\u5411\u56fe\u52a0 g[v].push_back(u);\n}\n\nint main() {\n    cin >> n >> m;\n    for (int i = 0; i < m; i++) {\n        int u, v;\n        cin >> u >> v;\n        add(u, v);\n    }\n    \/\/ \u904d\u5386\u9876\u70b9 u \u7684\u90bb\u63a5\u70b9\n    int u = 1;\n    for (int v : g[u]) {\n        cout << \"\u90bb\u63a5\u70b9: \" << v << endl;\n    }\n    return 0;\n}<\/code><\/pre>\n\n\n\n
\u6709\u8fb9\u6743\u7248\uff1a<\/p>\n\n\n\n
#include <iostream>\n#include <vector>\nusing namespace std;\n\nconst int N = 100005;\nvector<pair<int, int>> g[N];    \/\/ pair<\u90bb\u63a5\u70b9, \u6743\u503c>\nint n, m;\n\nvoid add(int u, int v, int w) {\n    g[u].emplace_back(v, w);    \/\/ \u7528 emplace_back \u907f\u514d\u62f7\u8d1d\n    \/\/ \u65e0\u5411\u56fe\u52a0 g[v].emplace_back(u, w);\n}\n\nint main() {\n    cin >> n >> m;\n    for (int i = 0; i < m; i++) {\n        int u, v, w;\n        cin >> u >> v >> w;\n        add(u, v, w);\n    }\n    int u = 1;\n    for (auto [v, w] : g[u]) {  \/\/ C++17 \u7ed3\u6784\u5316\u7ed1\u5b9a\n        cout << \"\u8fb9 \" << u << \" -> \" << v << \" \u6743\u503c: \" << w << endl;\n    }\n    return 0;\n}<\/code><\/pre>\n\n\n\n
3.\u8fb9\u96c6\u6570\u7ec4<\/h3>\n\n\n\n
\u8fb9\u96c6\u6570\u7ec4\u76f4\u63a5\u50a8\u5b58\u8fb9\u7684\u6240\u6709\u8fb9\u7684\u4fe1\u606f\uff0c\u9002\u7528\u4e8e\u9700\u8981\u6392\u5e8f\u8fb9\u7684\u7b97\u6cd5\uff08\u5982 Kruskal\u6700\u5c0f\u751f\u6210\u6811\uff09\u3002<\/p>\n\n\n\n
\u5b9e\u73b0\u4ee3\u7801\uff1a<\/p>\n\n\n\n
#include <iostream>\n#include <algorithm>\n#include <vector>\nusing namespace std;\n\nstruct Edge {\n    int u, v, w;\n    \/\/ \u53ef\u5b9a\u4e49\u6bd4\u8f83\u51fd\u6570\uff0c\u4fbf\u4e8e\u6392\u5e8f\n    bool operator<(const Edge& other) const {\n        return w < other.w; \/\/ \u6309\u6743\u503c\u5347\u5e8f\n    }\n};\n\nvector<Edge> edges; \/\/ \u8fb9\u96c6\u6570\u7ec4\nint n, m;\n\nvoid add(int u, int v, int w) {\n    edges.push_back({u, v, w});\n}\n\nint main() {\n    cin >> n >> m;\n    for (int i = 0; i < m; i++) {\n        int u, v, w;\n        cin >> u >> v >> w;\n        add(u, v, w);\n    }\n    \/\/ \u4f8b\u5982\uff1a\u6309\u6743\u503c\u6392\u5e8f\n    sort(edges.begin(), edges.end());\n    \/\/ \u904d\u5386\u6240\u6709\u8fb9\n    for (auto& e : edges) {\n        cout << e.u << \" -> \" << e.v << \" \u6743\u503c: \" << e.w << endl;\n    }\n    return 0;\n}<\/code><\/pre>\n\n\n\n
4.\u94fe\u5f0f\u524d\u5411\u661f<\/h3>\n\n\n\n
\u94fe\u5f0f\u524d\u5411\u661f\uff08Linked\u00a0Forward\u00a0Star\uff09\u9002\u7528\u4e8e\u8d85\u5927\u89c4\u6a21\u56fe\uff08\u5982n=10\u2076\uff0cm=10\u2077\uff09\uff0c\u8ffd\u6c42\u6781\u81f4\u6548\u7387\uff0c\u9759\u6001\u56fe\u6784\u5efa\u540e\u4e0d\u518d\u4fee\u6539\u3002\u7ade\u8d5b\u4e2d\u7684\u56fe\u7684\u5b58\u50a8\u7ecf\u5e38\u9700\u8981\u91c7\u7528\u94fe\u5f0f\u524d\u5411\u661f\u6765\u5b9e\u73b0\u9ad8\u6548\u7387\u5b58\u50a8\uff0c\u9700\u8981\u719f\u6089\u638c\u63e1\u3002<\/p>\n\n\n\n
\u5b9e\u73b0\u4ee3\u7801\uff1a<\/p>\n\n\n\n
#include <iostream>\nusing namespace std;\n\nconst int N = 100005;   \/\/ \u6700\u5927\u9876\u70b9\u6570\nconst int M = 200005;   \/\/ \u6700\u5927\u8fb9\u6570\uff08\u65e0\u5411\u56fe\u9700\u53cc\u500d\uff09\n\nstruct Edge {\n    int to, w, nxt;     \/\/ \u7ec8\u70b9\uff0c\u6743\u503c\uff0c\u4e0b\u4e00\u6761\u8fb9\u5728\u6570\u7ec4\u4e2d\u7684\u4e0b\u6807\n} e[M];\nint head[N], tot;       \/\/ head[u] \u5b58\u50a8 u \u7684\u7b2c\u4e00\u6761\u8fb9\u7f16\u53f7\uff0ctot \u4e3a\u8fb9\u8ba1\u6570\u5668\n\nvoid init() {           \/\/ \u521d\u59cb\u5316\uff08\u5982\u679c\u6709\u591a\u7ec4\u6570\u636e\u9700\u8981\u6e05\u7a7a\uff09\n    tot = 0;\n    for (int i = 1; i < N; i++) head[i] = 0; \/\/ 0 \u8868\u793a\u7a7a\uff0c\u4e5f\u53ef\u7528 -1\n}\n\nvoid add(int u, int v, int w) {\n    e[++tot] = {v, w, head[u]}; \/\/ \u5934\u63d2\u6cd5\n    head[u] = tot;\n}\n\nint main() {\n    init();\n    int n, m;\n    cin >> n >> m;\n    for (int i = 0; i < m; i++) {\n        int u, v, w;\n        cin >> u >> v >> w;\n        add(u, v, w);\n        \/\/ \u65e0\u5411\u56fe\u52a0 add(v, u, w);\n    }\n    \/\/ \u904d\u5386\u9876\u70b9 u \u7684\u6240\u6709\u90bb\u63a5\u70b9\n    int u = 1;\n    for (int i = head[u]; i; i = e[i].nxt) {\n        int v = e[i].to, w = e[i].w;\n        cout << \"\u8fb9 \" << u << \" -> \" << v << \" \u6743\u503c: \" << w << endl;\n    }\n    return 0;\n}<\/code><\/pre>\n\n\n\n
\u5bf9\u4e8e\u4ee5\u4e0a\u4ee3\u7801\u7684\u7406\u89e3\u8fd8\u8bf7\u8bfb\u8005\u81ea\u884c\u67e5\u9605\u8d44\u6599\u89c6\u9891\u53c2\u609f\uff0c\u8fd9\u91cc\u4e0d\u505a\u8fc7\u591a\u89e3\u91ca\u3002<\/p>\n\n\n\n
\u4e09\u3001\u7ecf\u5178\u4f8b\u9898<\/h2>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
\u5728ACM\u7b97\u6cd5\u7ade\u8d5b\u4e2d\uff0c\u56fe\u8bba\u95ee\u9898\u5360\u636e\u4e86\u76f8\u5f53\u91cd\u8981\u7684\u5730\u4f4d\u3002\u65e0\u8bba\u662f\u57fa\u7840\u7684\u904d\u5386\u3001\u6700\u77ed\u8def\u3001\u6700\u5c0f\u751f\u6210\u6811\uff0c\u8fd8\u662f\u590d\u6742\u7684\u7f51\u7edc\u6d41\u3001\u8fde\u901a […]<\/p>\n","protected":false},"author":1,"featured_media":334,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[18,1,15,12],"tags":[],"class_list":["post-301","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-graph-theory","category-article","category-algorithm-template","category-programming-algorithm-road"],"_links":{"self":[{"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/posts\/301","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/comments?post=301"}],"version-history":[{"count":7,"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/posts\/301\/revisions"}],"predecessor-version":[{"id":347,"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/posts\/301\/revisions\/347"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/media\/334"}],"wp:attachment":[{"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/media?parent=301"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/categories?post=301"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jiangqvweihuan.cn\/index.php\/wp-json\/wp\/v2\/tags?post=301"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}