Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonでスターグラフの中心を見つけるプログラム

1からnまでのラベルが付けられたn個のノードを持つ1つの無向スターグラフがあるとします。ご存知のように、スターグラフは、1つの中心ノードがあり、中心ノードを他のすべてのノードに接続する正確にn-1個のエッジがあるグラフです。与えられたスターグラフの中心を見つける必要があります。

したがって、入力が次のような場合

Pythonでスターグラフの中心を見つけるプログラム

3が中央にあるため、出力は3になります。

これを解決するには、次の手順に従います-

  • 見た：=新しいセット

  • グラフの各エッジ（u、v）について、実行します

    • uが表示されている場合は、

      • uを返す

    • vが表示されている場合は、

      • vを返す

    • 見たにuを挿入

    • 見たものにvを挿入

例

理解を深めるために、次の実装を見てみましょう-

def solve(graph):
   seen = set()

   for u,v in graph:
      if u in seen:
         return u
      if v in seen:
         return v
      seen.add(u)
      seen.add(v)

graph = [(1,3),(2,3),(4,3),(5,3),(6,3)]
print(solve(graph))

入力

[(1,3),(2,3),(4,3),(5,3),(6,3)]

出力

3

  1. Pythonでサービスセンターの最適な位置を見つけるためのプログラム

    いくつかの家が配置されている座標点のリストを含む位置のリストがあるとします。 （xc、yc）にサービスセンターを作成し、任意のポイントから（xc、yc）までのユークリッド距離の合計が最小になるようにする場合。したがって、最小距離の合計を見つける必要があります。 したがって、入力がpositions =[（10,11）、（11,10）、（11,12）、（12,11）]のような場合、出力は4.0になります。 これを解決するには、次の手順に従います- numIter：=50 関数total（）を定義します。これにはcx、cy、positionsが必要です 合計：=0.0

  2. Pythonのグラフでクリティカルエッジと疑似クリティカルエッジを見つけるプログラム

    0からn-1までの番号が付けられたn個の頂点を含むグラフが与えられたとします。グラフは無向であり、各エッジには重みがあります。したがって、グラフが与えられた場合、グラフMSTのクリティカルエッジと疑似クリティカルエッジを見つける必要があります。エッジを削除するとMSTの重みが増加する場合、そのエッジはクリティカルエッジと呼ばれます。疑似クリティカルエッジは、すべてではなく、すべてのグラフMSTに表示できるエッジです。グラフを入力として与えられたエッジのインデックスを見つけます。 したがって、入力が次のような場合 頂点の数が5の場合、出力は[[]、[0、1、2、3、4]]になります。指