E\uff1a\u8fb9\u7684\u6709\u7a77<\/strong>\u96c6\u5408<\/p>\n \u65e0\u5411\u56fe<\/strong>\uff1a\u6bcf\u6761\u8fb9\u90fd\u662f\u65e0\u65b9\u5411\u7684<\/p>\n \u6709\u5411\u56fe<\/strong>\uff1a\u6bcf\u6761\u8fb9\u90fd\u662f\u6709\u65b9\u5411\u7684<\/p>\n <\/p>\n \u5b8c\u5168\u56fe<\/strong>\uff1a\u4efb\u610f\u4e24\u4e2a\u70b9\u90fd\u6709\u4e00\u6761\u8fb9\u76f8\u8fde<\/p>\n <\/p>\n \u7a00\u758f\u56fe<\/strong>\uff1a\u6709\u5f88\u5c11\u8fb9\u6216\u5f27\u7684\u56fe\uff08e<nlogn\uff09<\/p>\n \u7a20\u5bc6\u56fe<\/strong>\uff1a\u6709\u8f83\u591a\u8fb9\u6216\u5f27\u7684\u56fe<\/p>\n \u7f51<\/strong>\uff1a\u8fb9\/\u5f27\u5e26\u6743<\/strong>\u7684\u56fe<\/p>\n \u90bb\u63a5<\/strong>\uff1a\u6709\u8fb9\/\u5f27\u76f8\u8fde\u7684\u4e24\u4e2a\u9876\u70b9\u4e4b\u95f4\u7684\u5173\u7cfb<\/p>\n \u5173\u8054(\u4f9d\u9644)<\/strong>\uff1a\u8fb9\/\u5f27\u4e0e\u9876\u70b9\u4e4b\u95f4\u7684\u5173\u7cfb<\/p>\n \u9876\u70b9\u7684\u5ea6<\/strong>\uff1a\u4e0e\u8be5\u9876\u70b9\u76f8\u5173\u8054\u7684\u8fb9\u7684\u6570\u76ee\uff0c\u8bb0\u4e3aTD(v)\uff1b<\/p>\n \u5728\u6709\u5411\u56fe<\/strong>\u4e2d\uff0c\u9876\u70b9\u7684\u5ea6\u7b49\u4e8e\u8be5\u9876\u70b9\u7684\u5165\u5ea6<\/strong>\u4e0e\u51fa\u5ea6<\/strong>\u4e4b\u548c<\/strong><\/p>\n <\/p>\n \u8def\u5f84<\/strong>\uff1a\u63a5\u7eed\u7684\u8fb9\u6784\u6210\u7684\u9876\u70b9\u5e8f\u5217<\/p>\n \u8def\u5f84\u957f\u5ea6<\/strong>\uff1a\u8def\u5f84\u4e0a\u8fb9\u6216\u5f27\u7684\u6570\u76ee\/\u6743\u503c\u4e4b\u548c<\/p>\n \u56de\u8def(\u73af)<\/strong>\uff1a\u7b2c\u4e00\u4e2a\u9876\u70b9\u548c\u6700\u540e\u4e00\u4e2a\u9876\u70b9\u76f8\u540c\u7684\u8def\u5f84<\/p>\n \u7b80\u5355\u8def\u5f84<\/strong>\uff1a\u9664\u8def\u5f84\u8d77\u70b9\u548c\u7ec8\u70b9\u53ef\u4ee5\u76f8\u540c\u5916\uff0c\u5176\u4f59\u9876\u70b9\u5747\u4e0d\u76f8\u540c\u7684\u8def\u5f84<\/p>\n \u7b80\u5355\u56de\u8def(\u7b80\u5355\u73af)<\/strong>\uff1a\u9664\u8def\u5f84\u8d77\u70b9\u548c\u7ec8\u70b9\u76f8\u540c\u5916\uff0c\u5176\u4f59\u9876\u70b9\u5747\u4e0d\u76f8\u540c\u7684\u8def\u5f84<\/p>\n <\/p>\n \u8fde\u901a\u56fe(\u5f3a\u8fde\u901a\u56fe)<\/strong>\uff1a\u5728\u65e0\uff08\u6709\uff09\u5411\u56feG=\uff08V\uff0c{E}\uff09\uff0c\u82e5\u5bf9\u4efb\u4f55\u4e24\u4e2a\u9876\u70b9v\u3001u\u90fd\u5b58\u5728\u4ecev\u5230u\u7684\u8def\u5f84\uff0c\u5219\u79f0G\u662f\u8fde\u901a\u56fe<\/strong>\uff08\u5f3a\u8fde\u901a\u56fe\uff09<\/p>\n <\/p>\n \u6743\u4e0e\u7f51<\/strong>\uff1a\u56fe\u4e2d\u8fb9\u6216\u5f27\u6240\u5177\u6709\u7684\u76f8\u5173\u6570\u79f0\u4e3a\u6743<\/strong>\u3002\u8868\u660e\u4ece\u4e00\u4e2a\u9876\u70b9\u5230\u53e6\u4e00\u4e2a\u9876\u70b9\u7684\u8ddd\u79bb\u6216\u8017\u8d39\uff1b\u5e26\u6743\u7684\u56fe\u79f0\u4e3a\u7f51<\/strong><\/p>\n <\/p>\n \u5b50\u56fe<\/strong><\/p>\n <\/p>\n \u8fde\u901a\u5206\u91cf\uff08\u5f3a\u8fde\u901a\u5206\u91cf\uff09<\/strong><\/p>\n <\/p>\n \u6781\u5c0f\u8fde\u901a\u5b50\u56fe<\/strong>\uff1a\u8be5\u5b50\u56fe\u662fG\u7684\u8fde\u901a\u5b50\u56fe\uff0c\u5728\u8be5\u5b50\u56fe\u4e2d\u5220\u9664\u4efb\u4f55\u4e00\u6761\u8fb9\uff0c\u5b50\u56fe\u4e0d\u518d\u8fde\u901a<\/p>\n \u751f\u6210\u6811<\/strong>\uff1a\u5305\u542b\u65e0\u5411\u56feG\u6240\u6709\u9876\u70b9\u7684\u6781\u5c0f\u8fde\u901a\u5b50\u56fe<\/p>\n \u751f\u6210\u68ee\u6797<\/strong>\uff1a\u5bf9\u975e\u8fde\u901a\u56fe\uff0c\u7531\u5404\u4e2a\u8fde\u901a\u5206\u91cf\u7684\u751f\u6210\u6811\u7684\u96c6\u5408<\/p>\n <\/p>\n \u516d\u5ea6\u7a7a\u95f4\u7406\u8bba\uff08\u5c0f\u4e16\u754c\u7406\u8bba\uff09<\/p>\n \u628a\u516d\u5ea6\u7a7a\u95f4\u7406\u8bba\u4e2d\u7684\u4eba\u9645\u5173\u7cfb\u7f51\u7edc\u62bd\u8c61\u6210\u4e00\u4e2a\u65e0\u5411\u56feG\u3002\u7528\u56feG\u4e2d\u7684\u4e00\u4e2a\u9876\u70b9\u8868\u793a\u4e00\u4e2a\u4eba\uff0c\u4e24\u4e2a\u4eba\u8ba4\u8bc6\u4e0e\u5426\u7528\u4ee3\u8868\u8fd9\u4e24\u4e2a\u4eba\u7684\u9876\u70b9\u4e4b\u95f4\u662f\u5426\u6709\u4e00\u6761\u8fb9\u6765\u8868\u793a\u3002\u4ece\u4efb\u4e00\u9876\u70b9\u51fa\u53d1\u7528\u5e7f\u5ea6\u4f18\u5148\u65b9\u6cd5\u5bf9\u56fe\u8fdb\u884c\u904d\u5386\uff0c\u7edf\u8ba1\u6240\u6709\u8def\u5f84\u957f\u5ea6\u4e0d\u8d85\u8fc77\u7684\u9876\u70b9<\/p>\n <\/p>\n <\/p>\n \u91cd\u8981\u64cd\u4f5c\uff1a<\/p>\n CreatGraph(&G, V, VR)<\/p>\n <\/p>\n DFSTraverse(G)<\/p>\n <\/p>\n BFSTraverse(G)<\/p>\n <\/p>\n \u56fe\u7684\u903b\u8f91\u7ed3\u6784\uff1a\u591a\u5bf9\u591a<\/p>\n \u56fe\u6ca1\u6709\u987a\u5e8f\u5b58\u50a8\u7ed3\u6784\uff0c\u4f46\u53ef\u4ee5\u501f\u52a9\u4e8c\u7ef4\u6570\u7ec4\u6765\u8868\u793a\u5143\u7d20\u95f4\u7684\u5173\u7cfb\uff1b\u8fd9\u79cd\u8868\u793a\u6cd5\u53eb\u505a\uff1a\u6570\u7ec4\u8868\u793a\u6cd5\uff08\u90bb\u63a5\u77e9\u9635<\/strong>\uff09<\/p>\n \u94fe\u5f0f\u5b58\u50a8\u7ed3\u6784\uff1a\u591a\u91cd\u94fe\u8868<\/p>\n <\/p>\n <\/p>\n \u6ce8\uff1a\u5728\u6709\u5411\u56fe\u7684\u90bb\u63a5\u77e9\u9635\u4e2d\uff0c<\/p>\n <\/p>\n \u5206\u6790\uff1a<\/p>\n <\/p>\n \u5373\uff08\u6709\u6743\u56fe\uff09\u7684\u90bb\u63a5\u77e9\u9635\u8868\u793a<\/p>\n <\/p>\n \u7b97\u6cd5\u601d\u60f3\uff1a<\/p>\n <\/p>\n \u90bb\u63a5\u77e9\u9635\u7684\u597d\u5904\uff1a<\/p>\n <\/p>\n \u574f\u5904\uff1a<\/p>\n <\/p>\n \u7279\u70b9\uff1a<\/p>\n <\/p>\n <\/p>\n <\/p>\n \u7b97\u6cd5\u601d\u60f3\uff1a<\/p>\n <\/p>\n \u90bb\u63a5\u8868\u7279\u70b9\uff1a<\/p>\n <\/p>\n \u90bb\u63a5\u77e9\u9635\u548c\u90bb\u63a5\u8868\u793a\u6cd5\u7684\u5173\u7cfb<\/p>\n <\/p>\n <\/p>\n \u5341\u5b57\u94fe\u8868(Orthogonal List)\u662f\u6709\u5411\u56fe\u7684\u53e6\u4e00\u79cd\u94fe\u5f0f\u5b58\u50a8\u7ed3\u6784\u3002\u6211\u4eec\u4e5f\u53ef\u4ee5\u628a\u5b83\u770b\u6210\u662f\u5c06\u6709\u5411\u56fe\u7684\u90bb\u63a5\u8868\u548c\u9006\u90bb\u63a5\u8868\u7ed3\u5408\u8d77\u6765\u5f62\u6210\u7684\u4e00\u79cd\u94fe\u8868<\/p>\n \u6709\u5411\u56fe\u4e2d\u7684\u6bcf\u4e00\u6761\u5f27\u5bf9\u5e94\u5341\u5b57\u94fe\u8868\u4e2d\u7684\u4e00\u4e2a\u5f27\u7ed3\u70b9<\/strong>\uff0c\u540c\u65f6\u6709\u5411\u56fe\u4e2d\u7684\u6bcf\u4e2a\u9876\u70b9\u5728\u5341\u5b57\u94fe\u8868\u4e2d\u5bf9\u5e94\u6709\u4e00\u4e2a\u7ed3\u70b9\uff0c\u53eb\u505a\u9876\u70b9\u7ed3\u70b9<\/strong><\/p>\n <\/p>\n <\/p>\n \u904d\u5386\u7684\u5b9a\u4e49\uff1a<\/p>\n \u4ece\u5df2\u7ed9\u7684\u8fde\u901a\u56fe\u4e2d\u67d0\u4ee5\u9876\u70b9\u51fa\u53d1\uff0c\u6cbf\u7740\u4e00\u4e9b\u8fb9\u8bbf\u904d\u56fe\u4e2d\u6240\u6709\u7684\u9876\u70b9\uff0c\u4e14\u4f7f\u6bcf\u4e2a\u9876\u70b9\u4ec5\u88ab\u8bbf\u95ee\u4e00\u6b21\uff0c\u5c31\u53eb\u505a\u56fe\u7684\u904d\u5386\uff0c\u5b83\u662f\u56fe\u7684\u57fa\u672c\u8fd0\u7b97<\/p>\n <\/p>\n \u56fe\u7684\u7279\u70b9\uff1a<\/p>\n \u56fe\u4e2d\u53ef\u80fd\u5b58\u5728\u56de\u8def\uff0c\u4e14\u56fe\u7684\u4efb\u4e00\u9876\u70b9\u90fd\u53ef\u80fd\u4e0e\u5176\u5b83\u9876\u70b9\u76f8\u901a\uff0c\u5728\u8bbf\u95ee\u5b8c\u67d0\u4e2a\u9876\u70b9\u4e4b\u540e\u53ef\u80fd\u4f1a\u6cbf\u7740\u67d0\u4e9b\u8fb9\u53c8\u56de\u5230\u4e86\u66fe\u7ecf\u8bbf\u95ee\u8fc7\u7684\u9876\u70b9<\/strong><\/p>\n <\/p>\n \u600e\u6837\u907f\u514d\u91cd\u590d\u8bbf\u95ee\uff1f<\/p>\n \u89e3\u51b3\u601d\u8def\uff1a\u8bbe\u7f6e\u8f85\u52a9\u6570\u7ec4 visited[n]\uff0c\u7528\u6765\u6807\u8bb0\u6bcf\u4e2a\u88ab\u8bbf\u95ee\u8fc7\u7684\u9876\u70b9<\/p>\n <\/p>\n Depth First Search\u2014\u2014\u2014\u2014DFS<\/p>\n <\/p>\n \u65b9\u6cd5\uff1a<\/p>\n <\/p>\n \u65f6\u95f4\u590d\u6742\u5ea6\uff1a<\/p>\n \u7ed3\u8bba\uff1a<\/p>\n <\/p>\n \u6d4b\u8bd5\u4ee3\u7801<\/p>\n \u6d4b\u8bd5\u622a\u56fe<\/p>\n <\/p>\n \u65b9\u6cd5\uff1a<\/p>\n <\/p>\n \u7c7bC\u8bed\u8a00<\/p>\n \u65f6\u95f4\u590d\u6742\u5ea6\uff1a<\/p>\n <\/p>\n C\u8bed\u8a00\u5b9e\u73b0<\/p>\n \u6d4b\u8bd5\u622a\u56fe<\/p>\n <\/p>\n <\/p>\n \u751f\u6210\u6811\uff1a\u6240\u6709\u9876\u70b9\u5747\u7531\u8fb9\u8fde\u63a5\u5728\u4e00\u8d77\uff0c\u4f46\u4e0d\u5b58\u5728\u56de\u8def<\/strong>\u7684\u56fe<\/p>\n \u4e00\u4e2a\u56fe\u53ef\u4ee5\u6709\u8bb8\u591a\u68f5\u4e0d\u540c\u7684\u751f\u6210\u6811<\/p>\n \u6240\u6709\u751f\u6210\u6811\u5177\u6709\u4ee5\u4e0b\u5171\u540c\u7279\u70b9\uff1a<\/p>\n <\/p>\n \u65e0\u5411\u56fe\u7684\u751f\u6210\u6811<\/p>\n <\/p>\n MST\u6027\u8d28\uff1a<\/p>\n \u5728\u751f\u6210\u6811\u7684\u6784\u9020\u8fc7\u7a0b\u4e2d\uff0c\u56fe\u4e2dn\u4e2a\u9876\u70b9\u5206\u5c5e\u4e24\u4e2a\u96c6\u5408\uff1a<\/p>\n <\/p>\n \u7b97\u6cd5\u601d\u60f3\uff1a<\/p>\n \u56fe\u89e3\uff1a<\/p>\n \u4ee5\u4e0a\u56feG4\u4e3a\u4f8b\uff0c\u6765\u5bf9\u666e\u91cc\u59c6\u8fdb\u884c\u6f14\u793a(\u4ece\u7b2c\u4e00\u4e2a\u9876\u70b9A\u5f00\u59cb\u901a\u8fc7\u666e\u91cc\u59c6\u7b97\u6cd5\u751f\u6210\u6700\u5c0f\u751f\u6210\u6811)\u3002<\/p>\n \u521d\u59cb\u72b6\u6001<\/strong>\uff1aV\u662f\u6240\u6709\u9876\u70b9\u7684\u96c6\u5408\uff0c\u5373V={A,B,C,D,E,F,G}\uff1bU\u548cT\u90fd\u662f\u7a7a\uff01 \u6b64\u65f6\uff0c\u6700\u5c0f\u751f\u6210\u6811\u6784\u9020\u5b8c\u6210\uff01\u5b83\u5305\u62ec\u7684\u9876\u70b9\u4f9d\u6b21\u662f\uff1aA B F E D C G<\/strong>\u3002<\/p>\n <\/p>\n \u6700\u5c0f\u751f\u6210\u6811\u53ef\u80fd\u4e0d\u552f\u4e00<\/p>\n <\/p>\n <\/p>\n \u4ea4\u901a\u7f51\u7edc\u7528\u6709\u5411\u7f51\u6765\u8868\u793a\uff1a<\/p>\n <\/p>\n \u95ee\u9898\u62bd\u8c61\uff1a\u5728\u6709\u5411\u7f51<\/strong>\u4e2dA\u70b9\uff08\u6e90\u70b9<\/strong>\uff09\u5230\u8fbeB\u70b9\uff08\u7ec8\u70b9<\/strong>\uff09\u7684\u591a\u6761\u8def\u5f84\u4e2d\uff0c\u5bfb\u627e\u4e00\u6761\u5404\u8fb9\u6743\u503c\u4e4b\u548c\u6700\u5c0f<\/strong>\u7684\u8def\u5f84\uff0c\u5373\u6700\u77ed\u8def\u5f84<\/strong><\/p>\n \u6700\u77ed\u8def\u5f84\u548c\u6700\u5c0f\u751f\u6210\u6811\u4e0d\u540c\uff0c\u8def\u5f84\u4e0a\u4e0d\u4e00\u5b9a\u5305\u542b n \u4e2a\u9876\u70b9\uff0c\u4e5f\u4e0d\u4e00\u5b9a\u5305\u542b n-1 \u6761\u8fb9<\/p>\n <\/p>\n \u7b2c\u4e00\u7c7b\u95ee\u9898<\/strong>\uff1a\u4e24\u70b9\u95f4\u7684\u6700\u77ed\u8def\u5f84<\/p>\n <\/p>\n \u7b2c\u4e8c\u7c7b\u95ee\u9898\uff1a\u67d0\u6e90\u70b9\u5230\u5176\u5b83\u5404\u70b9\u6700\u77ed\u8def\u5f84<\/p>\n <\/p>\n \u7b2c\u4e00\u7c7b\u95ee\u9898\uff1a\u5355\u6e90\u6700\u77ed\u8def\u5f84\u2014\u2014\u7528Dijkstra\uff08\u8fea\u6770\u65af\u7279\u62c9\uff09\u7b97\u6cd5<\/p>\n \u7b2c\u4e8c\u7c7b\u95ee\u9898\uff1a\u6240\u6709\u9876\u70b9\u95f4\u7684\u6700\u77ed\u8def\u5f84\u2014\u2014\u7528Floyd\uff08\u5f17\u6d1b\u4f0a\u5fb7\uff09\u7b97\u6cd5<\/p>\n <\/p>\n \u5728\u8c03\u6574\u540e\u7684\u5404\u6761\u8def\u5f84\u4e2d\uff0c\u518d\u627e\u957f\u5ea6\u6700\u77ed\u7684\u8def\u5f84\uff0c\u4f9d\u6b64\u7c7b\u63a8<\/p>\n \u6848\u4f8b\u5206\u6790<\/p>\n <\/p>\n \u7b97\u6cd5\u601d\u60f3\uff1a<\/p>\n <\/p>\n \u6709\u5411\u65e0\u73af\u56fe\uff1a\u65e0\u73af\u7684\u6709\u5411\u56fe\uff0c\u7b80\u79f0DAG\u56fe\uff08Directed Acycline Graph\uff09<\/p>\n \u6709\u5411\u65e0\u73af\u56fe\u5e38\u7528\u6765\u63cf\u8ff0\u4e00\u4e2a\u5de5\u7a0b\u6216\u7cfb\u7edf\u7684\u8fdb\u884c\u8fc7\u7a0b\u3002\uff08\u901a\u5e38\u628a\u8ba1\u5212\u3001\u65bd\u5de5\u3001\u751f\u4ea7\u3001\u7a0b\u5e8f\u6d41\u7a0b\u7b49\u5f53\u6210\u662f\u4e00\u4e2a\u5de5\u7a0b\uff09<\/p>\n \u4e00\u4e2a\u5de5\u7a0b\u53ef\u4ee5\u5206\u4e3a\u82e5\u5e72\u4e2a\u5b50\u5de5\u7a0b\uff0c\u53ea\u8981\u5b8c\u6210\u4e86\u8fd9\u4e9b\u5b50\u5de5\u7a0b\uff08\u6d3b\u52a8\uff09\uff0c\u5c31\u53ef\u4ee5\u5bfc\u81f4\u6574\u4e2a\u5de5\u7a0b\u7684\u5b8c\u6210<\/p>\n <\/p>\n AOV\u7f51\uff1a\u62d3\u6251\u6392\u5e8f<\/strong><\/p>\n \u7528\u4e00\u4e2a\u6709\u5411\u56fe\u8868\u793a\u4e00\u4e2a\u5de5\u7a0b\u7684\u5404\u4e2a\u5b50\u5de5\u7a0b\u53ca\u5176\u76f8\u4e92\u5236\u7ea6\u7684\u5173\u7cfb\uff0c\u5176\u4e2d\u4ee5\u9876\u70b9<\/strong>\u8868\u793a\u6d3b\u52a8<\/strong>\uff0c\u5f27\u8868\u793a\u6d3b\u52a8\u4e4b\u95f4\u7684\u4f18\u5148\u5236\u7ea6\u5173\u7cfb\uff0c\u79f0\u8fd9\u79cd\u6709\u5411\u7f51\u4e3a\u9876\u70b9\u8868\u793a\u6d3b\u52a8\u7684\u7f51\uff0c\u7b80\u79f0AOV\u7f51\uff08Activity On Vertex network\uff09<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440077.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440074.png\")
<\/p>\n\n
\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440079.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440078.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440085.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440076.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440612.png\")
<\/p>\n\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440610.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440617.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440618.png\")
<\/p>\n6.2 \u6848\u4f8b\u5f15\u5165<\/h2>\n
6.3 \u56fe\u7684\u7c7b\u578b\u5b9a\u4e49<\/h2>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440623.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440626.png\")
<\/p>\n\n
\n
\n
6.4 \u56fe\u7684\u5b58\u50a8\u7ed3\u6784<\/h2>\n
\n
6.4.1 \u90bb\u63a5\u77e9\u9635<\/h3>\n
\u65e0\u5411\u56fe<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440463.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440465.png\")
<\/p>\n\n
\/\/ \u56fe\u7684\u90bb\u63a5\u77e9\u9635\u5b58\u50a8\u8868\u793a\n#define MAX_VERTEX_NUM 20\t\/\/ \u6700\u5927\u9876\u70b9\u6570\n#define maxInt 65535\t\t\/\/ \u65e0\u7a77\u5927\ntypedef char vertexType;\t\/\/ \u9876\u70b9\u7c7b\u578b\ntypedef int arcType;\t\t\/\/ \u8fb9\u4e0a\u7684\u6743\u503c\u7c7b\u578b\n\ntypedef struct {\n\tvertexType vexs[MAX_VERTEX_NUM];\t\/\/ \u9876\u70b9\u96c6\u5408\n\tarcType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];\t\/\/ \u90bb\u63a5\u77e9\u9635\n\tint vexNum, arcNum;\t\/\/ \u56fe\u7684\u5f53\u524d\u9876\u70b9\u6570\u548c\u5f27\u6570\n}adjacencyMatrix;\n<\/code><\/pre>\n\u6709\u5411\u56fe<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440472.png\")
<\/p>\n\n
\n
\u7f51<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440476.png\")
<\/p>\n\u5b9e\u73b0<\/h4>\n
\n
\/*******************************************************************************************************************************\n * @description\uff1a\u8fd4\u56de\u9876\u70b9u\u5728\u56feG\u4e2d\u7684\u4f4d\u7f6e\n * @param\uff1aG\n * @param\uff1au\n * @return\uff1a\n *\/\nint locateVex(adjacencyMatrixGraph* G, vertexType u)\n{\n\tint i;\n\tfor (i = 0; i < G->vexNum; i++) {\n\t\tif (G->vexs[i] == u) {\n\t\t\treturn i;\n\t\t}\n\t}\n\treturn -1;\n}\n\n\n\n\n\n\/*******************************************************************************************************************************\n * @description\uff1a\u521b\u5efa\u65e0\u5411\u7f51\n * @param\uff1aG\n * @return\uff1a\n *\/\nstatus createUDN(adjacencyMatrixGraph* G)\n{\n\tvertexType v1, v2;\n\tint i, j, k, w;\n\tprintf(\"\u8bf7\u8f93\u5165\u9876\u70b9\u6570\u548c\u8fb9\u6570\uff1a\");\n\tscanf(\"%d,%d\", &G->vexNum, &G->arcNum);\n\tprintf(\"\u8bf7\u8f93\u5165\u9876\u70b9\u4fe1\u606f\uff1a\");\n\tfor (i = 0; i < G->vexNum; i++) {\n\t\tscanf(\"%c\", &G->vexs[i]);\n\t}\n\tfor (i = 0; i < G->vexNum; i++) {\n\t\tfor (j = 0; j < G->vexNum; j++) {\n\t\t\tG->arcs[i][j] = maxInt;\n\t\t}\n\t}\n\tfor (k = 0; k < G->arcNum; k++) {\n\t\tprintf(\"\u8bf7\u8f93\u5165\u4e00\u6761\u8fb9\u6240\u4f9d\u9644\u7684\u9876\u70b9\u548c\u6743\u503cw\uff1a\");\n\t\tscanf(\"%c,%c,%d\", &v1, &v2, &w);\n\t\ti = locateVex(G, v1);\n\t\tj = locateVex(G, v2);\n\t\tG->arcs[i][j] = w;\n\t\tG->arcs[j][i] = G->arcs[i][j];\t\/\/ \u65e0\u5411\u56fe\u5bf9\u79f0\n\t}\n\treturn OK;\n}\n<\/code><\/pre>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440481.png\")
<\/p>\n\n
\n
\n
\n
6.4.2 \u90bb\u63a5\u8868<\/h3>\n
\u65e0\u5411\u56fe<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440486.png\")
<\/p>\n\n
\u6709\u5411\u56fe<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440262.png\")
<\/p>\n\/\/ \u56fe\u7684\u90bb\u63a5\u8868\u5b58\u50a8\u8868\u793a\ntypedef struct arcNode {\n\tint adjVex;\t\/\/ \u8be5\u5f27\u6240\u6307\u5411\u7684\u9876\u70b9\u7684\u4f4d\u7f6e\n\tstruct arcNode* nextArc;\t\/\/ \u6307\u5411\u4e0b\u4e00\u6761\u5f27\u7684\u6307\u9488\n\tarcType info;\t\/\/ \u8be5\u5f27\u7684\u76f8\u5173\u4fe1\u606f\n}arcNode;\n\n\ntypedef struct {\n\tvertexType data;\t\/\/ \u9876\u70b9\u4fe1\u606f\n\tarcNode* firstArc;\t\/\/ \u6307\u5411\u7b2c\u4e00\u6761\u4f9d\u9644\u8be5\u9876\u70b9\u7684\u5f27\u7684\u6307\u9488\n}adjacencyListVertexNode;\n\n\ntypedef struct {\n\tadjacencyListVertexNode vertices[MAX_VERTEX_NUM];\t\/\/ \u9876\u70b9\u5411\u91cf\n\tint vexNum, arcNum;\t\/\/ \u56fe\u7684\u5f53\u524d\u9876\u70b9\u6570\u548c\u5f27\u6570\n}adjacencyList;\n<\/code><\/pre>\n\u5b9e\u73b0<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440283.png\")
<\/p>\n\n
\n
\n
\/*******************************************************************************************************************************\n * @description\uff1a\u8fd4\u56de\u9876\u70b9u\u5728\u56feG\u4e2d\u7684\u4f4d\u7f6e\n * @param\uff1aG\n * @param\uff1au\n * @return\uff1a\n *\/\nint locateVex_ByAL(adjacencyListGraph* G, vertexType u)\n{\n\tint i;\n\tfor (i = 0; i < G->vexNum; i++) {\n\t\tif (G->vertices[i].data == u) {\n\t\t\treturn i;\n\t\t}\n\t}\n\treturn -1;\n}\n\n\n\n\n\n\/*******************************************************************************************************************************\n * @description\uff1a\u7528\u90bb\u63a5\u8868\u521b\u5efa\u65e0\u5411\u7f51\n * @param\uff1aG\n * @return\uff1a\n *\/\nstatus createUDN_ByAL(adjacencyListGraph* G)\n{\n\tvertexType v1, v2;\n\tint i, j, k, w;\n\tarcNode* p;\n\tprintf(\"\u8bf7\u8f93\u5165\u9876\u70b9\u6570\u548c\u8fb9\u6570\uff1a\");\n\tscanf(\"%d,%d\", &G->vexNum, &G->arcNum);\n\tprintf(\"\u8bf7\u8f93\u5165\u9876\u70b9\u4fe1\u606f\uff1a\");\n\tfor (i = 0; i < G->vexNum; i++) {\n\t\tscanf(\"%c\", &G->vertices[i].data);\n\t\tG->vertices[i].firstArc = NULL;\n\t}\/\/ \u521d\u59cb\u5316\u90bb\u63a5\u8868\u7ed3\u675f\n\n\tfor (k = 0; k < G->arcNum; k++) {\n\t\tprintf(\"\u8bf7\u8f93\u5165\u4e00\u6761\u8fb9\u6240\u4f9d\u9644\u7684\u9876\u70b9\u548c\u6743\u503cw\uff1a\");\n\t\tscanf(\"%c,%c,%d\", &v1, &v2, &w);\n\t\ti = locateVex_ByAL(G, v1);\n\t\tj = locateVex_ByAL(G, v2);\n\t\t\/\/ \u91c7\u7528\u5934\u63d2\u6cd5\u63d2\u5165\u8fb9\u7ed3\u70b9\n\t\tp = (arcNode*)malloc(sizeof(arcNode));\n\t\tp->adjVex = j;\n\t\tp->info = w;\n\t\tp->nextArc = G->vertices[i].firstArc;\n\t\tG->vertices[i].firstArc = p;\n\t\t\/\/ \u65e0\u5411\u56fe\u5bf9\u79f0\uff1b\u82e5\u4e3a\u6709\u5411\u7f51\u4e0b\u9762\u53ef\u7701\u7565\n\t\t\/\/ \u540c\u7406\uff1a\u53ea\u8981\u4e0b\u9762\u7684\u4e0d\u8981\u4e0a\u9762\u7684\u5c31\u53ef\u4ee5\u5efa\u7acb\u9006\u90bb\u63a5\u8868\uff0c\u5373\u5165\u5ea6\n\t\tp = (arcNode*)malloc(sizeof(arcNode));\n\t\tp->adjVex = i;\n\t\tp->info = w;\n\t\tp->nextArc = G->vertices[j].firstArc;\n\t\tG->vertices[j].firstArc = p;\n\t}\n\treturn OK;\n}\n<\/code><\/pre>\n\n
\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440285.png\")
<\/p>\n\n
\n
6.4.3 \u5341\u5b57\u94fe\u8868<\/h3>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440280.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440295.png\")
<\/p>\n\/\/ \u56fe\u7684\u5341\u5b57\u94fe\u8868\u5b58\u50a8\u8868\u793a\n\n\/\/ \u9876\u70b9\u7ed3\u70b9\ntypedef struct vertexNode_CrossLinkedList {\n\tvertexType data;\t\/\/ \u9876\u70b9\u4fe1\u606f\n\tarcNode_CrossLinkedList* firstIn;\t\/\/ \u6307\u5411\u7b2c\u4e00\u6761\u5165\u5f27\u7684\u6307\u9488\n\tarcNode_CrossLinkedList* firstOut;\t\/\/ \u6307\u5411\u7b2c\u4e00\u6761\u51fa\u5f27\u7684\u6307\u9488\n}vertexNode_CrossLinkedList;\n\n\n\/\/ \u5f27\u7ed3\u70b9\ntypedef struct arcNode_CrossLinkedList {\n\tint tailVex, headVex;\t\/\/ \u8be5\u5f27\u7684\u5c3e\u548c\u5934\u9876\u70b9\u7684\u4f4d\u7f6e\n\tstruct arcNode_CrossLinkedList* headLink;\t\/\/ \u6307\u5411\u5f27\u5934\u76f8\u540c\u7684\u4e0b\u4e00\u6761\u5f27\u7684\u6307\u9488\n\tstruct arcNode_CrossLinkedList* tailLink;\t\/\/ \u6307\u5411\u5f27\u5c3e\u76f8\u540c\u7684\u4e0b\u4e00\u6761\u5f27\u7684\u6307\u9488\n\tarcType info;\t\/\/ \u8be5\u5f27\u7684\u76f8\u5173\u4fe1\u606f\n}arcNode_CrossLinkedList;\n\n\n\/\/ \u5341\u5b57\u94fe\u8868\ntypedef struct {\n\tvertexNode_CrossLinkedList xlist[MAX_VERTEX_NUM];\t\/\/ \u9876\u70b9\u5411\u91cf\n\tint vexNum, arcNum;\t\/\/ \u56fe\u7684\u5f53\u524d\u9876\u70b9\u6570\u548c\u5f27\u6570\n}crossLinkListGraph;\n<\/code><\/pre>\n6.4.4 \u90bb\u63a5\u591a\u91cd\u8868<\/h3>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440301.png\")
<\/p>\n\/\/ \u56fe\u7684\u90bb\u63a5\u591a\u91cd\u8868\u5b58\u50a8\u8868\u793a\n\n\/\/ \u5f27\u7ed3\u70b9\ntypedef struct arcNode_AdjacencyMultipleList {\n\tint ivex, jvex;\t\/\/ \u8be5\u5f27\u4f9d\u9644\u7684\u4e24\u4e2a\u9876\u70b9\u7684\u4f4d\u7f6e\n\tstruct arcNode_AdjacencyMultipleList* ilink;\t\/\/ \u6307\u5411\u4f9d\u9644\u9876\u70b9ivex\u7684\u4e0b\u4e00\u6761\u5f27\u7684\u6307\u9488\n\tstruct arcNode_AdjacencyMultipleList* jlink;\t\/\/ \u6307\u5411\u4f9d\u9644\u9876\u70b9jvex\u7684\u4e0b\u4e00\u6761\u5f27\u7684\u6307\u9488\n\tarcType info;\t\/\/ \u8be5\u5f27\u7684\u76f8\u5173\u4fe1\u606f\n\tint mark;\t\/\/ \u8be5\u5f27\u662f\u5426\u5df2\u7ecf\u8bbf\u95ee\u8fc7\u7684\u6807\u5fd7\n}arcNode_AdjacencyMultipleList;\n\n\n\n\/\/ \u9876\u70b9\u7ed3\u70b9\ntypedef struct vertexNode_AdjacencyMultipleList {\n\tvertexType data;\t\/\/ \u9876\u70b9\u4fe1\u606f\n\tarcNode_AdjacencyMultipleList* firstArc;\t\/\/ \u6307\u5411\u7b2c\u4e00\u6761\u4f9d\u9644\u8be5\u9876\u70b9\u7684\u5f27\u7684\u6307\u9488\n}vertexNode_AdjacencyMultipleList;\n\n\n\/\/ \u90bb\u63a5\u591a\u91cd\u8868\ntypedef struct {\n\tvertexNode_AdjacencyMultipleList vNodes[MAX_VERTEX_NUM];\t\/\/ \u9876\u70b9\u5411\u91cf\n\tint vexNum, arcNum;\t\/\/ \u56fe\u7684\u5f53\u524d\u9876\u70b9\u6570\u548c\u5f27\u6570\n}adjacencyMultipleList;\n<\/code><\/pre>\n6.5 \u56fe\u7684\u904d\u5386<\/h2>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440388.png\")
<\/p>\n\n
6.5.1 \u6df1\u5ea6\u4f18\u5148\u904d\u5386<\/h3>\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440390.png\")
<\/p>\n\u5b9e\u73b0<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440399.png\")
<\/p>\n\/*******************************************************************************************************************************\n * @description\uff1a\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\n * @param\uff1aG\n * @param\uff1av\n *\/\nvoid DFS(adjacencyMatrixGraph G, int v)\n{\n\t\/\/ \u8bbf\u95ee\u9876\u70b9v\n\tvisited[v] = TRUE;\n\tprintf(\"%c \", G.vexs[v]);\n\t\/\/ \u5bf9v\u7684\u6bcf\u4e2a\u90bb\u63a5\u9876\u70b9w\n\tfor (int w = 0; w < G.vexNum; w++)\n\t\tif (G.arcs[v][w] == 1 && !visited[w])\n\t\t\tDFS(G, w);\n\n}\n<\/code><\/pre>\n\n
\n
void DFSMain()\n{\n\tadjacencyMatrixGraph G = { 0 };\n\t\/\/ \u5077\u61d2\u76f4\u63a5\u7528\u90bb\u63a5\u77e9\u9635\u521b\u5efa\u65e0\u5411\u56fe\n\tG.vexs[0] = '1';\n\tG.vexs[1] = '2';\n\tG.vexs[2] = '3';\n\tG.vexs[3] = '4';\n\tG.vexs[4] = '5';\n\tG.vexs[5] = '6';\n\n\t\/* \u6784\u5efa\u77e9\u9635\n\t* 0 1 1 1 0 0\n\t* 1 0 0 0 1 0\n\t* 1 0 0 0 1 0\n\t* 1 0 0 0 0 1\n\t* 0 1 1 0 0 0\n\t* 0 0 0 1 0 0\n\t*\/\n\n\tG.arcs[0][0] = 0; G.arcs[0][1] = 1; G.arcs[0][2] = 1; G.arcs[0][3] = 1; G.arcs[0][4] = 0; G.arcs[0][5] = 0;\n\tG.arcs[1][0] = 1; G.arcs[1][1] = 0; G.arcs[1][2] = 0; G.arcs[1][3] = 0; G.arcs[1][4] = 1; G.arcs[1][5] = 0;\n\tG.arcs[2][0] = 1; G.arcs[2][1] = 0; G.arcs[2][2] = 0; G.arcs[2][3] = 0; G.arcs[2][4] = 1; G.arcs[2][5] = 0;\n\tG.arcs[3][0] = 1; G.arcs[3][1] = 0; G.arcs[3][2] = 0; G.arcs[3][3] = 0; G.arcs[3][4] = 0; G.arcs[3][5] = 1;\n\tG.arcs[4][0] = 0; G.arcs[4][1] = 1; G.arcs[4][2] = 1; G.arcs[4][3] = 0; G.arcs[4][4] = 0; G.arcs[4][5] = 0;\n\tG.arcs[5][0] = 0; G.arcs[5][1] = 0; G.arcs[5][2] = 0; G.arcs[5][3] = 1; G.arcs[5][4] = 1; G.arcs[5][5] = 0;\n\n\tG.arcNum = 6;\n\tG.vexNum = 6;\n\n\n\tprintf(\"\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\uff1a\");\n\tDFS(G, 1);\n\n}\n<\/code><\/pre>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440394.png\")
<\/p>\n6.5.2 \u5e7f\u5ea6\u4f18\u5148\u904d\u5386<\/h3>\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440405.png\")
<\/p>\n\u5b9e\u73b0<\/h4>\n
void BFS(Graph G,int V)\n{\n cout<<v;\n visited[v] = true;\t\/\/ \u8bbf\u95ee\u7b2cv\u4e2a\u9876\u70b9\n initQueue(Q);\t\t\/\/ \u8f85\u52a9\u961f\u5217Q\u521d\u59cb\u5316\uff0c\u7f6e\u7a7a\n enQueue(Q, v);\t\t\/\/ v\u8fdb\u961f\n while(!isQueueEmpty(Q)){\n deQueue(Q, u);\t\/\/ \u961f\u5934\u5143\u7d20\u51fa\u961f\u5e76\u7f6e\u4e3au\n for(w = FirstAdjVex(G, u);w>=0;w = NextAdjVex(G, u,w)){\n if(!visited[w]){\t\/\/ w\u4e3au\u7684\u5c1a\u4e3a\u8bbf\u95ee\u7684\u90bb\u63a5\u7ed3\u70b9\n cout<<w;\n visited[w] = true;\t\n enQueue(Q, w);\t\/\/ w\u8fdb\u961f\n }\/\/ end if\n }\/\/ end for\n }\/\/ end while\n}\n<\/code><\/pre>\n\n
\/*******************************************************************************************************************************\n * @description\uff1a\u67e5\u627e\u7b2c\u4e00\u4e2a\u90bb\u63a5\u70b9\n * @param\uff1aG\n * @param\uff1av\n * @return\uff1a\n *\/\nstatic int firstAdjVex(adjacencyMatrixGraph* G, int v)\n{\n\tfor (int i = 0; i < G->vexNum; i++) {\n\t\tif (G->arcs[v][i] != 0) {\n\t\t\treturn i;\n\t\t}\n\t}\n\treturn -1;\n}\n\n\n\n\n\n\/*******************************************************************************************************************************\n * @description\uff1a\u67e5\u627e\u4e0b\u4e00\u4e2a\u90bb\u63a5\u70b9\n * @param\uff1aG\n * @param\uff1av\n * @param\uff1aw\n * @return\uff1a\n *\/\nstatic int nextAdjVex(adjacencyMatrixGraph* G, int v, int w)\n{\n\tfor (int i = w + 1; i < G->vexNum; i++) {\n\t\tif (G->arcs[v][i] != 0) {\n\t\t\treturn i;\n\t\t}\n\t}\n\treturn -1;\n}\n\n\n\n\n\n\n\/*******************************************************************************************************************************\n * @description\uff1a\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22\n * @param\uff1aG\n * @param\uff1av\n *\/\nvoid BFS(adjacencyMatrixGraph* G, int v)\n{\n\tint w;\n\t\/\/ \u521d\u59cb\u5316\u8f85\u52a9\u6570\u7ec4\n\tfor (int i = 0; i < G->vexNum; i++) {\n\t\tvisited_BFS[i] = 0;\n\t}\n\t\/\/ \u521d\u59cb\u5316\u961f\u5217\n\tqueue<int> Q;\n\t\/\/ \u8bbf\u95ee\u9876\u70b9v\n\tprintf(\"%c \", G->vexs[v]);\n\tvisited_BFS[v] = 1;\n\t\/\/ \u9876\u70b9v\u5165\u961f\n\tQ.push(v);\n\t\/\/ \u961f\u5217\u975e\u7a7a\n\twhile (!Q.empty()) {\n\t\t\/\/ \u51fa\u961f\n\t\tv = Q.front();\n\t\tQ.pop();\n\t\t\/\/ \u67e5\u627ev\u7684\u90bb\u63a5\u70b9\n\t\tfor (w = firstAdjVex(G, v); w >= 0; w = nextAdjVex(G, v, w)) {\n\t\t\t\/\/ \u672a\u8bbf\u95ee\u8fc7\n\t\t\tif (!visited_BFS[w]) {\n\t\t\t\t\/\/ \u8bbf\u95ee\u9876\u70b9w\n\t\t\t\tprintf(\"%c \", G->vexs[w]);\n\t\t\t\tvisited_BFS[w] = 1;\n\t\t\t\t\/\/ \u9876\u70b9w\u5165\u961f\n\t\t\t\tQ.push(w);\n\t\t\t}\n\t\t}\n\t}\n}\n<\/code><\/pre>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440414.png\")
<\/p>\n6.5.3 DFS\u548cBFS\u7684\u6bd4\u8f83<\/h3>\n
\n
6.6 \u56fe\u7684\u5e94\u7528<\/h2>\n
6.6.1 \u6700\u5c0f\u751f\u6210\u6811<\/h3>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440537.png\")
<\/p>\n\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440083.png\")
<\/p>\n\n
<\/p>\n\u666e\u91cc\u59c6Prim\u7b97\u6cd5<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440084.png\")
<\/p>\n<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440090.png\")
<\/p>\n
\n\u7b2c1\u6b65<\/strong>\uff1a\u5c06\u9876\u70b9A\u52a0\u5165\u5230U\u4e2d\u3002
\n\u6b64\u65f6\uff0cU={A}\u3002
\n\u7b2c2\u6b65<\/strong>\uff1a\u5c06\u9876\u70b9B\u52a0\u5165\u5230U\u4e2d\u3002
\n\u4e0a\u4e00\u6b65\u64cd\u4f5c\u4e4b\u540e\uff0cU={A}, V-U={B,C,D,E,F,G}\uff1b\u56e0\u6b64\uff0c\u8fb9(A,B)\u7684\u6743\u503c\u6700\u5c0f\u3002\u5c06\u9876\u70b9B\u6dfb\u52a0\u5230U\u4e2d\uff1b\u6b64\u65f6\uff0cU={A,B}\u3002
\n\u7b2c3\u6b65<\/strong>\uff1a\u5c06\u9876\u70b9F\u52a0\u5165\u5230U\u4e2d\u3002
\n\u4e0a\u4e00\u6b65\u64cd\u4f5c\u4e4b\u540e\uff0cU={A,B}, V-U={C,D,E,F,G}\uff1b\u56e0\u6b64\uff0c\u8fb9(B,F)\u7684\u6743\u503c\u6700\u5c0f\u3002\u5c06\u9876\u70b9F\u6dfb\u52a0\u5230U\u4e2d\uff1b\u6b64\u65f6\uff0cU={A,B,F}\u3002
\n\u7b2c4\u6b65<\/strong>\uff1a\u5c06\u9876\u70b9E\u52a0\u5165\u5230U\u4e2d\u3002
\n\u4e0a\u4e00\u6b65\u64cd\u4f5c\u4e4b\u540e\uff0cU={A,B,F}, V-U={C,D,E,G}\uff1b\u56e0\u6b64\uff0c\u8fb9(F,E)\u7684\u6743\u503c\u6700\u5c0f\u3002\u5c06\u9876\u70b9E\u6dfb\u52a0\u5230U\u4e2d\uff1b\u6b64\u65f6\uff0cU={A,B,F,E}\u3002
\n\u7b2c5\u6b65<\/strong>\uff1a\u5c06\u9876\u70b9D\u52a0\u5165\u5230U\u4e2d\u3002
\n\u4e0a\u4e00\u6b65\u64cd\u4f5c\u4e4b\u540e\uff0cU={A,B,F,E}, V-U={C,D,G}\uff1b\u56e0\u6b64\uff0c\u8fb9(E,D)\u7684\u6743\u503c\u6700\u5c0f\u3002\u5c06\u9876\u70b9D\u6dfb\u52a0\u5230U\u4e2d\uff1b\u6b64\u65f6\uff0cU={A,B,F,E,D}\u3002
\n\u7b2c6\u6b65<\/strong>\uff1a\u5c06\u9876\u70b9C\u52a0\u5165\u5230U\u4e2d\u3002
\n\u4e0a\u4e00\u6b65\u64cd\u4f5c\u4e4b\u540e\uff0cU={A,B,F,E,D}, V-U={C,G}\uff1b\u56e0\u6b64\uff0c\u8fb9(D,C)\u7684\u6743\u503c\u6700\u5c0f\u3002\u5c06\u9876\u70b9C\u6dfb\u52a0\u5230U\u4e2d\uff1b\u6b64\u65f6\uff0cU={A,B,F,E,D,C}\u3002
\n\u7b2c7\u6b65<\/strong>\uff1a\u5c06\u9876\u70b9G\u52a0\u5165\u5230U\u4e2d\u3002
\n\u4e0a\u4e00\u6b65\u64cd\u4f5c\u4e4b\u540e\uff0cU={A,B,F,E,D,C}, V-U={G}\uff1b\u56e0\u6b64\uff0c\u8fb9(F,G)\u7684\u6743\u503c\u6700\u5c0f\u3002\u5c06\u9876\u70b9G\u6dfb\u52a0\u5230U\u4e2d\uff1b\u6b64\u65f6\uff0cU=V\u3002<\/p>\n\/*******************************************************************************************************************************\n * @description\uff1aPrim\u7b97\u6cd5\uff0c\u751f\u6210\u6700\u5c0f\u751f\u6210\u6811\n * @param\uff1aG\n *\/\nvoid MiniSpanTree_Prim(adjacencyMatrixGraph G) {\n\tint min, i, j, k;\n\tint adjvex[MAX_VERTEX_NUM];\t\t\/\/ \u4fdd\u5b58\u76f8\u5173\u9876\u70b9\u4e0b\u6807\n\tint lowCost[MAX_VERTEX_NUM];\t\/\/ \u4fdd\u5b58\u76f8\u5173\u9876\u70b9\u95f4\u8fb9\u7684\u6743\u503c\n\tlowCost[0] = 0;\t\t\t\t\t\/\/ \u521d\u59cb\u5316\u7b2c\u4e00\u4e2a\u6743\u503c\u4e3a0\uff0c\u5373v0\u52a0\u5165\u751f\u6210\u6811\n\tadjvex[0] = 0;\t\t\t\t\t\/\/ \u521d\u59cb\u5316\u7b2c\u4e00\u4e2a\u9876\u70b9\u4e0b\u6807\u4e3a0\n\tfor (i = 1; i < G.vexNum; i++) {\n\t\tlowCost[i] = G.arcs[0][i];\t\/\/ \u5c06v0\u9876\u70b9\u4e0e\u4e4b\u6709\u8fb9\u7684\u6743\u503c\u5b58\u5165\u6570\u7ec4\n\t\tadjvex[i] = 0;\t\t\t\t\/\/ \u521d\u59cb\u5316\u90fd\u4e3av0\u7684\u4e0b\u6807\n\t}\n\tfor (i = 1; i < G.vexNum; i++) {\n\t\tmin = maxInt;\t\t\t\t\/\/ \u521d\u59cb\u5316\u6700\u5c0f\u6743\u503c\u4e3a\u221e\n\t\tj = 1; k = 0;\n\t\twhile (j < G.vexNum) {\n\t\t\tif (lowCost[j] != 0 && lowCost[j] < min) {\n\t\t\t\tmin = lowCost[j];\t\/\/ \u627e\u51fa\u5f53\u524d\u6700\u5c0f\u7684\n\t\t\t\tk = j;\t\t\t\t\/\/ \u5c06\u5f53\u524d\u6700\u5c0f\u6743\u503c\u7684\u4e0b\u6807\u5b58\u5165k\n\t\t\t}\n\t\t\tj++;\n\t\t}\n\t\tcout << \"(\" << adjvex[k] << \",\" << k << \")\" << endl;\t\/\/ \u6253\u5370\u5f53\u524d\u9876\u70b9\u8fb9\u4e2d\u6743\u503c\u6700\u5c0f\u7684\u8fb9\n\t\tlowCost[k] = 0;\t\/\/ \u5c06\u5f53\u524d\u9876\u70b9\u7684\u6743\u503c\u8bbe\u7f6e\u4e3a0\uff0c\u8868\u793a\u6b64\u9876\u70b9\u5df2\u7ecf\u5b8c\u6210\u4efb\u52a1\n\t\tfor (j = 1; j < G.vexNum; j++) {\n\t\t\tif (lowCost[j] != 0 && G.arcs[k][j] < lowCost[j]) {\n\t\t\t\tlowCost[j] = G.arcs[k][j];\t\/\/ \u5c06v0\u9876\u70b9\u4e0e\u4e4b\u6709\u8fb9\u7684\u6743\u503c\u5b58\u5165\u6570\u7ec4\n\t\t\t\tadjvex[j] = k;\t\/\/ \u521d\u59cb\u5316\u90fd\u4e3av0\u7684\u4e0b\u6807\n\t\t\t}\n\t\t}\n\t}\n}\n<\/code><\/pre>\n\u514b\u9c81\u65af\u5361\u5c14Kruskal\u7b97\u6cd5<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440093.png\")
<\/p>\n\/*******************************************************************************************************************************\n * @description\uff1asort()\u6240\u9700\u7684\u6bd4\u8f83\u51fd\u6570\n * @param\uff1aa\n * @param\uff1ab\n * @return\uff1a\n *\/\nstatic bool cmp(edge a, edge b) {\n\treturn a.weight < b.weight;\n}\n\n\n\n\n\n\n\/*******************************************************************************************************************************\n * @description\uff1a\u7528\u4e8e\u67e5\u627e\u8fde\u7ebf\u9876\u70b9\u7684\u5c3e\u90e8\u4e0b\u6807\n * @param\uff1aparent\n * @param\uff1af\n * @return\uff1a\n *\/\nstatic int find(int* parent, int f) {\n\twhile (parent[f] > 0) {\n\t\tf = parent[f];\n\t}\n\treturn f;\n}\n\n\n\n\n\n\n\/*******************************************************************************************************************************\n * @description\uff1aKruskal\u7b97\u6cd5\uff0c\u751f\u6210\u6700\u5c0f\u751f\u6210\u6811\n * @param\uff1aG\n *\/\nvoid MiniSpanTree_Kruskal(adjacencyMatrixGraph G) {\n\tint i, j, n, m;\n\tint k = 0;\t\/\/ \u7528\u4e8e\u7edf\u8ba1\u5f53\u524d\u751f\u6210\u6811\u8fb9\u6570\n\tint adjvex[MAX_VERTEX_NUM];\t\/\/ \u4fdd\u5b58\u76f8\u5173\u9876\u70b9\u4e0b\u6807\n\tedge edges[MAX_VERTEX_NUM];\t\/\/ \u5b9a\u4e49\u8fb9\u96c6\u6570\u7ec4\uff0cedge\u7684\u7ed3\u6784\u4e3a{begin,end,weight}\n\tfor (i = 0; i < G.vexNum; i++) {\n\t\tfor (j = i; j < G.vexNum; j++) {\n\t\t\tif (G.arcs[i][j] != 0 && G.arcs[i][j] < maxInt) {\n\t\t\t\tedges[k].begin = i;\n\t\t\t\tedges[k].end = j;\n\t\t\t\tedges[k].weight = G.arcs[i][j];\n\t\t\t\tk++;\n\t\t\t}\n\t\t}\n\t}\n\tsort(edges, edges + G.arcNum, cmp);\t\/\/ \u6309\u6743\u503c\u5927\u5c0f\u6392\u5e8f\uff0c\u4ece\u5c0f\u5230\u5927\n\tfor (i = 0; i < G.vexNum; i++) {\n\t\tadjvex[i] = 0;\n\t}\n\tfor (i = 0; i < G.arcNum; i++) {\n\t\tn = find(adjvex, edges[i].begin);\n\t\tm = find(adjvex, edges[i].end);\n\t\tif (n != m) {\n\t\t\tadjvex[n] = m;\n\t\t\tcout << \"(\" << edges[i].begin << \",\" << edges[i].end << \")\" << endl;\n\t\t}\n\t}\n}\n<\/code><\/pre>\n\u4e24\u79cd\u7b97\u6cd5\u6bd4\u8f83<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440203.png\")
<\/p>\n6.6.2 \u6700\u77ed\u8def\u5f84<\/h3>\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440925.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440928.png\")
<\/p>\n\u8fea\u6770\u65af\u7279\u62c9Dijkstra\u7b97\u6cd5<\/h4>\n
\n
\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440938.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440940.png\")
<\/p>\n\/*******************************************************************************************************************************\n * @description\uff1aDijkstra\u7b97\u6cd5\n * @param\uff1aG\n * @param\uff1av0\n * @param\uff1aP\n * @param\uff1aD\n * @return\uff1a\n *\/\nstatus Dijkstra(adjacencyMatrixGraph* G, int v0, int* P, int* D)\n{\n\tint final[MAX_VERTEX_NUM];\t\/\/ final[i] = 1\u8868\u793a\u6c42\u5f97\u9876\u70b9vi\u7684\u6700\u77ed\u8def\u5f84\n\tint v, w, k, min;\n\tfor (v = 0; v < G->vexNum; v++) {\t\/\/ \u521d\u59cb\u5316\n\t\tfinal[v] = 0;\t\/\/ \u5168\u90e8\u9876\u70b9\u521d\u59cb\u5316\u4e3a\u672a\u77e5\u6700\u77ed\u8def\u5f84\u72b6\u6001\n\t\tD[v] = G->arcs[v0][v];\t\/\/ \u5c06\u4e0ev0\u70b9\u6709\u8fde\u7ebf\u7684\u9876\u70b9\u52a0\u4e0a\u6743\u503c\n\t\tP[v] = 0;\t\/\/ \u521d\u59cb\u5316\u8def\u5f84\u6570\u7ec4P\u4e3a0\n\t}\n\tD[v0] = 0;\t\/\/ v0\u81f3v0\u8def\u5f84\u4e3a0\n\tfinal[v0] = 1;\t\/\/ v0\u81f3v0\u4e0d\u9700\u8981\u6c42\u8def\u5f84\n\t\/\/ \u5f00\u59cb\u4e3b\u5faa\u73af\uff0c\u6bcf\u6b21\u6c42\u5f97v0\u5230\u67d0\u4e2av\u9876\u70b9\u7684\u6700\u77ed\u8def\u5f84\n\tfor (v = 1; v < G->vexNum; v++) {\n\t\tmin = INFINITY;\t\/\/ \u5f53\u524d\u6240\u77e5\u79bbv0\u9876\u70b9\u7684\u6700\u8fd1\u8ddd\u79bb\n\t\tfor (w = 0; w < G->vexNum; w++) {\t\/\/ \u5bfb\u627e\u79bbv0\u6700\u8fd1\u7684\u9876\u70b9\n\t\t\tif (!final[w] && D[w] < min) {\n\t\t\t\tk = w;\n\t\t\t\tmin = D[w];\t\/\/ w\u9876\u70b9\u79bbv0\u9876\u70b9\u66f4\u8fd1\n\t\t\t}\n\t\t}\n\t\tfinal[k] = 1;\t\/\/ \u5c06\u76ee\u524d\u627e\u5230\u7684\u6700\u8fd1\u7684\u9876\u70b9\u7f6e\u4e3a1\n\t\tfor (w = 0; w < G->vexNum; w++) {\t\/\/ \u4fee\u6b63\u5f53\u524d\u6700\u77ed\u8def\u5f84\u53ca\u8ddd\u79bb\n\t\t\tif (!final[w] && (min + G->arcs[k][w] < D[w])) {\n\t\t\t\tD[w] = min + G->arcs[k][w];\t\/\/ \u4fee\u6539\u5f53\u524d\u8def\u5f84\u957f\u5ea6\n\t\t\t\tP[w] = k;\n\t\t\t}\n\t\t}\n\t}\n\treturn OK;\n}\n<\/code><\/pre>\n\u5f17\u6d1b\u4f0a\u5fb7Floyd\u7b97\u6cd5<\/h4>\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440949.png\")
<\/p>\n\/\/Floyd-Warshall\u7b97\u6cd5\u6838\u5fc3\u8bed\u53e5\n for(int k = 0; k < n; k++){\n for(int i = 0; i < n; i++){\n for(int j = 0; j < n; j++){\n if(e[i][k] + e[k][j] < e[i][j]){\n e[i][j] = e[i][k] + e[k][j];\n }\n }\n }\n }\n<\/code><\/pre>\n6.6.3 \u62d3\u6251\u6392\u5e8f<\/h3>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440950.png\")
<\/p>\n