![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261001021635-6abdc28359edf.jpg\")
<\/h2>\n🔥keyipatience:\u4e2a\u4eba\u4e3b\u9875<\/p>\n
🎬\u4f5c\u8005\u7b80\u4ecb：C\/C++\u540e\u7aef\u5f00\u53d1\u5b66\u4e60\u8005<\/p>\n
🌟\u4e13\u680f\u4f20\u9001\u95e8：\u300ac++\u300b\u300alinux\u300b\u300ac++\u9ad8\u9636\u6570\u636e\u7ed3\u6784\u300b\u300ac++\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u300b<\/p>\n
\u2b50\ufe0fpatience is key in life<\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261001021635-6abdc283d75ed.png\")
<\/h2>\n1.\u56fe G=(V,E)，\u7531\u4e24\u90e8\u5206\u7ec4\u6210<\/span><\/p>\n 2.\u65e0\u5411\u56fe vs \u6709\u5411\u56fe<\/span><\/p>\n 3.\u5b8c\u5168\u56fe<\/span><\/p>\n 4.\u90bb\u63a5\u9876\u70b9<\/span><\/p>\n 5.\u9876\u70b9\u7684\u5ea6<\/span><\/p>\n \u63e1\u624b\u5b9a\u7406：\u56fe\u4e2d\u6240\u6709\u9876\u70b9\u5ea6\u6570\u4e4b\u548c = \u8fb9\u6570 \u00d7 2<\/p>\n 6.\u8def\u5f84 & \u8def\u5f84\u957f\u5ea6<\/span><\/p>\n \u4f8b\u5b50：\u56fe\u91cc\u7684\u4ea4\u901a\u7f51\u7edc\u56fe，\u8fb9\u4e0a\u6570\u5b57\u5c31\u662f\u8def\u7a0b；\u65bd\u5de5\u8fdb\u5ea6\u56fe，\u6570\u5b57\u4ee3\u8868\u5de5\u671f\u3002<\/p>\n 7.\u7b80\u5355\u8def\u5f84 & \u56de\u8def（\u73af）<\/span><\/p>\n 8.\u5b50\u56fe<\/span><\/p>\n \u539f\u56feG=(V,E)，\u65b0\u56feG1=(V1,E1)\u53ea\u8981\u6ee1\u8db3：V1\u662f\u539f\u56fe\u9876\u70b9\u7684\u5b50\u96c6，E1\u662f\u539f\u56fe\u8fb9\u7684\u5b50\u96c6，G1\u5c31\u662fG\u7684\u5b50\u56fe\u3002<\/p>\n \u53ef\u4ee5\u5c11\u70b9\u3001\u5c11\u8fb9；\u4f46\u4e0d\u80fd\u51fa\u73b0\u539f\u56fe\u6ca1\u6709\u7684\u70b9\u6216\u8005\u8fb9\u3002<\/p>\n 9.\u8fde\u901a\u56fe（\u65e0\u5411\u56fe） & \u5f3a\u8fde\u901a\u56fe（\u6709\u5411\u56fe）<\/span><\/p>\n 10.\u751f\u6210\u6811<\/span><\/p>\n 2\u5c31\u662f1\u7684\u751f\u6210\u6811<\/p>\n \u6700\u5c0f\u751f\u6210\u6811 (MST)：\u6240\u6709\u751f\u6210\u6811\u91cc，\u8fb9\u6743\u603b\u548c\u6700\u5c0f\u7684\u90a3\u4e00\u68f5\u3002<\/span><\/p>\n \u6838\u5fc3\u601d\u60f3：\u7528\u4e8c\u7ef4\u6570\u7ec4（\u77e9\u9635）\u5b58\u9876\u70b9\u4e4b\u95f4\u6709\u6ca1\u6709\u8fb9 \u77e9\u9635 edge[i][j] \u4ee3\u8868\u9876\u70b9 i \u5230\u9876\u70b9 j \u7684\u8fde\u63a5\u60c5\u51b5\u3002<\/p>\n 1.\u65e0\u5411\u56fe G1<\/span><\/p>\n （1）\u65e0\u5411\u56fe\u90bb\u63a5\u77e9\u9635\u4e00\u5b9a\u5bf9\u79f0：edge[i][j] = edge[j][i]<\/p>\n （2）edge[i][j]=1：i \u548c j \u4e4b\u95f4\u6709\u8fb9；\u7b49\u4e8e 0：\u6ca1\u6709\u8fb9<\/p>\n 2.\u6709\u5411\u56fe G2<\/span><\/p>\n \u77e9\u9635\u4e0d\u4e00\u5b9a\u5bf9\u79f0，\u8fb9\u6709\u65b9\u5411！ edge[A][B]=1 \u4ee3\u8868 A\u2192B；edge[B][A]=1 \u4ee3\u8868 B\u2192A，\u4e8c\u8005\u76f8\u4e92\u72ec\u7acb\u3002<\/p>\n 3.\u5e26\u6743\u56fe<\/span><\/p>\n 1.\u6a21\u677f\u53c2\u6570<\/span><\/p>\n template<class V,class W,W MAX_W,bool Direction=false><\/p>\n （1）V：\u9876\u70b9\u7684\u6570\u636e\u7c7b\u578b（\u9876\u70b9\u5b58\u4ec0\u4e48，\u6bd4\u5982string\/char）<\/p>\n （2）W：\u8fb9\u7684\u6743\u91cd\u7c7b\u578b（int\u3001double）<\/p>\n （3）MAX_W：\u4ee3\u8868\u4e0d\u5b58\u5728\u8fb9\u7684\u6743\u91cd\u503c（\u65e0\u7a77\u5927）<\/p>\n （4）Direction=false：\u9ed8\u8ba4\u65e0\u5411\u56fe；\u4f20 true \u5c31\u662f\u6709\u5411\u56fe<\/p>\n \u90bb\u63a5\u77e9\u9635\u6838\u5fc3：_matrix[i][j] \u4ee3\u8868\u9876\u70b9 i \u2192 \u9876\u70b9 j \u7684\u8fb9\u6743\u91cd；\u7b49\u4e8e MAX_W \u4ee3\u8868\u6ca1\u6709\u8fd9\u6761\u8fb9<\/p>\n 2.\u79c1\u6709\u6210\u5458<\/span><\/p>\n vector<V>_vertexs; \/\/ \u4fdd\u5b58\u6240\u6709\u9876\u70b9 3.\u6784\u9020\u51fd\u6570<\/span><\/p>\n Graph(const V* vertexs, int n) （1）\u628a\u4f20\u5165\u9876\u70b9\u6570\u7ec4\u653e\u5230_vertexs<\/p>\n （2）\u5faa\u73af\u5efa\u7acb\u9876\u70b9\u540d \u2192 \u6570\u7ec4\u4e0b\u6807map<\/p>\n \u597d\u5904：\u7528\u6237\u4f20\u9876\u70b9（\u6bd4\u5982'a'），\u4e0d\u7528\u81ea\u5df1\u8bb0\u6570\u5b57\u4e0b\u6807，\u7c7b\u5185\u90e8\u81ea\u52a8\u8f6c\u6210\u77e9\u9635\u7d22\u5f15<\/p>\n （3）\u521b\u5efan*n\u7684\u4e8c\u7ef4\u77e9\u9635，\u5168\u90e8\u521d\u59cb\u5316\u4e3aMAX_W（\u9ed8\u8ba4\u65e0\u8fb9）<\/p>\n 4.GetVertexIndex<\/span><\/p>\n int GetVertexIndex(const V& v) \u8f93\u5165\u9876\u70b9，\u8fd4\u56de\u5b83\u5728\u77e9\u9635\u91cc\u7684\u4e0b\u6807；\u627e\u4e0d\u5230\u8fd4\u56de – 1\u3002<\/p>\n 4._AddEdge<\/span><\/p>\n void _AddEdge(int srci, int dsti,const W&w) （1）srci\u8d77\u70b9\u4e0b\u6807，dsti\u7ec8\u70b9\u4e0b\u6807<\/p>\n （2）\u6709\u5411\u56fe：\u53ea\u8bbe\u7f6ematrix[srci][dsti]=w，\u5355\u5411\u8fb9<\/p>\n （3）\u65e0\u5411\u56fe（\u9ed8\u8ba4）：\u540c\u65f6\u8bbe\u7f6ematrix[dsti][srci]=w，\u53cc\u5411\u8fb9<\/p>\n 5.AddEdge<\/span><\/p>\n void AddEdge(const V& src, const V& dst, const W& w) \u5bf9\u5916\u4f7f\u7528：\u76f4\u63a5\u4f20\u9876\u70b9\u540d\u5b57，\u4e0d\u7528\u7ba1\u4e0b\u6807，\u5185\u90e8\u81ea\u52a8\u8f6c\u4e0b\u6807\u8c03\u7528_AddEdge\u3002 \u793a\u4f8b：g.AddEdge('A','B',5)<\/p>\n 6<\/span>.Print<\/span><\/p>\n void Print() cout << " ";\/\/\u7a7a\u4e8c\u683c \/\/ 2. \u6253\u5370\u90bb\u63a5\u77e9\u9635 \/\/ 3. \u6253\u5370\u6240\u6709\u7684\u8fb9，\u6ce8\u610f:\u6253\u5370\u8fb9\u7684\u5faa\u73af i<j：\u5982\u679c\u662f\u6709\u5411\u56fe\u65f6，\u6709\u5411\u8fb9\u4f1a\u6f0f\u6389，\u4e0d\u80fd\u76f4\u63a5\u590d\u7528,\u9700\u8981\u53bb\u6389 template<class V,class W,W MAX_W,bool Direction=false> cout << " ";\/\/\u7a7a\u4e8c\u683c \/\/ 2. \u6253\u5370\u90bb\u63a5\u77e9\u9635 \/\/ 3. \u6253\u5370\u6240\u6709\u7684\u8fb9，\u6ce8\u610f:\u6253\u5370\u8fb9\u7684\u5faa\u73af i<j：\u5982\u679c\u662f\u6709\u5411\u56fe\u65f6，\u6709\u5411\u8fb9\u4f1a\u6f0f\u6389，\u4e0d\u80fd\u76f4\u63a5\u590d\u7528,\u9700\u8981\u53bb\u6389 private: \u6d4b\u8bd5\u7528\u4f8b：<\/span><\/p>\n void TestGraph() \u7ed3\u679c：<\/span> \u90bb\u63a5\u8868：\u4f7f\u7528\u6570\u7ec4\u8868\u793a\u9876\u70b9\u7684\u96c6\u5408，\u4f7f\u7528\u94fe\u8868\u8868\u793a\u8fb9\u7684\u5173\u7cfb\u3002<\/p>\n 1. \u65e0\u5411\u56fe\u90bb\u63a5\u8868\u5b58\u50a8<\/span><\/p>\n 2.\u6709\u5411\u56fe\u90bb\u63a5\u8868\u5b58\u50a8<\/span><\/p>\n \u5b9e\u9645\u6211\u4eec\u5b9e\u73b0\u7684\u65f6\u5019\u4e0d\u7528\u5206\u522b\u5b9e\u73b0\u5165\u8fb9\u8868\u548c\u51fa\u8fb9\u88682\u4e2a\u8868，\u666e\u901a\u90bb\u63a5\u8868\u53ea\u5b58\u3010\u51fa\u8fb9\u3011，\u4e00\u6761\u5c31\u591f；\u4e0d\u9700\u8981\u989d\u5916\u518d\u5355\u72ec\u5f00\u4e00\u5f20\u8868\u4e13\u95e8\u5b58\u5165\u8fb9\u3002\u5e76\u4e14\u7edd\u5927\u591a\u6570\u7b97\u6cd5（DFS\u3001BFS\u3001Dijkstra\u3001\u62d3\u6251\u6392\u5e8f）\u53ea\u9700\u8981\u904d\u5386\u4e00\u4e2a\u70b9\u6240\u6709\u5f80\u5916\u8d70\u7684\u8fb9<\/span>，\u53ea\u9700\u8981\u51fa\u8fb9\u8868，\u53ea\u7528_linktable\u5c31\u8db3\u591f\u3002<\/p>\n 1.Edge \u8fb9\u7ed3\u6784\u4f53（\u5355\u94fe\u8868\u8282\u70b9）<\/span><\/p>\n template<class W> Edge<W>(const int dsti=-1,const W&w=W()) 2. Graph \u7c7b\u6210\u5458\u53d8\u91cf（private）<\/span><\/p>\n vector<V> _vertexs; \/\/ \u9876\u70b9\u6570\u7ec4 eg：\u00a0\u9876\u70b9：A(0), B(1), C(2) _linktable[0] \u662f\u9876\u70b9 A \u7684\u8fb9\u94fe\u8868\u5934，\u5b58 A \u6240\u6709\u51fa\u53bb\u7684\u8fb9 _linktable[1] \u662f\u9876\u70b9 B \u7684\u8fb9\u94fe\u8868\u5934<\/p>\n 3.\u6784\u9020\u51fd\u6570<\/span><\/p>\n Graph(const V* vertexs, int n) 4.GetVertexIndex<\/span><\/p>\n int GetVertexIndex(const V& v) 5.AddEdge \u6dfb\u52a0\u8fb9（\u6838\u5fc3！\u533a\u5206\u6709\u5411 \/ \u65e0\u5411）<\/span><\/p>\n void AddEdge(const V& src, const V& dst, const W&w) \/\/ \u5934\u63d2\u6cd5：\u65b0\u5efa\u8fb9，\u63d2\u5230srci\u5bf9\u5e94\u7684\u94fe\u8868\u5934\u90e8 \/\/ Direction=false \u65e0\u5411\u56fe：\u53cc\u5411\u90fd\u8981\u52a0\u8fb9 6.Print<\/span><\/p>\n void Print() \/\/ \u7b2c\u4e8c\u90e8\u5206：\u904d\u5386\u90bb\u63a5\u8868 _linktables \/\/ cur\u62ff\u5230\u8fd9\u4e2a\u9876\u70b9\u5bf9\u5e94\u7684\u8fb9\u94fe\u8868\u5934\u6307\u9488 namespace LinkTable Edge<W>(const int dsti = -1,const W& w=W()) } int srci = GetVertexIndex(src); \/\/\u6e90\u9876\u70b9\u4e0b\u6807 \/\/ \u5934\u63d2\u6cd5：\u65b0\u5efa\u8fb9，\u63d2\u5230srci\u5bf9\u5e94\u7684\u94fe\u8868\u5934\u90e8 \/\/ Direction=false \u65e0\u5411\u56fe：\u53cc\u5411\u90fd\u8981\u52a0\u8fb9 \/\/ \u7b2c\u4e8c\u90e8\u5206：\u904d\u5386\u90bb\u63a5\u8868 _linktable \/\/ cur\u62ff\u5230\u8fd9\u4e2a\u9876\u70b9\u5bf9\u5e94\u7684\u8fb9\u94fe\u8868\u5934\u6307\u9488<\/p>\n Edge* cur = _linktable[i];<\/p>\n while (cur) cout << _vertexs[cur->_dsti] <<"[" << cur->_dsti << "]" << cur->_w << "->"; private: \u6d4b\u8bd5\u4f8b\u5b50：<\/span><\/p>\n void TestGraph() \u7ed3\u679c：<\/span><\/p>\n \u5177\u4f53\u8fc7\u7a0b：<\/span><\/p>\n \u4e0b\u6807：0 \u5f20\u4e09，1 \u674e\u56db，2 \u738b\u4e94，3 \u8d75\u516d<\/span><\/p>\n<\/p>\n 0.\u6700\u5f00\u59cb<\/span><\/p>\n _linktable[0]: null 1.AddEdge (\u5f20\u4e09，\u674e\u56db，100)<\/p>\n _linktable[0]: E1(1,100) \u2192 null 2.AddEdge (\u5f20\u4e09，\u738b\u4e94，200)<\/p>\n _linktable[0]: E3(2,200) \u2192 E1(1,100) \u2192 null 3.AddEdge (\u738b\u4e94，\u8d75\u516d，30)<\/p>\n \u6700\u7ec8<\/p>\n _linktable[0]: E3(2,200) \u2192 E1(1,100) \u2192 null \u8fb9\u5c11 = \u7a00\u758f，\u8fb9\u6ee1 = \u7a20\u5bc6\u3002<\/span><\/p>\n eg：<\/span><\/p>\n n=1000 \u4e2a\u9876\u70b9<\/p>\n void BFS(const V& v) void DFS(const V&v) 🔥keyipatience:\u4e2a\u4eba\u4e3b\u9875 🎬\u4f5c\u8005\u7b80\u4ecb：C\/C\u540e\u7aef\u5f00\u53d1\u5b66\u4e60\u8005 🌟\u4e13\u680f\u4f20\u9001\u95e8：\u300ac\u300b\u300alinux\u300b\u300ac\u9ad8\u9636\u6570\u636e\u7ed3\u6784\u300b\u300ac\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u300b \u2b50\ufe0fpatience is key in life \u56fe\n
\n
\n
\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261001021638-6abdc286b8295.png\")
<\/p>\n\n
\n
\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261001021638-6abdc286e7348.png\")
<\/p>\n\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261001021639-6abdc287164cb.png\")
<\/p>\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261001021639-6abdc287269cd.png\")
<\/p>\n\n
\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261001021639-6abdc2875318f.png\")
<\/p>\n\u90bb\u63a5\u77e9\u9635<\/span><\/h3>\n
\u90bb\u63a5\u77e9\u9635\u7c7b\u578b<\/span><\/h4>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261001021639-6abdc2875f8dd.png\")
<\/p>\n\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261001021639-6abdc287ab8e4.png\")
<\/p>\n\u4e00\u6b65\u6b65\u5b9e\u73b0\u90bb\u63a5\u77e9\u9635<\/span><\/h4>\n
\nvector <vector<W>>_matrix; \/\/ \u90bb\u63a5\u77e9\u9635，\u4e8c\u7ef4\u6570\u7ec4
\nmap<V,int>_indexmap; \/\/ \u9876\u70b9 -> \u4e0b\u6807 \u7684\u6620\u5c04：\u6bd4\u5982\u9876\u70b9'A'\u6620\u5c04\u52300\u53f7\u4e0b\u6807<\/p>\n
\n{
\n_vertexs.assign(vertexs, vertexs + n);
\nfor (int i = 0; i < n; i++)
\n{
\n_indexmap[_vertexs[i]] = i;
\n}
\n_matrix.assign(n, vector<W>(n, MAX_W));
\n}<\/p>\n
\n{
\nauto ret = _indexmap.find(v);
\nif (ret == _indexmap.end())return -1;
\nelse return ret->second;
\n}<\/p>\n
\n{
\n_matrix[srci][dsti] = w;
\nif (Direction == false)_matrix[dsti][srci] = w;\/\/\u65e0\u5411\u56fe\u8981\u5efa\u7acb2\u6761
\n} <\/p>\n
\n{
\nint srci = GetVertexIndex(src);
\nint dsti = GetVertexIndex(dst);
\n_AddEdge(srci, dsti, w);
\n}<\/p>\n
\n{
\n\/\/3 \u90e8\u5206\u6253\u5370：
\n\/\/ 1. \u6253\u5370\u9876\u70b9\u548c\u4e0b\u6807\u6620\u5c04\u5173\u7cfb
\nfor (int i = 0; i < _vertexs.size(); i++)
\n{
\ncout << _vertexs[i] << "-" << i << " ";
\n}
\ncout << endl;
\ncout << endl;<\/p>\n
\nfor (int i = 0; i < _vertexs.size(); ++i)
\n{
\ncout << i << " ";
\n}
\ncout << endl;<\/p>\n
\nfor (int i = 0; i < _matrix.size(); ++i) {
\ncout << i << " ";
\nfor (int j = 0; j < _matrix[i].size(); ++j) {
\nif (_matrix[i][j] != MAX_W)
\ncout << _matrix[i][j] << " ";
\nelse
\ncout << "#" << " ";
\n}
\ncout << endl;
\n}
\ncout << endl << endl;<\/p>\n
\nfor (size_t i = 0; i < _matrix.size(); ++i) {
\nfor (size_t j = 0; j < _matrix[i].size(); ++j) {
\nif (i < j && _matrix[i][j] != MAX_W) {
\ncout << _vertexs[i] << "-" << _vertexs[j] << ":" << _matrix[i][j] << endl;
\n}
\n}
\n}
\n} <\/p>\n\u5b8c\u6574\u4ee3\u7801：<\/span><\/h4>\n
\nclass Graph
\n{
\npublic:
\nGraph(){}
\nGraph(const V* vertexs, int n)
\n{
\n_vertexs.assign(vertexs, vertexs + n);\/\/assign(\u521d\u59cb\u8fed\u4ee3\u5668，\u7ed3\u675f\u8fed\u4ee3\u5668）
\nfor (int i = 0; i < n; i++)
\n{
\n_indexmap[_vertexs[i]] = i;\/\/\u5efa\u7acb\u6620\u5c04
\n}
\n_matrix.assign(n, vector<W>(n, MAX_W));
\n}
\nint GetVertexIndex(const V& v)
\n{
\nauto ret = _indexmap.find(v);
\nif (ret == _indexmap.end())return -1;
\nelse return ret->second;
\n}
\nvoid _AddEdge(int srci, int dsti,const W&w)
\n{
\n_matrix[srci][dsti] = w;
\nif (Direction == false)_matrix[dsti][srci] = w;\/\/\u65e0\u5411\u56fe\u8981\u5efa\u7acb2\u6761
\n}
\nvoid AddEdge(const V& src, const V& dst, const W& w)
\n{
\nint srci = GetVertexIndex(src);
\nint dsti = GetVertexIndex(dst);
\n_matrix[srci][dsti] = w;
\nif (Direction == false)_matrix[dsti][srci] = w;\/\/\u65e0\u5411\u56fe\u8981\u5efa\u7acb2\u6761
\n}
\n void Print()
\n{
\n\/\/3\u90e8\u5206\u6253\u5370：
\n\/\/ 1. \u6253\u5370\u9876\u70b9\u548c\u4e0b\u6807\u6620\u5c04\u5173\u7cfb
\nfor (int i = 0; i < _vertexs.size(); i++)
\n{
\ncout << _vertexs[i] << "-" << i << " ";
\n}
\ncout << endl;
\ncout << endl;<\/p>\n
\nfor (int i = 0; i < _vertexs.size(); ++i)
\n{
\ncout << i << " ";
\n}
\ncout << endl;<\/p>\n
\nfor (int i = 0; i < _matrix.size(); ++i) {
\ncout << i << " ";
\nfor (int j = 0; j < _matrix[i].size(); ++j) {
\nif (_matrix[i][j] != MAX_W)
\ncout << _matrix[i][j] << " ";
\nelse
\ncout << "#" << " ";
\n}
\ncout << endl;
\n}
\ncout << endl << endl;<\/p>\n
\nfor (size_t i = 0; i < _matrix.size(); ++i) {
\nfor (size_t j = 0; j < _matrix[i].size(); ++j) {
\nif (i < j && _matrix[i][j] != MAX_W) {
\ncout << _vertexs[i] << "-" << _vertexs[j] << ":" << _matrix[i][j] << endl;
\n}
\n}
\n}
\n}<\/p>\n
\nvector<V>_vertexs;
\nvector <vector<W>>_matrix;
\nmap<V,int>_indexmap;
\n}; <\/p>\n
\n{
\nGraph<char, int, INT_MAX, true> g("0123", 4);
\ng.AddEdge('0', '1', 1);
\ng.AddEdge('0', '3', 4);
\ng.AddEdge('1', '3', 2);
\ng.AddEdge('1', '2', 9);
\ng.AddEdge('2', '3', 8);
\ng.AddEdge('2', '1', 5);
\ng.AddEdge('2', '0', 3);
\ng.AddEdge('3', '2', 6);
\ng.Print();
\n} <\/p>\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261001021639-6abdc287c0d19.png\")
<\/p>\n\u90bb\u63a5\u8868（\u94fe\u8868\u7248\u90bb\u63a5\u8868）<\/span><\/h3>\n
\u90bb\u63a5\u8868\u7c7b\u578b<\/span><\/h4>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261001021639-6abdc287d637e.png\")
<\/p>\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261001021640-6abdc28810bff.png\")
<\/p>\n\u4e00\u6b65\u6b65\u5b9e\u73b0\u90bb\u63a5\u8868：<\/span><\/h4>\n
\nstruct Edge
\n{
\n int _dsti; \/\/ \u76ee\u6807\u9876\u70b9\u7684\u4e0b\u6807（\u91cd\u70b9！\u4e0d\u662f\u9876\u70b9\u503c，\u662f\u5728_vertexs\u91cc\u7684\u7d22\u5f15）
\n W _w; \/\/ \u8fb9\u6743
\n Edge<W>* next; \/\/ \u6307\u5411\u4e0b\u4e00\u6761\u8fb9\u7684\u6307\u9488，\u90bb\u63a5\u8868\u662f\u5355\u94fe\u8868<\/p>\n
\n :_dsti(dsti)
\n ,_w(w)
\n ,next(nullptr)
\n { }
\n};<\/p>\n
\nmap<V, int> _indexmap; \/\/ key:\u9876\u70b9\u503cV，value:\u9876\u70b9\u4e0b\u6807i,\u9876\u70b9\u548c\u4e0b\u6807\u6620\u5c04
\nvector<Edge*> _linktable; \/\/ \u90bb\u63a5\u8868！\u6570\u7ec4，\u6bcf\u4e2a\u5143\u7d20\u662f\u8fb9\u94fe\u8868\u5934\u6307\u9488<\/p>\n
\n{
\n _vertexs.assign(vertexs, vertexs + n);
\n for (int i = 0; i < n; i++)
\n {
\n _indexmap[_vertexs[i]] = i; \/\/ \u9876\u70b9\u503c\u6620\u5c04\u5230\u4e0b\u6807
\n }
\n _linktable.assign(n, nullptr); \/\/ n\u4e2a\u9876\u70b9，n\u6761\u7a7a\u94fe\u8868，\u521d\u59cb\u90fd\u662fnullptr
\n}<\/p>\n
\n{
\n auto ret = _indexmap.find(v);
\n if (ret == _indexmap.end())return -1;
\n else return ret->second;
\n}<\/p>\n
\n{
\n int srci = GetVertexIndex(src); \/\/\u6e90\u9876\u70b9\u4e0b\u6807
\n int dsti = GetVertexIndex(dst); \/\/\u76ee\u6807\u9876\u70b9\u4e0b\u6807<\/p>\n
\n Edge* newedge = new Edge(dsti,w);
\n newedge->next = _linktable[srci];
\n _linktable[srci] = newedge;<\/p>\n
\n if (Direction == false)
\n {
\n Edge* newedge2 = new Edge(srci, w);
\n newedge2->next = _linktable[dsti];
\n _linktable[dsti] = newedge2;
\n }
\n}<\/p>\n
\n{
\n\/\/ \u7b2c\u4e00\u90e8\u5206：\u6253\u5370\u3010\u9876\u70b9\u7f16\u53f7\u548c\u540d\u5b57\u3011
\nfor (size_t i = 0; i < _vertexs.size(); ++i)
\n{
\ncout << "[" << i << "]" << "->" << _vertexs[i] << endl;
\n}
\ncout << endl;<\/p>\n
\nfor (size_t i = 0; i < _linktable.size(); ++i)
\n{
\n\/\/ \u6253\u5370\u8d77\u70b9：\u9876\u70b9\u540d\u5b57[\u4e0b\u6807]
\ncout << _vertexs[i] << "[" << i << "]" << "->";<\/p>\n
\nEdge* cur = _linktable[i];
\nwhile (cur)
\n{
\n\/\/ cur->_dsti：\u76ee\u6807\u9876\u70b9\u4e0b\u6807
\n\/\/ _vertexs[cur->_dsti]：\u76ee\u6807\u9876\u70b9\u540d\u5b57
\ncout << _vertexs[cur->_dsti] << "[" << cur->_dsti << "]" << cur->_w << "->";
\ncur = cur->_next;
\n}
\ncout << "nullptr" << endl;
\n}
\n} <\/p>\n\u5b8c\u6574\u4ee3\u7801：<\/span><\/h4>\n
\n{
\ntemplate<class W>
\nstruct Edge
\n{
\n\/\/\u4e0d\u9700\u8981srci
\nint _dsti;
\nW _w;
\nEdge<W>* next;<\/p>\n
\n:_dsti(dsti)
\n, _w(w)
\n, next(nullptr)
\n{
\n}
\n};
\ntemplate<class V, class W, bool Direction = false>
\nclass Graph
\n{
\npublic:
\ntypedef Edge<W> Edge;
\nGraph(const V* vertexs, int n)
\n{
\n_vertexs.assign(vertexs, vertexs + n);\/\/assign(\u521d\u59cb\u8fed\u4ee3\u5668，\u7ed3\u675f\u8fed\u4ee3\u5668）
\nfor (int i = 0; i < n; i++)
\n{
\n_indexmap[_vertexs[i]] = i;\/\/\u5efa\u7acb\u6620\u5c04
\n}
\n_linktable.assign(n, nullptr);<\/p>\n
\nint GetVertexIndex(const V& v)
\n{
\nauto ret = _indexmap.find(v);
\nif (ret == _indexmap.end())return -1;
\nelse return ret->second;
\n}
\nvoid AddEdge(const V& src, const V& dst, const W& w)
\n{<\/p>\n
\nint dsti = GetVertexIndex(dst); \/\/\u76ee\u6807\u9876\u70b9\u4e0b\u6807<\/p>\n
\nEdge* newedge = new Edge(dsti, w);
\nnewedge->next = _linktable[srci];
\n_linktable[srci] = newedge;<\/p>\n
\nif (Direction == false)
\n{
\nEdge* newedge2 = new Edge(srci, w);
\nnewedge2->next = _linktable[dsti];
\n_linktable[dsti] = newedge2;
\n}
\n}
\nvoid Print()
\n{
\n\/\/ \u7b2c\u4e00\u90e8\u5206：\u6253\u5370\u3010\u9876\u70b9\u7f16\u53f7\u548c\u540d\u5b57\u3011
\nfor (size_t i = 0; i < _vertexs.size(); ++i)
\n{
\ncout << "[" << i << "]" << "->" << _vertexs[i] << endl;
\n}
\ncout << endl;<\/p>\n
\nfor (size_t i = 0; i < _linktable.size(); ++i)
\n{
\n\/\/ \u6253\u5370\u8d77\u70b9：\u9876\u70b9\u540d\u5b57[\u4e0b\u6807]
\ncout << _vertexs[i] << "[" << i << "]" << "->";<\/p>\n
\n{
\n\/\/ cur->_dsti：\u76ee\u6807\u9876\u70b9\u4e0b\u6807
\n\/\/ _vertexs[cur->_dsti]：\u76ee\u6807\u9876\u70b9\u540d\u5b57<\/p>\n
\ncur = cur->next;
\n}
\ncout << "nullptr" << endl;
\n}
\n}<\/p>\n
\nvector<V>_vertexs;
\nmap<V, int>_indexmap;
\nvector<Edge*>_linktable;
\n}; <\/p>\n
\n{
\nstring a[] = { "\u5f20\u4e09", "\u674e\u56db", "\u738b\u4e94", "\u8d75\u516d" };
\nGraph<string, int> g1(a, 4);
\ng1.AddEdge("\u5f20\u4e09", "\u674e\u56db", 100);
\ng1.AddEdge("\u5f20\u4e09", "\u738b\u4e94", 200);
\ng1.AddEdge("\u738b\u4e94", "\u8d75\u516d", 30);
\ng1.Print();
\n} <\/p>\n![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261001021640-6abdc28849287.png\")
<\/p>\n
\n_linktable[1]: null
\n_linktable[2]: null
\n_linktable[3]: null<\/p>\n\n
\n_linktable[1]: E2(0,100) \u2192 null
\n_linktable[2]: null
\n_linktable[3]: null<\/p>\n\n
\n_linktable[1]: E2(0,100) \u2192 null
\n_linktable[2]: E4(0,200) \u2192 null
\n_linktable[3]: null<\/p>\n\n
\n_linktable[1]: E2(0,100) \u2192 null
\n_linktable[2]: E5(3,30) \u2192 E4(0,200) \u2192 null
\n_linktable[3]: E6(2,30) \u2192 null <\/p>\n\u90bb\u63a5\u77e9\u9635\u548c\u90bb\u63a5\u8868\u5bf9\u6bd4：<\/span><\/h3>\n
\n
\n
\n
\u5bf9\u6bd4\u9879\u90bb\u63a5\u77e9\u9635\u90bb\u63a5\u8868<\/tr>\n \n\n \u5b58\u50a8\u7ed3\u6784<\/td>\n \u4e8c\u7ef4\u6570\u7ec4 matrix[i][j]matrix[i][j]\u5b58 i\u2192j \u8fb9\u6743；MAX_W \u4ee3\u8868\u65e0\u8fb9<\/td>\n vector<Edge*>\u94fe\u8868\u6570\u7ec4，\u6bcf\u4e2a\u6570\u7ec4\u5143\u7d20\u5c31\u662f\u4e00\u4e2a\u94fe\u8868<\/td>\n<\/tr>\n \n \u7a7a\u95f4\u590d\u6742\u5ea6<\/td>\n O(n2)\u53ea\u548c\u9876\u70b9\u6570\u6709\u5173，\u548c\u8fb9\u65e0\u5173<\/td>\n O(n+E)\u9876\u70b9 + \u5b9e\u9645\u8fb9，\u8fb9\u8d8a\u5c11\u8d8a\u7701\u7a7a\u95f4<\/td>\n<\/tr>\n \n \u9002\u5408\u56fe<\/td>\n \u7a20\u5bc6\u56fe（\u8fb9\u5f88\u591a）<\/td>\n \u7a00\u758f\u56fe（\u8fb9\u5f88\u5c11）<\/td>\n<\/tr>\n \n \u67e5\u8be2 i,j \u4e24\u70b9\u6709\u6ca1\u6709\u8fb9<\/td>\n \u76f4\u63a5matrix[i][j]，O(1)<\/td>\n \u00a0\u9700\u8981\u904d\u5386 i \u7684\u90bb\u63a5\u94fe\u8868，\u6700\u574fO(n)<\/td>\n<\/tr>\n \n \u904d\u5386\u4e00\u4e2a\u9876\u70b9\u7684\u6240\u6709\u90bb\u8fb9<\/td>\n \u00a0\u8981\u5faa\u73af\u5168\u90e8 n \u4e2a\u70b9，O(n)<\/td>\n \u00a0\u76f4\u63a5\u904d\u5386\u94fe\u8868，\u51fa\u8fb9\u6570\u91cf，\u5f88\u5feb<\/td>\n<\/tr>\n \n \u65b0\u589e\u8fb9<\/td>\n \u00a0O(1)，\u76f4\u63a5\u8d4b\u503c<\/td>\n \u00a0O(1)，\u5c3e\u63d2\u8282\u70b9<\/td>\n<\/tr>\n \n \u5220\u9664\u8fb9<\/td>\n \u00a0O(1)，\u76f4\u63a5\u8d4b\u503c MAX_W<\/td>\n \u00a0\u9700\u8981\u904d\u5386\u94fe\u8868\u627e\u5230\u8be5\u8fb9，\u6162<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n DFS\u548cBFS（\u4ee5\u90bb\u63a5\u77e9\u9635\u5b9e\u73b0）<\/span><\/h3>\n
BFS:<\/span><\/h4>\n
\n{
\ncout << "BFS:";
\nint srci = GetVertexIndex(v);
\nif (srci == -1)
\n{
\ncout << "\u9876\u70b9\u4e0d\u5b58\u5728" << endl;
\nreturn;
\n}
\nvector<bool>vis(_vertexs.size(), false);
\nqueue<int>q;\/\/\u5b58\u4e0b\u6807
\nq.push(srci);
\nvis[srci] = true;
\nwhile (q.size())
\n{
\nint front = q.front();
\nq.pop();
\ncout << _vertexs[front] << " ";
\nfor (int i = 0; i < _vertexs.size(); i++)\/\/\u628a\u548c\u76f8\u90bb\u7684\u5168\u90e8\u627e\u51fa\u6765
\n{
\nif (_matrix[front][i]!=MAX_W && !vis[i])
\n{
\nq.push(i);
\nvis[i] = true;
\n}
\n}
\n}
\ncout << endl;
\n} <\/p>\nDFS：<\/span><\/h4>\n
\n{
\ncout << "DFS:";
\nint srci = GetVertexIndex(v);
\nif (srci == -1)
\n{
\ncout << "\u9876\u70b9\u4e0d\u5b58\u5728" << endl;
\nreturn;
\n}
\nvector<bool>vis(_vertexs.size(),false);
\n_dfs(srci, vis);
\n}
\nvoid _dfs(int srci, vector<bool>& vis)\/\/\u5f15\u7528vis\u76f8\u5f53\u4e8e\u5168\u5c40
\n{
\ncout << _vertexs[srci] << " ";
\nvis[srci] = true;
\nfor (int i = 0; i< _vertexs.size(); i++)
\n{
\nif (_matrix[srci][i] != MAX_W && !vis[i])
\n{
\n_dfs(i, vis);
\n}
\n}
\n} <\/p>\n","protected":false},"excerpt":{"rendered":"
\n\u56fe\u7684\u57fa\u7840\u77e5\u8bc6
\n1.\u56fe G(V,E)，\u7531\u4e24\u90e8\u5206\u7ec4\u6210
\nV（\u9876\u70b9\u96c6）：\u4e00\u5806\u70b9，\u4e0d\u80fd\u4e3a\u7a7aE（\u8fb9\u96c6）<\/p>\n","protected":false},"author":2,"featured_media":111505,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[12694,7290,7291,1984,1813],"topic":[],"class_list":["post-111518","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-server","tag-12694","tag-7290","tag-7291","tag-1984","tag-1813"],"yoast_head":"\n