{"id":730,"date":"2021-11-12T16:33:35","date_gmt":"2021-11-12T08:33:35","guid":{"rendered":"https:\/\/swordofmorning.com\/?p=730"},"modified":"2025-10-09T13:55:35","modified_gmt":"2025-10-09T05:55:35","slug":"pgexam-data-structure-07","status":"publish","type":"post","link":"https:\/\/swordofmorning.com\/index.php\/2021\/11\/12\/pgexam-data-structure-07\/","title":{"rendered":"\u8003\u7814\u6570\u636e\u7ed3\u6784 07 \u56fe"},"content":{"rendered":"
\n
<\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/defs>\u56fe<\/text><\/g><\/use><\/use><\/use><\/use><\/svg><\/use><\/svg><\/g>\u5b9a<\/text><\/g>\u4e49<\/text><\/g><\/g><\/g><\/g>\u5b58<\/text><\/g>\u50a8<\/text><\/g>\u7ed3<\/text><\/g>\u6784<\/text><\/g><\/use><\/g>\u76f8<\/text><\/g>\u90bb<\/text><\/g>\u77e9<\/text><\/g>\u9635<\/text><\/g>\u3001<\/text><\/g>\u90bb<\/text><\/g>\u63a5<\/text><\/g>\u8868<\/text><\/g>\u6cd5<\/text><\/g><\/g><\/g><\/g>\u90bb<\/text><\/g>\u63a5<\/text><\/g>\u591a<\/text><\/g>\u91cd<\/text><\/g>\u8868<\/text><\/g>\u3001<\/text><\/g>\u5341<\/text><\/g>\u5b57<\/text><\/g>\u94fe<\/text><\/g>\u8868<\/text><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g>\u904d<\/text><\/g>\u5386<\/text><\/g><\/use><\/g>\u5e7f<\/text><\/g>\u5ea6<\/text><\/g>\u4f18<\/text><\/g>\u5148<\/text><\/g>\u904d<\/text><\/g>\u5386<\/text><\/g><\/g><\/g><\/g>\u5e7f<\/text><\/g>\u5ea6<\/text><\/g>\u4f18<\/text><\/g>\u5148<\/text><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g>\u76f8<\/text><\/g>\u5173<\/text><\/g>\u5e94<\/text><\/g>\u7528<\/text><\/g><\/use><\/use><\/use><\/use><\/svg><\/use><\/svg><\/g>\u6700<\/text><\/g>\u5c0f<\/text><\/g>\u751f<\/text><\/g>\u6210<\/text><\/g>\u6811<\/text><\/g>\uff1a<\/text><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g>\u7b97<\/text><\/g>\u6cd5<\/text><\/g>\u3001<\/text><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g>\u7b97<\/text><\/g>\u6cd5<\/text><\/g><\/g><\/g><\/g>\u6700<\/text><\/g>\u77ed<\/text><\/g>\u8def<\/text><\/g>\u5f84<\/text><\/g>\uff1a<\/text><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g>\u7b97<\/text><\/g>\u6cd5<\/text><\/g>\u3001<\/text><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g>\u7b97<\/text><\/g>\u6cd5<\/text><\/g><\/g><\/g><\/g>\u62d3<\/text><\/g>\u6251<\/text><\/g>\u6392<\/text><\/g>\u5e8f<\/text><\/g>\uff1a<\/text><\/g><\/use><\/g><\/use><\/g><\/use><\/g>\u7f51<\/text><\/g><\/g><\/g><\/g>\u5173<\/text><\/g>\u952e<\/text><\/g>\u8def<\/text><\/g>\u5f84<\/text><\/g>\uff1a<\/text><\/g><\/use><\/g><\/use><\/g><\/use><\/g>\u7f51<\/text><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/svg><\/mjx-container><\/div>\n<\/div>\n

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

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

1.1 \u56fe\u7684\u5b9a\u4e49<\/h3>\n

  \u56feG\u7531\u9876\u70b9\u96c6V\u548c\u8fb9\u96c6E\u7ec4\u6210\uff0c\u8bb0\u4e3aG = (V, E)\uff0c\u5176\u4e2dV(G)\u8868\u793a\u56feG\u4e2d\u9876\u70b9\u7684\u6709\u9650\u975e\u7a7a\u96c6\uff1bE(G)\u8868\u793a\u56feG\u4e2d\u9876\u70b9\u4e4b\u95f4\u7684\u5173\u7cfb(\u8fb9\u96c6\u5408)\u3002\u82e5V={v1<\/sub>, v2<\/sub>...vn<\/sub>}\uff0c\u5219\u7528|V|\u8868\u793a\u56feG\u4e2d\u9876\u70b9\u7684\u4e2a\u6570\uff0cE={(u, v)| u\u2208V, v \u2208 V}\uff0c\u7528|E|\u8868\u793a\u56feG\u4e2d\u7684\u8fb9\u6570\u3002<\/p>\n

1.1.1 \u6709\u5411\u56fe<\/h4>\n

  \u4e0d\u591a\u89e3\u91ca\uff0c\u6709\u65b9\u5411\u6307\u5411\u7684\u56fe\u3002<\/p>\n

1.1.2 \u65e0\u5411\u56fe<\/h4>\n

  \u540c\u4e0a\u3002<\/p>\n

1.1.3 \u7b80\u5355\u56fe\u3001\u591a\u91cd\u56fe<\/h4>\n

  \u5982\u679c\u4e00\u4e2a\u56fe\u6ee1\u8db3\uff1a<\/p>\n

    \n
  1. \u4e0d\u5b58\u5728\u91cd\u590d\u7684\u8fb9\uff1b<\/li>\n
  2. \u4e0d\u5b58\u5728\u9876\u70b9\u5230\u81ea\u8eab\u7684\u8fb9\u3002<\/li>\n<\/ol>\n

    \u90a3\u4e48\u8be5\u56fe\u5c31\u79f0\u4e3a\u7b80\u5355\u56fe\u3002\u82e5\u56feG\u4e2d\u4e24\u4e2a\u9876\u70b9\u4e4b\u95f4\u7684\u8fb9\u6570\u5927\u4e8e1\u6761\uff0c\u53c8\u5141\u8bb8\u9876\u70b9\u901a\u8fc7\u4e00\u6761\u8fb9\u548c\u81ea\u8eab\u76f8\u8fde\uff0c\u5219\u56feG\u79f0\u4e3a\u591a\u91cd\u56fe\u3002<\/p>\n

    1.1.4 \u5b8c\u5168\u56fe<\/h4>\n

      \u5bf9\u4e8e\u65e0\u5411\u56fe\uff0c\u4efb\u610f\u4e24\u4e2a\u9876\u70b9\u4e4b\u95f4\u90fd\u5b58\u5728\u8fb9\u3002\u5bf9\u4e8e\u6709\u5411\u56fe\uff0c\u8868\u8ff0\u5219\u662f\uff1a\u603b\u80fd\u4ece\u4e00\u4e2a\u9876\u70b9\u5230\u8fbe\u53e6\u4e00\u4e2a\u9876\u70b9\u3002<\/p>\n

    1.1.5 \u5b50\u56fe<\/h4>\n

      \u6709\u4e24\u4e2a\u56feG = (V, E)\u548cG1 = (V1, E1)\uff0c\u82e5V1\u662fV\u7684\u5b50\u96c6\uff0c\u4e14E1\u662fE\u7684\u5b50\u96c6\uff0c\u5219\u79f0\u56feG1\u662f\u56feG\u7684\u5b50\u56fe\u3002<\/p>\n

    1.1.6 \u901a\u9053\u3001\u8fde\u901a\u56fe\u548c\u8fde\u901a\u5206\u91cf<\/h4>\n

      \u5728\u65e0\u5411\u56fe<\/strong>\u4e2d\uff0c\u82e5\u9876\u70b9v\u5230\u9876\u70b9w\u6709\u8def\u5f84\u5b58\u5728\uff0c\u5219\u79f0v\u548cw\u662f\u8fde\u901a\u7684\u3002\u82e5\u56feG\u4e2d\u4efb\u610f\u4e24\u4e2a\u9876\u70b9\u90fd\u662f\u8fde\u901a\u7684\uff0c\u5219\u79f0\u56feG\u4e3a\u8fde\u901a\u56fe\uff0c\u5426\u5219\u79f0\u4e3a\u975e\u8fde\u901a\u56fe\u3002\u65e0\u5411\u56fe\u4e2d\u7684\u6781\u5927\u8fde\u901a\u5b50\u56fe\uff0c\u79f0\u4e3a\u8fde\u901a\u5206\u91cf\u3002<\/p>\n

    1.1.7 \u5f3a\u8fde\u901a\u56fe\u3001\u5f3a\u8fde\u901a\u5206\u91cf<\/h4>\n

      \u5728\u6709\u5411\u56fe<\/strong>\u4e2d\uff0c\u82e5\u4e00\u5bf9\u9876\u70b9w\u548cv\uff0c\u82e5\u53ef\u4ecew\u5230v\u3001\u53ef\u4ecev\u5230w\u3002\u90a3\u4e48w\u548cv\u4e4b\u95f4\u662f\u5f3a\u8fde\u901a\u7684\u3002\u5176\u4f59\u6982\u5ff5\u4e0e\u4e0a\u8ff0\u8fde\u901a\u56fe\u76f8\u540c\u3002<\/p>\n

    1.1.8 \u751f\u6210\u6811\u3001\u751f\u6210\u68ee\u6797<\/h4>\n

      \u5bf9\u4e8e\u4e00\u4e2a\u8fde\u901a\u56feG\uff0c\u82e5\u5176\u4e00\u4e2a\u5b50\u56feG1\u662f\u4e00\u9897\u5305\u542bG\u6240\u6709\u9876\u70b9\u7684\u6811\uff0c\u5219\u8be5\u5b50\u56fe\u79f0\u4e3aG\u7684\u751f\u6210\u6811\u3002\u751f\u6210\u6811\u662f\u5305\u542b\u56feG\u6240\u6709\u9876\u70b9\u7684\u6781\u5c0f\u8fde\u901a\u5b50\u56fe\u3002<\/p>\n

    1.1.9 \u9876\u70b9\u7684\u5ea6\u3001\u5165\u5ea6\u548c\u51fa\u5ea6<\/h4>\n

      \u5728\u65e0\u5411\u56fe\u4e2d\uff0c\u9876\u70b9v\u7684\u5ea6\u662f\u6307\u4f9d\u9644\u4e8e\u9876\u70b9v\u7684\u8fb9\u7684\u6761\u6570\u3002
    \n  \u5728\u6709\u5411\u56fe\u4e2d\uff0c\u51fa\u5ea6\u662f\u4ecev\u51fa\u53d1\u7684\u8fb9\u6570\uff0c\u5165\u5ea6\u662f\u5230\u8fbev\u7684\u8fb9\u6570\u3002<\/p>\n

    1.1.10 \u8fb9\u3001\u6743\u548c\u7f51<\/h4>\n

      \u5728\u56fe\u4e2d\uff0c\u6bcf\u6761\u8fb9\u4e0a\u90fd\u53ef\u4ee5\u6807\u4e0a\u67d0\u79cd\u6570\u503c\uff0c\u8be5\u6570\u503c\u88ab\u79f0\u4e3a\u8fb9\u7684\u6743\u503c\u3002\u8fd9\u79cd\u8fb9\u4e0a\u5e26\u6743\u503c\u7684\u56fe\u79f0\u4e3a\u5e26\u6743\u56fe\uff0c\u4e5f\u79f0\u4e3a\u7f51\u3002<\/p>\n

    1.1.11 \u7a00\u758f\u56fe\u3001\u7a20\u5bc6\u56fe<\/h4>\n

      \u8fb9\u5f88\u5c11\u7684\u56fe\u53eb\u7a00\u758f\u56fe\uff0c\u8fb9\u5f88\u591a\u7684\u56fe\u53eb\u7a20\u5bc6\u56fe\u3002\u4e00\u822c\u5f53\u56feG\u6ee1\u8db3|E|<|V|log|V|\uff0c\u53ef\u4ee5\u5c06\u56feG\u662f\u4e3a\u7a00\u758f\u56fe\u3002<\/p>\n

    1.1.12 \u8def\u5f84\u3001\u8def\u5f84\u957f\u5ea6\u548c\u56de\u8def<\/h4>\n

      \u9876\u70b9vp<\/sub>\u5230\u9876\u70b9vq<\/sub>\u4e4b\u95f4\u7684\u4e00\u6761\u8def\u5f84\u662f\u6307\u9876\u70b9\u5e8f\u5217vp<\/sub>...vi<\/sub>...vq<\/sub>\u3002\u8def\u5f84\u4e0a\u8fb9<\/strong>\u7684\u6570\u76ee\u79f0\u4e3a\u8def\u5f84\u957f\u5ea6\u3002\u7b2c\u4e00\u4e2a\u9876\u70b9\u548c\u6700\u540e\u4e00\u4e2a\u9876\u70b9\u76f8\u540c\u7684\u8def\u5f84\uff0c\u79f0\u4e3a\u56de\u8def\u6216\u73af\u3002<\/p>\n

    1.1.13 \u7b80\u5355\u8def\u5f84\u3001\u7b80\u5355\u56de\u8def<\/h4>\n

      \u9876\u70b9\u4e0d\u91cd\u590d\uff0c\u5373\u7b80\u5355\u3002<\/p>\n

    1.1.14 \u8ddd\u79bb<\/h4>\n

      \u4ece\u9876\u70b9u\u51fa\u53d1\u5230\u9876\u70b9v\u7684\u6700\u77ed\u8def\u5f84\u82e5\u5b58\u5728\uff0c\u5219\u6b64\u8def\u5f84\u7684\u957f\u5ea6\u79f0\u4e3a\u4eceu\u5230v\u7684\u8ddd\u79bb\u3002\u82e5\u4e0d\u5b58\u5728\u8def\u5f84\uff0c\u5219\u8ddd\u79bb\u4e3a\u65e0\u7a77\u3002<\/p>\n

    1.1.15 \u6709\u5411\u6811<\/h4>\n

      \u4e00\u4e2a\u9876\u70b9\u5165\u5ea6\u4e3a0\uff0c\u5176\u4f59\u9876\u70b9\u7684\u5165\u5ea6\u5747\u4e3a1\u7684\u6709\u5411\u56fe\uff0c\u79f0\u4e3a\u6709\u5411\u6811\u3002<\/p>\n

    \u4e8c\u3001\u56fe\u7684\u5b58\u50a8\u53ca\u57fa\u672c\u64cd\u4f5c<\/h2>\n

    2.1 \u90bb\u63a5\u77e9\u9635\u6cd5<\/h3>\n

      \u7528\u4e00\u4e2a\u4e00\u7ef4\u6570\u7ec4\u5b58\u653e\u56fe\u4e2d\u7684\u9876\u70b9<\/strong>\u4fe1\u606f\uff0c\u7528\u4e00\u4e2a\u4e8c\u7ef4\u6570\u7ec4\u5b58\u653e\u56fe\u4e2d\u7684\u8fb9<\/strong>\u7684\u4fe1\u606f\u3002\u5b58\u50a8\u9876\u4e4b\u95f4\u90bb\u63a5\u5173\u7cfb\u7684\u4e8c\u7ef4\u6570\u7ec4\u79f0\u4e3a\u90bb\u63a5\u77e9\u9635\u3002<\/p>\n

    struct MGraph\n{\n    int vertex[num];\n    int graph[num][num];\n    int vexnum, arcnum;\n    \/\/ \u5f53\u524d\u8282\u70b9\u7684\u9876\u70b9\u6570 \u548c \u5f27\u6570\n};\n<\/code><\/pre>\n
      \u5728\u4e0a\u8ff0\u56fe\u4e2d\uff0c\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7graph[1][3] = 1\u8868\u793a\u4ecevertex[1]\u53ef\u4ee5\u5230\u8fbevertex[3]\uff08\u4e0b\u6807\uff09\uff1b\u540c\u6837\uff0c\u4f7f\u7528[2][1] = 0\u8868\u793a\u4e0d\u53ef\u5230\u8fbe\u3002\u8fd9\u91cc\u9700\u8981\u533a\u5206\u6709\u5411\u56fe\u548c\u65e0\u5411\u56fe\uff0c\u65e0\u5411\u56fe\u662f\u5bf9\u79f0\u7684\uff0c\u6709\u5411\u56fe\u5219\u4e0d\u662f\u3002<\/p>\n
    2.2 \u90bb\u63a5\u8868\u6cd5<\/h3>\n
      \u4e3a\u4e86\u89e3\u51b3\u90bb\u63a5\u77e9\u9635\u5229\u7528\u7387\u4f4e\u7684\u95ee\u9898\uff0c\u8fd9\u91cc\u4f7f\u7528\u90bb\u63a5\u8868\u6765\u5b8c\u6210\u3002<\/p>\n
    \/\/ \u90bb\u63a5\u8282\u70b9\nstruct ArcNode\n{\n    int adjvex; \/\/ \u90bb\u63a5\u8282\u70b9\u7f16\u53f7\n    ArcNode* next;  \/\/ \u6307\u5411\u4e0b\u4e00\u4e2a\u8282\u70b9\n}\n\n\/\/ \u90bb\u63a5\u8868\nstruct AdjList\n{\n    std::list<ArcNode*> ArcList;    \/\/ \u9876\u70b9\u5217\u8868\n    int vexnum, arcnum;\n    \/\/ \u5f53\u524d\u8282\u70b9\u7684\u9876\u70b9\u6570 \u548c \u5f27\u6570\n}\n<\/code><\/pre>\n
      \u4e3a\u4e86\u66f4\u597d\u5730\u7406\u89e3\u90bb\u63a5\u8868\u4e0e\u90bb\u63a5\u77e9\u9635\u4e4b\u95f4\u7684\u8f6c\u5316\uff0c\u6211\u4eec\u7ed9\u51fa\u5982\u4e0b\u4f8b\u9898\uff1a
    \nDescription<\/strong>
    \n  \u7ed9\u4e00\u4e2a\u5e26\u6743\u6709\u5411\u56fe\u7684\u90bb\u63a5\u77e9\u9635\u8868\u793a\uff0c\u5c06\u4e4b\u8f6c\u6362\u4e3a\u90bb\u63a5\u8868\u7684\u8868\u793a\uff0c\u5e76\u8f93\u51fa\u5bf9\u5e94\u7684\u90bb\u63a5\u8868
    \nInput<\/strong>
    \n  \u7b2c\u4e00\u884c\uff1a\u4e24\u4e2a\u6574\u6570m\uff08\u56fe\u7684\u8282\u70b9\u6570\uff09\uff0cn\uff08\u56fe\u7684\u8fb9\u6570\uff09\uff080 < n,m < 100,\uff09\u3002\u4f59\u4e0bn\u884c\uff1an*n\u77e9\u9635\uff0c\u4ee3\u8868\u77e9\u9635\u8868\u793a\u4e0b\u7684\u56fe\uff08\u5176\u4e2d\u4ee5\u975e\u96f6\u8868\u793a\u6709\u94fe\u63a5,\u6570\u5b57\u95f4\u4ee5\u7a7a\u683c\u9694\u5f00\uff09
    \nOutput<\/strong>
    \n  \u8f93\u51fa\u6709m\u884c\uff0c\u5bf9\u5e94m\u4e2a\u8282\u70b9\u7684\u90bb\u63a5\u8868\u793a\u4e0b\u7684\u8282\u70b9\u8fde\u63a5\u60c5\u51b5
    \nSample Input<\/strong>
    \n6 10
    \n0 5 0 7 0 0
    \n0 0 4 0 0 0
    \n8 0 0 0 0 0
    \n0 0 5 0 0 6
    \n0 0 5 0 0 0
    \n3 0 0 0 1 0
    \nSample Output<\/strong>
    \n0:1 3
    \n1:2
    \n2:0
    \n3:2 5
    \n4:2
    \n5:0 4<\/p>\n
    2.3 \u5341\u5b57\u94fe\u8868\u4e0e\u90bb\u63a5\u591a\u91cd\u8868<\/h3>\n
    p 208; \u540e\u9762\u8981\u8003\u518d\u8865\u5145\u3002<\/p>\n
    \u4e09\u3001\u56fe\u7684\u904d\u5386<\/h2>\n
    3.1 \u5e7f\u5ea6\u4f18\u5148\u641c\u7d22 BFS<\/h3>\n
    \u9898\u76ee\u63cf\u8ff0<\/strong>
    \n  \u56fe\u7684\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22\u7c7b\u4f3c\u4e8e\u6811\u7684\u6309\u5c42\u6b21\u904d\u5386\uff0c\u5373\u4ece\u67d0\u4e2a\u7ed3\u70b9\u5f00\u59cb\uff0c\u5148\u8bbf\u95ee\u8be5\u7ed3\u70b9\uff0c\u7136\u540e\u8bbf\u95ee\u8be5\u7ed3\u70b9\u7684\u6240\u6709\u90bb\u63a5\u70b9\uff0c\u518d\u4f9d\u6b21\u8bbf\u95ee\u5404\u90bb\u63a5\u70b9\u7684\u90bb\u63a5\u70b9\u3002\u5982\u6b64\u8fdb\u884c\u4e0b\u53bb\uff0c\u76f4\u5230\u6240\u6709\u7684\u7ed3\u70b9\u90fd\u8bbf\u95ee\u4e3a\u6b62\u3002\u5728\u8be5\u9898\u4e2d\uff0c\u5047\u5b9a\u6240\u6709\u7684\u7ed3\u70b9\u4ee5\u201cA\u201d--\u201cZ\u201d\u4e2d\u7684\u82e5\u5e72\u5b57\u7b26\u8868\u793a\uff0c\u4e14\u8981\u6c42\u7ed3\u70b9\u7684\u8bbf\u95ee\u987a\u5e8f\u6839\u636e\u5f55\u5165\u7684\u987a\u5e8f\u8fdb\u884c\u8bbf\u95ee\u3002\u5982\u679c\u7ed3\u70b9\u5f55\u5165\u7684\u987a\u5e8f\u4e3aHUEAK\uff0c\u8981\u6c42\u4eceH\u5f00\u59cb\u8fdb\u884c\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22\uff0c\u5219\u53ef\u80fd\u7684\u641c\u7d22\u7ed3\u679c\u4e3a\uff1aH->E->A->U->K.
    \n\u8f93\u5165<\/strong>
    \n  \u7b2c\u4e00\u884c\u4e3a\u4e00\u4e2a\u6574\u6570n\uff0c\u8868\u793a\u9876\u70b9\u7684\u4e2a\u6570\uff0c\u7b2c\u4e8c\u884c\u4e3an\u4e2a\u5927\u5199\u5b57\u6bcd\u6784\u6210\u7684\u5b57\u7b26\u4e32\uff0c\u8868\u793a\u9876\u70b9\uff0c\u63a5\u4e0b\u6765\u662f\u4e3a\u4e00\u4e2an*n\u5927\u5c0f\u7684\u6574\u6570\u77e9\u9635\uff0c\u8868\u793a\u56fe\u7684\u90bb\u63a5\u5173\u7cfb\u3002\u6570\u5b57\u4e3a0\u8868\u793a\u4e0d\u90bb\u63a5\uff0c\u5426\u5219\u4e3a\u76f8\u5e94\u7684\u8fb9\u7684\u957f\u5ea6\u3002\u6700\u540e\u4e00\u884c\u4e3a\u4e00\u4e2a\u5b57\u7b26\uff0c\u8868\u793a\u8981\u6c42\u8fdb\u884c\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22\u7684\u8d77\u59cb\u9876\u70b9\u3002
    \n\u8f93\u51fa<\/strong>
    \n  \u7528\u4e00\u884c\u8f93\u51fa\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22\u7ed3\u679c\uff0c\u8d77\u59cb\u70b9\u4e3a\u7ed9\u5b9a\u7684\u9876\u70b9\u3002
    \n\u6837\u4f8b\u8f93\u5165<\/strong>
    \n5
    \nHUEAK
    \n0 0 2 3 0
    \n0 0 0 7 4
    \n2 0 0 0 0
    \n3 7 0 0 1
    \n0 4 0 1 0
    \nH
    \n\u6837\u4f8b\u8f93\u51fa<\/strong>
    \nHEAUK<\/p>\n
    #include <iostream>\n#include <vector>\n#include <string>\n#include <deque>\n\n\/\/ \u8282\u70b9\u5143\u7d20\nstruct Node\n{\n    int id;         \/\/ \u8282\u70b9\u5e8f\u53f7\n    bool flag;      \/\/ \u662f\u5426\u8bbf\u95ee\u8fc7\n    char ele;       \/\/ \u5b58\u50a8\u7684\u5143\u7d20\n    std::vector<int>list;   \/\/ \u5f53\u524d\u8282\u70b9\u7684\u8def\u5f84, 0\u8868\u793a\u4e0d\u53ef\u5230\u8fbe[i]\u8282\u70b9, n\u8868\u793a\u53ef\u5230\u8fbe[i]\u8282\u70b9\n\n    \/\/ \u6784\u9020\u51fd\u6570\n    Node():\n        flag{ true }, ele{ '\\0' }\n    { }\n};\n\n\/*\n    BFS\u641c\u7d22\u51fd\u6570\n\n    \u8fd4\u56de\u503c\uff1aBFS\u904d\u5386\u7684\u7ed3\u679c\n    \u53c2\u65701\uff1a\u9876\u70b9\u6570\u7ec4\n    \u53c2\u65702\uff1a\u641c\u7d22\u8d77\u70b9\n*\/\nstd::string BFS(std::vector<Node> Vertex, \n                Node Begin);\n\nint main()\n{\n\/* ========== Section I : \u6570\u636e\u51c6\u5907 ========== *\/\n    \/\/ \u56fe\u7684\u5927\u5c0f\n    int size{ 0 };\n    \/\/ \u9876\u70b9\u5143\u7d20\n    std::string Vertex_ele;\n    \/\/ \u9876\u70b9\n    std::vector<Node> Vertex;\n\n    \/\/ \u5f55\u5165\u5927\u5c0f\u548c\u9876\u70b9\n    std::cin >> size >> Vertex_ele;\n    \/\/ \u9876\u70b9\u5927\u5c0f\u6539\u53d8\n    Vertex.resize(size);\n\n    \/\/ \u8bfb\u5165\u6570\u636e\n    for (int i = 0; i < size; ++i)\n    {\n        \/\/ ele\u8d4b\u503c\n        Vertex[i].ele = Vertex_ele.at(i);\n        Vertex[i].id = i;\n\n        \/\/ list\u8d4b\u503c\n        for (int j = 0; j < size; ++j)\n        {\n            int input{ 0 };\n            std::cin >> input;\n            Vertex[i].list.push_back(input);\n        }\n    }\n\n    \/\/ \u5f00\u59cb\u641c\u7d22\u7684\u5143\u7d20\uff0c\u5373\u641c\u7d22\u8d77\u70b9\n    char BeginCh;\n    std::cin >> BeginCh;\n\n\/* ========== Section II : BFS ========== *\/\n    \/\/ \u5b9a\u4f4d\u641c\u7d22\u8d77\u70b9\n    for (int i = 0; i < size; ++i)\n    {\n        if(Vertex[i].ele == BeginCh)\n        {\n            std::cout << BFS(Vertex, Vertex[i]);\n            break;\n        }\n    }\n\n    return 0;\n}\n\nstd::string BFS(std::vector<Node> Vertex, Node Begin)\n{\n    \/\/ BFS\u904d\u5386\u961f\u5217\n    std::deque<Node> Trans;\n\n    Trans.push_back(Begin);\n\n    \/\/ \u8fd4\u56de\u503c\n    std::string re;\n\n    \/\/ \u5f00\u59cb\u904d\u5386\n    while(!Trans.empty())\n    {\n        \/\/ \u961f\u9996\n        Node head = Trans.front();\n        Trans.pop_front();\n\n        \/\/ \u8bbf\u95ee\u5143\u7d20 \u8fd9\u91cc\u9700\u8981\u5224\u65ad\u662f\u5426\u53ef\u4ee5\u8bbf\u95ee\n        if (Vertex[head.id].flag == true)\n        {\n            re.push_back(head.ele);\n        }\n        else\n        {\n            continue;\n        }\n        \/\/ \u961f\u9996\u8282\u70b9flag\u7f6e0\n        Vertex[head.id].flag = false;\n\n        \/\/ \u67e5\u627ehead\u53ef\u5230\u8fbe\u7684\u8282\u70b9\n        for (int i = 0; i < Vertex.size(); ++i)\n        {\n            if (head.list[i] != 0               \/\/ \u53ef\u5230\u8fbe\n                && Vertex[i].flag == true)      \/\/ \u672a\u8bbf\u95ee\n            {\n                Trans.push_back(Vertex[i]);\n            }\n        }\n    }\n\n    return re;\n}\n<\/code><\/pre>\n
    3.1.1 BFS\u6027\u80fd\u5206\u6790<\/h4>\n
    \u7a7a\u95f4\u590d\u6742\u5ea6<\/h5>\n
      O(vertex)\uff0c\u9700\u8981\u81f3\u591asize == vertex\u7684\u961f\u5217\u3002<\/p>\n
    \u65f6\u95f4\u590d\u6742\u5ea6<\/h5>\n
      O(vertex)\uff0c\u6700\u574f\u60c5\u51b5\u4e0b\u6bcf\u4e2a\u70b9\u90fd\u8981\u5165\u961f\u4e00\u6b21\u3002<\/p>\n
    3.1.2 BFS\u6700\u77ed\u8def\u5f84<\/h4>\n
      \u5229\u7528\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22\u603b\u662f\u6309\u8ddd\u79bb\u904d\u5386<\/strong>\u7684\u7279\u6027\uff0c\u6211\u4eec\u53ef\u4ee5\u5229\u7528\u5b83\u6765\u6c42\u6700\u77ed\u8def\u5f84\u3002\u4e0b\u9762\u6211\u4eec\u8ba1\u7b97\u4ecevBegin\u5230vEnd\u7684\u8ddd\u79bb\uff0c\u5373\u6211\u4eec\u53ea\u9700\u8981\u5728while\u5faa\u73af\u91cc\u9762\u52a0\u5165\u4e00\u4e2adistence++\u5373\u53ef\u3002\u4f46\u662f\u9700\u8981\u6ce8\u610f\u7684\u662f\uff0c\u6211\u4eec\u8fd9\u91cc\u904d\u5386\uff0c\u4e0d\u518d\u662f\u6bcf\u6b21\u53d6\u51fa\u5934\u7ed3\u70b9\u904d\u5386\uff0c\u800c\u662f\u53d6\u51fa\u961f\u5217\u91cc\u9762\u6240\u6709\u8282\u70b9<\/strong>\uff08\u5373\u4e00\u5c42\uff09\u5faa\u73af\u4e00\u6b21\uff0c\u5373\u6211\u4eec\u4f7f\u7528\u5c42\u6b21\u904d\u5386<\/strong>\u8ba1\u7b97\u8ddd\u79bb\u3002<\/p>\n
    int BFS(std::vector<Node> Vertex, Node Begin)\n{\n    \/\/ BFS\u904d\u5386\u961f\u5217\n    std::deque<Node> Trans;\n\n    Trans.push_back(Begin);\n\n    \/\/ \u8fd4\u56de\u503c\n    std::string re;\n\n    int distance = 0;\n\n    \/\/ \u5f00\u59cb\u904d\u5386 - \u6bcf\u6b21\u5faa\u73af\u904d\u5386\u4e00\u5c42\n    while(!Trans.empty())\n    {   \n        \/\/ \u53d6\u51fa\u961f\u5217\u6240\u6709\u5143\u7d20\n        std::list<Node> nodes = all nodes in deque(Trans);\n\n        \/\/ \u5224\u65ad\u8282\u70b9\u662f\u5426\u53ef\u4ee5\u904d\u5386\n        for (auto node : nodes)\n        {\n            \/\/ \u5224\u65ad\u662f\u5426\u53ef\u4ee5\u904d\u5386\n            if (node.flag == true)\n            {\n                \/\/ node flag\u7f6e0\uff0c\u5e76\u968f\u540e\u8bbf\u95ee\n                node.flag = false;\n            }\n            else if (node.flag == false)\n            {\n                \/\/ node \u79fb\u9664\u51falist\n                nodes.remove(node);\n            }\n        }\n\n        \/\/ \u8bbf\u95ee\u6240\u6709\u8282\u70b9\n        for (auto node : nodes)\n        {\n            \/\/ \u8bbf\u95ee\uff0c\u5e76\u5c06\u5176\u53ef\u5230\u8fbe\u7684\u8282\u70b9\u538b\u5165\u961f\u5217\n\n            if (node.list[i] != 0               \/\/ \u53ef\u5230\u8fbe\n                && Vertex[i].flag == true)      \/\/ \u672a\u8bbf\u95ee\n            {\n                Trans.push_back(Vertex[i]);\n            }\n        }\n\n        \/\/ \u6bcf\u4e00\u5c42\u7684\u8ddd\u79bb\n        distance++;\n    }\n\n    return distance;\n}\n<\/code><\/pre>\n
    3.2 \u6df1\u5ea6\u4f18\u5148\u641c\u7d22 DFS<\/h3>\n
    \u9898\u76ee\u63cf\u8ff0<\/strong>
    \n  \u56fe\u7684\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u7c7b\u4f3c\u4e8e\u6811\u7684\u5148\u6839\u904d\u5386\uff0c\u5373\u4ece\u67d0\u4e2a\u7ed3\u70b9\u5f00\u59cb\uff0c\u5148\u8bbf\u95ee\u8be5\u7ed3\u70b9\uff0c\u7136\u540e\u6df1\u5ea6\u8bbf\u95ee\u8be5\u7ed3\u70b9\u7684\u7b2c\u4e00\u68f5\u5b50\u6811\uff0c\u4f9d\u6b21\u4e3a\u7b2c\u4e8c\u9876\u5b50\u6811\u3002\u5982\u6b64\u8fdb\u884c\u4e0b\u53bb\uff0c\u76f4\u5230\u6240\u6709\u7684\u7ed3\u70b9\u90fd\u8bbf\u95ee\u4e3a\u6b62\u3002\u5728\u8be5\u9898\u4e2d\uff0c\u5047\u5b9a\u6240\u6709\u7684\u7ed3\u70b9\u4ee5\u201cA\u201d\u81f3\u201cZ\u201d\u4e2d\u7684\u82e5\u5e72\u5b57\u7b26\u8868\u793a\uff0c\u4e14\u8981\u6c42\u7ed3\u70b9\u7684\u8bbf\u95ee\u987a\u5e8f\u6839\u636e\u5f55\u5165\u7684\u987a\u5e8f\u8fdb\u884c\u8bbf\u95ee\u3002\u5982\u679c\u7ed3\u70b9\u5f55\u5165\u7684\u987a\u5e8f\u4e3aHUEAK\uff0c\u4eceH\u5f00\u59cb\u8fdb\u884c\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\uff0c\u5219\u53ef\u80fd\u7684\u641c\u7d22\u7ed3\u679c\u4e3a\uff1aH->A->K->U>E.
    \n\u8f93\u5165<\/strong>
    \n  \u7b2c\u4e00\u884c\u4e3a\u4e00\u4e2a\u6574\u6570n\uff0c\u8868\u793a\u9876\u70b9\u7684\u4e2a\u6570\uff0c\u7b2c\u4e8c\u884c\u4e3an\u4e2a\u5927\u5199\u5b57\u6bcd\u6784\u6210\u7684\u5b57\u7b26\u4e32\uff0c\u8868\u793a\u9876\u70b9\uff0c\u63a5\u4e0b\u6765\u662f\u4e3a\u4e00\u4e2an*n\u5927\u5c0f\u7684\u6574\u6570\u77e9\u9635\uff0c\u8868\u793a\u56fe\u7684\u90bb\u63a5\u5173\u7cfb\u3002\u6570\u5b57\u4e3a0\u8868\u793a\u4e0d\u90bb\u63a5\uff0c\u5426\u5219\u4e3a\u76f8\u5e94\u7684\u8fb9\u7684\u957f\u5ea6\u3002\u6700\u540e\u4e00\u884c\u4e3a\u4e00\u4e2a\u5b57\u7b26\uff0c\u8868\u793a\u8981\u6c42\u8fdb\u884c\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u7684\u8d77\u59cb\u9876\u70b9\u3002
    \n\u8f93\u51fa<\/strong>
    \n  \u7528\u4e00\u884c\u8f93\u51fa\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u7ed3\u679c\uff0c\u8d77\u59cb\u70b9\u4e3a\u7ed9\u5b9a\u7684\u9876\u70b9\u3002
    \n\u6837\u4f8b\u8f93\u5165<\/strong>
    \n5
    \nHUEAK
    \n0 0 2 3 0
    \n0 0 0 7 4
    \n2 0 0 0 0
    \n3 7 0 0 1
    \n0 4 0 1 0
    \nH
    \n\u6837\u4f8b\u8f93\u51fa<\/strong>
    \nHEAUK<\/p>\n
    #include <iostream>\n#include <vector>\n#include <string>\n#include <deque>\n\n\/\/ \u8282\u70b9\u5143\u7d20\nstruct Node\n{\n    int id;         \/\/ \u8282\u70b9\u5e8f\u53f7\n    bool flag;      \/\/ \u662f\u5426\u8bbf\u95ee\u8fc7\n    char ele;       \/\/ \u5b58\u50a8\u7684\u5143\u7d20\n    std::vector<int>list;   \/\/ \u5f53\u524d\u8282\u70b9\u7684\u8def\u5f84, 0\u8868\u793a\u4e0d\u53ef\u5230\u8fbe[i]\u8282\u70b9, n\u8868\u793a\u53ef\u5230\u8fbe[i]\u8282\u70b9\n\n    \/\/ \u6784\u9020\u51fd\u6570\n    Node():\n        flag{ true }, ele{ '\\0' }\n    { }\n};\n\nstd::string ans;    \/\/ \u904d\u5386\u7ed3\u679c\n\n\/*\n    DFS\u641c\u7d22\u51fd\u6570\n\n    \u8fd4\u56de\u503c\uff1avoid\n    \u53c2\u65701\uff1a\u9876\u70b9\u6570\u7ec4\n    \u53c2\u65702\uff1a\u5f53\u524d\u8282\u70b9\n*\/\nvoid DFS(std::vector<Node>& Vertex, Node& node);\n\nint main()\n{\n\/* ========== Section I : \u6570\u636e\u51c6\u5907 ========== *\/\n    \/\/ \u56fe\u7684\u5927\u5c0f\n    int size{ 0 };\n    \/\/ \u9876\u70b9\u5143\u7d20\n    std::string Vertex_ele;\n    \/\/ \u9876\u70b9\n    std::vector<Node> Vertex;\n\n    \/\/ \u5f55\u5165\u5927\u5c0f\u548c\u9876\u70b9\n    std::cin >> size >> Vertex_ele;\n    \/\/ \u9876\u70b9\u5927\u5c0f\u6539\u53d8\n    Vertex.resize(size);\n\n    \/\/ \u8bfb\u5165\u6570\u636e\n    for (int i = 0; i < size; ++i)\n    {\n        \/\/ ele\u8d4b\u503c\n        Vertex[i].ele = Vertex_ele.at(i);\n        Vertex[i].id = i;\n\n        \/\/ list\u8d4b\u503c\n        for (int j = 0; j < size; ++j)\n        {\n            int input{ 0 };\n            std::cin >> input;\n            Vertex[i].list.push_back(input);\n        }\n    }\n\n    \/\/ \u5f00\u59cb\u641c\u7d22\u7684\u5143\u7d20\uff0c\u5373\u641c\u7d22\u8d77\u70b9\n    char BeginCh;\n    std::cin >> BeginCh;\n\n\/* ========== Section II : BFS ========== *\/\n    \/\/ \u5b9a\u4f4d\u641c\u7d22\u8d77\u70b9\n    for (int i = 0; i < size; ++i)\n    {\n        if(Vertex[i].ele == BeginCh)\n        {\n            DFS(Vertex, Vertex[i]);\n            break;\n        }\n    }\n\n    std::cout << ans << std::endl;\n\n    return 0;\n}\n\nvoid DFS(std::vector<Node>& Vertex, Node& node)\n{\n    \/\/ false \u5219\u8fd4\u56de\n    if (!node.flag) return;\n\n    \/\/ \u8bbf\u95ee\u5143\u7d20\n    ans.push_back(node.ele);\n\n    \/\/ \u6807\u8bb0flag\u4e3aflase\n    node.flag = false;\n\n    \/\/ \u904d\u5386\u53ef\u5230\u8fbe\u7684\u70b9\n    for (int i = 0; i < Vertex.size(); i++)\n    {\n        if (node.list[i] != 0)\n        {\n            DFS(Vertex, Vertex[i]);\n        }\n    }\n}\n<\/code><\/pre>\n
    3.2.1 DFS\u6027\u80fd\u5206\u6790<\/h4>\n
    \u7a7a\u95f4\u590d\u6742\u5ea6<\/h5>\n
      O(vertex)\uff0c\u9700\u8981\u501f\u52a9\u6808\u5b9e\u73b0\u63d0\u67dc\u3002<\/p>\n
    \u65f6\u95f4\u590d\u6742\u5ea6<\/h5>\n
      \u4ee5\u90bb\u63a5\u77e9\u9635\u8868\u793a\u65f6\uff0c\u67e5\u627e\u6bcf\u4e2a\u9876\u70b9\u6240\u9700\u7684\u65f6\u95f4\u4e3aO(vertex)\uff0c\u603b\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(vertex2<\/sup>)\uff1b\u4ee5\u90bb\u63a5\u8868\u50a8\u5b58\u65f6\uff0c\u67e5\u627e\u6240\u6709\u9876\u70b9\u6240\u9700\u65f6\u95f4\u4e3aO(Edge)\uff0c\u603b\u65f6\u95f4\u4e3aO(Edge2<\/sup>)\u3002<\/p>\n
    \u56db\u3001\u56fe\u7684\u5e94\u7528<\/h2>\n
    4.1 \u6700\u5c0f\u751f\u6210\u6811<\/h3>\n
    4.1.1 Prim\u7b97\u6cd5<\/h4>\n
    void Prim(G, T)\n{\n    \/*\n        T : \u6811\n        U : \u7528\u4e8e\u7edf\u8ba1\u9876\u70b9\u662f\u5426\u5168\u90e8\u52a0\u5165\u6811\u4e2d\n    *\/\n    T = nullptr;        \/\/ \u521d\u59cb\u5316\u6811\uff0c\u4f7f\u5176\u4e3a\u7a7a\n    U = { w };          \/\/ \u5c06\u4efb\u610f\u4e00\u70b9w\uff0c\u6dfb\u52a0\u5165\u6811\n\n    while (U.size() != G.size())  \n    {\n        step 1: \u5bfb\u627e\u5f53\u524dT\u96c6\u5408\u4e0eG\u56fe\u4e4b\u95f4\u6743\u503c\u6700\u5c0f\u7684\u4e24\u4e2a\u70b9\uff0c\u5373Tn\u548cGn\u3002\n        step 2: \u8fb9Tn-Gn \u52a0\u5165 T\u4e2d\u3002\n        step 3: \u9876\u70b9Gn \u52a0\u5165 U\u4e2d\u3002\n    }\n}\n<\/code><\/pre>\n
    4.1.2 Kruskal\u7b97\u6cd5<\/h4>\n
    void Kruskal(V, T)\n{\n    \/*\n        E : \u8fb9\u96c6\u5408\uff0c\u7528\u4e8e\u5b58\u653e\u6240\u6709\u7684\u8fb9\u4ee5\u53ca\u5176\u957f\u5ea6\n    *\/\n    T = V;          \/\/ \u521d\u59cb\u5316\u6811\uff0c\u4ec5\u542b\u9876\u70b9\n    CC = n;         \/\/ \u8054\u901a\u5206\u91cf = \u9876\u70b9\u6570\n    while (CC > 1)\n    {\n        step 1: \u4eceE\u4e2d\u9009\u51fa\u6700\u77ed\u7684\u8fb9v-u\u3002\n        step 2: \u5982\u679c u\u548cv\u5c5e\u4e8eT\u4e2d\u4e0d\u540c\u7684\u8054\u901a\u5206\u91cf\uff0c\u5219\u6b64\u8fb9\u52a0\u5165T\u6811\u3001\u8054\u901a\u5206\u91cf\u6570CC--\u3002\n    }\n}\n<\/code><\/pre>\n
    4.1.3 \u6bd4\u8f83<\/h4>\n\"\u56fe1\"\n
      \u5728Prim\u7b97\u6cd5\u4e2d\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(V2<\/sup>)\uff1b\u5728Kruskal\u7b97\u6cd5\u4e2d\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(E*logE)\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
    \u56fe\u5b9a\u4e49\u5b58\u50a8\u7ed3\u6784\u76f8\u90bb\u77e9\u9635\u3001\u90bb\u63a5\u8868\u6cd5\u90bb\u63a5\u591a\u91cd\u8868\u3001\u5341\u5b57\u94fe\u8868\u904d\u5386\u5e7f\u5ea6\u4f18\u5148\u904d\u5386\u5e7f\u5ea6\u4f18\u5148\u76f8\u5173\u5e94\u7528\u6700\u5c0f\u751f\u6210\u6811\uff1a\u7b97\u6cd5\u3001\u7b97\u6cd5\u6700\u77ed\u8def\u5f84\uff1a\u7b97\u6cd5\u3001\u7b97\u6cd5\u62d3\u6251 …<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[60],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/730"}],"collection":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/comments?post=730"}],"version-history":[{"count":3,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/730\/revisions"}],"predecessor-version":[{"id":733,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/730\/revisions\/733"}],"wp:attachment":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/media?parent=730"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/categories?post=730"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/tags?post=730"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}