一種子圖匹配裝置，用于在大規模圖中查找出與帶環圖匹配的子圖，包括：生成樹模塊、匹配模塊、判斷模塊以及集合模塊。生成樹模塊根據最小生成樹算法找到帶環圖的生成樹；匹配模塊自底向上對數據圖進行生成樹匹配，尋找與生成樹匹配的樹Li（i>=1）；判斷模塊判斷所述樹Li的評分函數值與缺失邊數之和是否大于等于預設值，若是，則判斷模塊判斷樹Li能否擴展為帶環圖；集合模塊還在所述樹Li的評分函數值與缺失邊數之和大于等于預設值時將所述集合V中前固定值個匹配圖輸出。

1.一種子圖匹配裝置，用于在大規模圖中查找出與帶環圖匹配的
子圖，包括：
生成樹模塊，用于根據最小生成樹算法找到所述帶環圖的生成樹；
匹配模塊，用于自底向上對數據圖進行生成樹匹配，尋找與生成樹
匹配的樹Li；
判斷模塊，用于判斷所述樹Li的評分函數值與缺失邊數之和是否大
于等于預設值，其中，所述判斷模塊還用于在所述樹Li的評分函數值與
缺失邊數之和小于預設值時判斷所述樹Li能否擴展為帶環圖；
集合模塊，用于在樹Li能擴展為帶環圖時將所述樹Li擴展為匹配
圖，并存入集合V中，其中，所述集合模塊還用于將所述集合V中的匹
配圖按照權重從小到大來排序，所述判斷模塊還用于判斷集合V中匹配
圖的個數是否大于等于固定值，且在集合V中匹配圖的個數大于等于固
定值時將所述預設值設為第固定值個匹配圖的權重；
其中，所述集合模塊還用于在所述樹Li的評分函數值與缺失邊數之
和大于等于預設值時將所述集合V中前固定值個匹配圖輸出。
2.如權利要求1所述的子圖匹配裝置，其特征在于，所述集合模
塊在所述樹Li不能擴展為帶環圖時丟棄樹Li。
3.如權利要求1所述的子圖匹配裝置，其特征在于，評分函數為：
s c o r e ( M Q ) = Σ ( X ; Y ) ∈ E ( Q ) C ( X ; Y ) d i s t ( u ; v ) ]]>
其中u，v∈M_Q，M_Q是查詢圖Q在數據圖G_D中的匹配圖，
(X；Y)＝(λ^-1(u)；λ^-1(v))為查詢圖Q中的邊，C(X；Y)為與查詢邊(X；Y)關
聯的系數，dist(u；v)表示頂點u和v的最短路徑的距離值。
4.如權利要求1所述的子圖匹配裝置，其特征在于，所述匹配模
塊包括：
分解子模塊，用于將所述生成樹自頂向下分解為只有邊的子樹；
判斷子模塊，用于判斷子樹生長后形成的樹是否為I型子樹，所述
I型子樹為葉子節點無兄弟的樹；
尋找子模塊，用于在所述子樹生長后形成的樹為I型子樹時在所述
數據圖中尋找所述子樹的根結點到葉子節點的最優結果，放入pTable中，
其中，所述尋找子模塊還用于將所述pTable中權重值最小的數據放入
sTable中，并刪除pTable中權重值最小的數據，所述判斷子模塊還用于
判斷所述子樹是否為最后一棵子樹；
輸出子模塊，用于在所述子樹是最后一棵子樹時將所述sTable的內
容作為所述生成樹的一個匹配的樹Li。
5.如權利要求4所述的子圖匹配裝置，其特征在于，所述尋找子
模塊還用于在所述子樹生長后形成的樹不為I型子樹時在所述數據圖中
尋找所述子樹的兄弟節點之間的最優結果，放入pTable中。
6.如權利要求4所述的子圖匹配裝置，其特征在于，所述分解子
模塊還用于在所述子樹不是最后一棵子樹時將所述子樹作為葉子節點。
7.一種子圖匹配的方法，用于在大規模圖中查找出與帶環圖匹配
的子圖，其特征在于，所述方法包括以下步驟：
根據最小生成樹算法找到所述帶環圖的生成樹；
自底向上對數據圖進行生成樹匹配，尋找與生成樹匹配的樹Li；
判斷所述樹Li的評分函數值與缺失邊數之和是否大于等于預設值；
若所述樹Li的評分函數值與缺失邊數之和小于預設值，則判斷所述
樹Li能否擴展為帶環圖；
若所述樹Li能擴展為帶環圖，則將所述樹Li擴展為匹配圖，并存
入集合V中；
將所述集合V中的匹配圖按照權重從小到大來排序；
判斷所述集合V中匹配圖的個數是否大于等于固定值；
若所述集合V中匹配圖的個數大于等于固定值，則將所述預設值設
為第固定值個匹配圖的權重，其中，若所述樹Li的評分函數值與缺失邊
數之和大于等于預設值，則將所述集合V中前固定值個匹配圖輸出。
8.如權利要求7所述的子圖匹配的方法，其特征在于，還包括以
下步驟：
若所述樹Li不能擴展為帶環圖時，則丟棄樹Li。
9.如權利要求7所述的子圖匹配的方法，其特征在于，所述評分
函數為：
s c o r e ( M Q ) = Σ ( X ; Y ) ∈ E ( Q ) C ( X ; Y ) d i s t ( u ; v ) ]]>
其中u，v∈M_Q，M_Q是查詢圖Q在數據圖G_D中的匹配圖，
(X；Y)＝(λ^-1(u)；λ^-1(v))為查詢圖Q中的邊，C(X；Y)為與查詢邊(X；Y)關
聯的系數，dist(u；v)表示頂點u和v的最短路徑的距離值。
10.如權利要求7所述的子圖匹配的方法，其特征在于，步驟“自底
向上對數據圖進行生成樹匹配，尋找與生成樹匹配的樹Li”包括以下步
驟：
將所述生成樹自頂向下分解為只有邊的子樹；
判斷子樹生長后形成的樹是否為I型子樹，所述I型子樹為葉子節
點無兄弟的樹；
若所述子樹生長后形成的樹為I型子樹，則在所述數據圖中尋找所
述子樹的根結點到葉子節點的最優結果，放入pTable中；
將所述pTable中權重值最小的數據放入sTable中，并刪除pTable
中權重值最小的數據；
判斷所述子樹是否為最后一棵子樹；
若所述子樹為最后一棵子樹時將所述sTable的內容作為所述生成樹
的一個匹配的樹Li。
11.如權利要求10所述的子圖匹配的方法，其特征在于，步驟“自
底向上對數據圖進行生成樹匹配，尋找與生成樹匹配的樹Li”還包括以
下步驟：
若所述子樹生長后形成的樹不為I型子樹，則在所述數據圖中尋找
所述子樹的兄弟節點之間的最優結果，放入pTable中。
12.如權利要求10所述的子圖匹配的方法，其特征在于，步驟“自
底向上對數據圖進行生成樹匹配，尋找與生成樹匹配的樹Li”還包括以
下步驟：
若所述子樹不是最后一棵子樹，則將所述子樹作為葉子節點。