資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學查詢圖中最大團的最小大小的程式（Python）
假設我們給定一個圖，並要求找出該圖中最大團的最小大小。圖的團是圖的一個子集，其中每對頂點都是相鄰的，即每對頂點之間都存在一條邊。在多項式時間內找到圖中最大的團是不可能的，因此，給定一個小圖的節點數和邊數，我們將不得不找出它裡面的最大團。
因此，如果輸入類似於節點數 = 4，邊數 = 4；則輸出將為 2。
在上圖中，團的最大大小為 2。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式 helper()。這將接收 x，y 作為引數。
- ga := x mod y
- gb := y - ga
- sa := x / y 的商 + 1
- sb := x / y 的商
- 返回 ga * gb * sa * sb + ga *(ga - 1) * sa * sa / 2 + gb * (gb - 1) * sb * sb / 2
- i := 1
- j := 節點數 + 1
- 當 i + 1 < j 時，執行以下操作：
- p := i + floor((j - i) / 2)
- k := helper(節點數, p)
- 如果 k < 邊數，則
- i := p
- 否則，
- j := p
- 返回 j
示例
讓我們看看下面的實現，以便更好地理解：
import math def helper(x, y): ga = x % y gb = y - ga sa = x // y + 1 sb = x // y return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2 def solve(nodes, edges): i = 1 j = nodes + 1 while i + 1 < j: p = i + (j - i) // 2 k = helper(nodes, p) if k < edges: i = p else: j = p return j print(solve(4, 4))
輸入
4,4
輸出
2
更新於：2021年10月6日
瀏覽量：168
廣告