{"id":22779,"date":"2020-12-19T12:16:21","date_gmt":"2020-12-19T04:16:21","guid":{"rendered":"https:\/\/swarma.org\/?p=22779"},"modified":"2020-12-19T12:16:21","modified_gmt":"2020-12-19T04:16:21","slug":"%e4%bb%80%e4%b9%88%e6%98%af%e5%9b%be%ef%bc%88%e6%8a%bd%e8%b1%a1%e6%95%b0%e6%8d%ae%e7%b1%bb%e5%9e%8b%ef%bc%89-%e9%9b%86%e6%99%ba%e7%99%be%e7%a7%91","status":"publish","type":"post","link":"https:\/\/swarma.org\/?p=22779","title":{"rendered":"\u4ec0\u4e48\u662f\u56fe\uff08\u62bd\u8c61\u6570\u636e\u7c7b\u578b\uff09| \u96c6\u667a\u767e\u79d1"},"content":{"rendered":"
\n
\n
\n
\n
\n

<\/p>\n

\u201c\u96c6\u667a\u767e\u79d1\u7cbe\u9009\u201d\u662f\u4e00\u4e2a\u957f\u671f\u4e13\u680f\uff0c\u6301\u7eed\u4e3a\u5927\u5bb6\u63a8\u9001\u590d\u6742\u6027\u79d1\u5b66\u76f8\u5173\u7684\u57fa\u672c\u6982\u5ff5\u548c\u8d44\u6e90\u4fe1\u606f\u3002\u4f5c\u4e3a\u96c6\u667a\u4ff1\u4e50\u90e8\u7684\u5f00\u6e90\u79d1\u5b66\u9879\u76ee\uff0c\u96c6\u667a\u767e\u79d1\u5e0c\u671b\u6253\u9020\u590d\u6742\u6027\u79d1\u5b66\u9886\u57df\u6700\u5168\u9762\u7684\u767e\u79d1\u5168\u4e66\uff0c\u6b22\u8fce\u5bf9\u590d\u6742\u6027\u79d1\u5b66\u611f\u5174\u8da3\u3001\u70ed\u7231\u77e5\u8bc6\u6574\u7406\u548c\u5206\u4eab\u7684\u670b\u53cb\u52a0\u5165\uff01<\/span>
<\/section>\n

<\/section>\n

\u672c\u6587\u662f\u5bf9\u96c6\u667a\u767e\u79d1\u4e2d\u201c\u56fe\uff08\u62bd\u8c61\u6570\u636e\u7c7b\u578b\uff09\u201d\u8bcd\u6761\u7684\u6458\u5f55\uff0c\u53c2\u8003\u8d44\u6599\u53ca\u76f8\u5173\u8bcd\u6761\u8bf7\u53c2\u9605\u767e\u79d1\u8bcd\u6761\u539f\u6587\u3002<\/span><\/p>\n


<\/section>\n

\u672c\u8bcd\u6761\u7531\u96c6\u667a\u4ff1\u4e50\u90e8\u4f17\u5305\u751f\u4ea7\uff0c\u96be\u514d\u5b58\u5728\u7eb0\u6f0f\u548c\u95ee\u9898\uff0c\u6b22\u8fce\u5927\u5bb6\u7559\u8a00\u53cd\u9988\u6216\u8005\u524d\u5f80\u5bf9\u5e94\u7684\u767e\u79d1\u8bcd\u6761\u9875\u9762\u8fdb\u884c\u4fee\u6539\uff0c\u4e00\u7ecf\u4fee\u6539\uff0c\u53ef\u4ee5\u83b7\u5f97\u5bf9\u5e94\u7684\u79ef\u5206\u5956\u52b1\u5662\uff01<\/span><\/em><\/span><\/p>\n


<\/p>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n

\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

\u76ee\u5f55<\/strong><\/p>\n


<\/p>\n

\n

\u4e00\u3001\u4ec0\u4e48\u56fe\uff08\u62bd\u8c61\u6570\u636e\u7c7b\u578b\uff09<\/strong><\/strong><\/p>\n

\u4e8c\u3001\u64cd\u4f5c\u65b9\u5f0f<\/strong><\/p>\n

\u4e09\u3001\u8868\u793a\u65b9\u6cd5<\/strong><\/p>\n

\u56db\u3001\u56fe\u7684\u5e76\u884c\u5316\u8868\u793a<\/strong><\/p>\n

\u4e94\u3001\u96c6\u667a\u767e\u79d1\u8bcd\u6761\u5fd7\u613f\u8005\u62db\u52df<\/strong><\/strong><\/strong><\/strong><\/strong><\/p>\n

<\/strong><\/strong><\/strong><\/strong><\/p>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n

\n
\n
\n
\n
\n
\n
\n
\n
\n
\n


<\/p>\n


<\/p>\n

<\/section>\n
\n
\n
\n
\u56fe\uff08\u62bd\u8c61\u6570\u636e\u7c7b\u578b\uff09\uff1a<\/section>\n
https:\/\/wiki.swarma.org\/index.php?title=\u56fe\uff08\u62bd\u8c61\u6570\u636e\u7c7b\u578b\uff09<\/section>\n<\/section>\n<\/section>\n<\/blockquote>\n


<\/p>\n


<\/p>\n

\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

<\/section>\n

<\/section>\n
\n
<\/svg><\/section>\n<\/section>\n<\/section>\n
\n

1. \u4ec0\u4e48\u662f\u56fe\uff08\u62bd\u8c61\u6570\u636e\u7c7b\u578b\uff09<\/strong><\/strong><\/p>\n<\/section>\n

\n

<\/section>\n

<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n


<\/p>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n

\n

\u5728\u8ba1\u7b97\u673a\u79d1\u5b66\u4e2d\uff0c\u56fe\u662f\u4e00\u79cd\u62bd\u8c61\u7684\u6570\u636e\u7c7b\u578b\uff0c\u5b83\u5b9e\u73b0\u4e86\u6570\u5b66\u4e2d\u56fe\u8bba\u9886\u57df\u7684\u4e24\u4e2a\u6982\u5ff5\uff1a\u65e0\u5411\u56fe undirected graph\u548c\u6709\u5411\u56fe directed graph\u3002<\/span><\/p>\n


<\/p>\n

\u4e00\u4e2a\u56fe\u7684\u6570\u636e\u7ed3\u6784\u7531\u4e00\u7ec4\u6709\u9650\u7684\uff08\u4e5f\u53ef\u80fd\u662f\u53ef\u53d8\u7684\uff09\u9876\u70b9 vertices\uff08\u4e5f\u79f0\u4e3a\u8282\u70b9 nodes\u6216\u70b9 points\uff09 \uff0c\u4ee5\u53ca\u4e00\u7ec4\u8fb9edges \uff08\u4e5f\u79f0\u4e3a\u94fe\u63a5 links\u6216\u76f4\u7ebf lines\uff09 \u6784\u6210\u3002\u8fd9\u91cc\uff0c\u6bcf\u6761\u8fb9\u90fd\u662f\u7531\u9876\u70b9\u96c6\u5408\u4e2d\u7684\u4e24\u4e2a\u5f7c\u6b64\u4e0d\u540c\u7684\u9876\u70b9\u6784\u6210\uff1b\u6362\u53e5\u8bdd\u8bf4\uff0c\u6bcf\u6761\u8fb9\u90fd\u662f\u7531\u56fe\u4e2d\u7684\u4e00\u5bf9\u9876\u70b9\u6784\u6210\u7684\u3002\u6839\u636e\u6784\u6210\u6bcf\u6761\u8fb9\u7684\u9876\u70b9\u5bf9\u662f\u6709\u5e8f\u5bf9\u8fd8\u662f\u65e0\u5e8f\u5bf9\uff0c\u56fe\u53ef\u4ee5\u5206\u6210\u6709\u5411\u56fe directed graph \u548c\u65e0\u5411\u56fe undirected graph\uff1b\u5bf9\u4e8e\u65e0\u5411\u56fe\u800c\u8a00\uff0c\u6784\u6210\u5176\u6bcf\u6761\u8fb9\u7684\u9876\u70b9\u5bf9\u662f\u65e0\u5e8f\u7684\uff0c\u800c\u6709\u5411\u56fe\u4e2d\uff0c\u6784\u6210\u6bcf\u6761\u8fb9\u7684\u9876\u70b9\u5bf9\u662f\u6709\u5e8f\u7684\uff0c\u8fd9\u6837\u6211\u4eec\u4e5f\u79f0\u6709\u5411\u56fe\u4e2d\u7684\u8fb9\u4e3a\u7bad\u5934arrows\u3002\u5728\u56fe\u6570\u636e\u7ed3\u6784\u4e2d\uff0c\u9876\u70b9\u53ef\u4ee5\u662f\u4ee5\u4e0b\u4e09\u79cd\u7c7b\u578b\u7684\u6570\u636e\uff1a1. \u56fe\u7ed3\u6784\u7684\u4e00\u90e8\u5206\uff1b2. \u7531\u6574\u578b\u6570\u7d22\u5f15\u8868\u793a\u7684\u5916\u90e8\u5b9e\u4f53\u5bf9\u8c61\uff1b3. \u7531\u5f15\u7528references\u8868\u793a\u7684\u5916\u90e8\u5b9e\u4f53\u5bf9\u8c61\u3002<\/span><\/p>\n

<\/p>\n

\u4e00\u4e2a\u6709\u4e09\u4e2a\u9876\u70b9\uff08\u84dd\u8272\u5706\u5708\uff09\u548c\u4e09\u6761\u8fb9\uff08\u9ed1\u8272\u7bad\u5934\uff09\u7684\u6709\u5411\u56fe\u3002<\/span><\/section>\n

<\/section>\n
\u56fe\u7684\u6570\u636e\u7ed3\u6784\u8fd8\u53ef\u4ee5\u4e3a\u6bcf\u6761\u8fb9\u5173\u8054\u67d0\u4e2a\u8fb9\u503c edge value\uff0c\u5982\u7b26\u53f7\u6807\u7b7e\u6216\u6570\u503c\u5c5e\u6027\uff08\u6210\u672c\u3001\u5bb9\u91cf\u3001\u957f\u5ea6\u7b49\uff09\u3002  <\/span><\/section>\n


<\/p>\n


<\/p>\n


<\/p>\n

\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

<\/section>\n

<\/section>\n
\n
<\/svg><\/section>\n<\/section>\n<\/section>\n
\n

2. \u64cd\u4f5c\u65b9\u5f0f<\/strong><\/strong><\/p>\n<\/section>\n

\n

<\/section>\n

<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n


<\/p>\n

\u56fe\u5f62 G \u7684\u6570\u636e\u7ed3\u6784\u63d0\u4f9b\u7684\u57fa\u672c\u64cd\u4f5c\u901a\u5e38\u5305\u62ec\uff1a<\/span><\/p>\n


<\/p>\n

\n
    \n
  • <\/li>\n<\/ul>\n
    adjacent (G, x, y)\uff1a\u68c0\u9a8c\u9876\u70b9 x \u5230\u9876\u70b9 y \u662f\u5426\u5b58\u5728\u8fb9\uff1b<\/span><\/code><\/pre>\n<\/section>\n
    \n
      \n
    • <\/li>\n<\/ul>\n
      neighbors<\/span> (G, x)\uff1a\u5217\u51fa\u6240\u6709\u6ee1\u8db3\u8fd9\u6837\u6761\u4ef6\u7684\u9876\u70b9y\uff1a\u7ed9\u5b9a\u7684\u9876\u70b9x\u6709\u4e00\u6761\u8fb9\u8fde\u5230\u4e86\u9876\u70b9y;<\/span><\/code><\/pre>\n<\/section>\n
      \n
        \n
      • <\/li>\n<\/ul>\n
        add_vertex (G, x)\uff1a\u6dfb\u52a0\u65b0\u9876\u70b9 x \uff1b<\/span><\/code><\/pre>\n<\/section>\n
        \n
          \n
        • <\/li>\n<\/ul>\n
          remove_vertex (G, x)\uff1a\u5220\u9664\u5df2\u6709\u9876\u70b9 x \uff1b<\/span><\/code><\/pre>\n<\/section>\n
          \n
            \n
          • <\/li>\n<\/ul>\n
            add_edge (G, x, y)\uff1a\u6dfb\u52a0\u4e00\u6761\u8fde\u63a5\u9876\u70b9 x \u548c\u9876\u70b9 y \u7684\u8fb9\uff1b<\/span><\/code><\/pre>\n<\/section>\n
            \n
              \n
            • <\/li>\n<\/ul>\n
              remove_edge (G, x, y)\uff1a\u5220\u9664\u8fde\u63a5\u9876\u70b9 x \u548c\u9876\u70b9 y \u7684\u8fb9\uff1b<\/span><\/code><\/pre>\n<\/section>\n
              \n
                \n
              • <\/li>\n<\/ul>\n
                get_vertex_value<\/span> (G, x)\uff1a\u8fd4\u56de\u4e0e\u9876\u70b9 x \u5173\u8054\u503c\uff1b<\/span><\/code><\/pre>\n<\/section>\n
                \n
                  \n
                • <\/li>\n<\/ul>\n
                  set_vertex_value<\/span> (G, x, v)\uff1a\u5c06\u9876\u70b9 x \u7684\u5173\u8054\u503c\u8bbe\u7f6e\u4e3a v \u3002<\/span><\/code><\/pre>\n<\/section>\n

                  <\/p>\n
                  \u5c06\u503c\u5173\u8054\u5230\u8fb9\u7684\u7ed3\u6784\u901a\u5e38\u8fd8\u63d0\u4f9b\uff1a<\/span><\/p>\n

                  <\/p>\n
                  \n
                    \n
                  • <\/li>\n<\/ul>\n
                    get_edge_value (G, x, y): returns the value<\/span> associated with the edge<\/span> (x, y<\/span>)<\/span>;<\/span><\/code><\/pre>\n<\/section>\n
                    \n
                      \n
                    • <\/li>\n<\/ul>\n
                      set_edge_value (G, x, y, v): sets the value associated with the edge (x, y) to v.<\/span><\/code><\/pre>\n<\/section>\n

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

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

                      <\/section>\n

                      <\/section>\n
                      \n
                      <\/svg><\/section>\n<\/section>\n<\/section>\n
                      \n
                      3.\u8868\u793a\u65b9\u6cd5<\/strong><\/strong><\/p>\n<\/section>\n
                      \n

                      <\/section>\n

                      <\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n

                      <\/p>\n
                      \u5b9e\u9645\u5e94\u7528\u4e2d\uff0c\u7528\u4ee5\u8868\u793a\u56fe\u7684\u5404\u7c7b\u6570\u636e\u7ed3\u6784\uff1a<\/span><\/p>\n

                      <\/p>\n
                        \n
                      • \n
                        \u90bb\u63a5\u8868 Adjacency list<\/span><\/p>\n<\/li>\n<\/ul>\n
                        \u9876\u70b9\u88ab\u5b58\u50a8\u4e3a\u8bb0\u5f55\u6216\u5bf9\u8c61\uff0c\u5e76\u4e14\u6bcf\u4e2a\u9876\u70b9\u5b58\u50a8\u4e00\u4e2a\u76f8\u90bb\u9876\u70b9\u5217\u8868\u3002 \u8fd9\u79cd\u6570\u636e\u7ed3\u6784\u5141\u8bb8\u5728\u9876\u70b9\u4e0a\u5b58\u50a8\u989d\u5916\u7684\u6570\u636e\u3002\u5f53\u8fb9\u4e5f\u88ab\u5b58\u50a8\u4e3a\u5bf9\u8c61\u65f6\uff0c\u8fd9\u4e9b\u5bf9\u8c61\u5c31\u53ef\u4ee5\u4f5c\u4e3a\u989d\u5916\u7684\u6570\u636e\u5b58\u50a8\u5728\u9876\u70b9\u4e0a\uff1b\u8fd9\u4e2a\u65f6\u5019\u5728\u6bcf\u4e2a\u9876\u70b9\u7684\u6570\u636e\u7ed3\u6784\u4e2d\uff0c\u5b58\u50a8\u4e86\u6240\u6709\u548c\u8fd9\u4e2a\u9876\u70b9\u76f8\u90bb\u7684\u8fb9\uff0c\u5e76\u4e14\u5176\u4e2d\u6bcf\u6761\u8fb9\u5b58\u50a8\u4e86\u5b83\u6240\u8fde\u63a5\u7684\u4e24\u4e2a\u9876\u70b9\u3002<\/span><\/p>\n