問題タブ [cyclic-graph]

正規表現から NFA へのコンバーターを実装しようとしています。ほとんどのコードを記述しましたが、状態 (ノード) とエッジの表現を考慮して、サイクルを使用してグラフを作成する方法を見つけるのに苦労しています。

私のグラフ表現は次のとおりです。

正規表現を NFA に変換する私の関数は、基本的に正規表現のタイプのパターン マッチであり、正規表現のタイプと「最終状態」(NFA のすべての発信エッジが移動する場所) を取り込み、「開始状態」を返します。その正規表現の（部分的に構築された）NFAの。NFA フラグメントは、発信エッジ リストで構築された State を返すことによって構築されます。各エッジの終了状態は、再帰呼び出しによって構築されます。

ほとんどのコードは簡単ですが、グラフでサイクルを必要とする Kleene スターと + の NFA を構築するのに苦労しています。私の表現を考えると、次のような結果になります。

この時点で s が未定義であるため、明らかにこれはコンパイルされません。ただし、型チェッカーはそのような再帰的に定義された型を (正当に) 拒否するため、"rec" キーワードも追加できません。そしてまた...）。基本的に、ここには鶏が先か卵が先かという問題があります。完全に構築される前に、「状態」参照を別の状態に渡す必要があります。再帰呼び出しで。

参照/可変レコードを使用せずにこれを行う方法はありますか? これを可能な限り機能的に保ちたいのですが、状況を考えるとこれを回避する方法がわかりません...誰か提案がありますか?

巡回有向グラフがあり、任意の 2 つのノード間で共通の子孫のリストを作成するアルゴリズム (できれば最適なもの) があるかどうか疑問に思っていましたか? Lowest Common Ancestor (LCA) とはほぼ反対のことです。

私はプロローグの完全な初心者です。パスがエッジ間に存在するかどうかを確認する必要がある問題を見つけようとしています。巡回用の非巡回グラフ コードが完成しました。私のコードは無限ループに陥ります。

新しい述語 new_path(Start,End,path) を定義して、このケースを処理する必要があります。これにより、無限ループが解消されます。続行する方法を教えてください。

私はプロローグで書いています：

巡回グラフも処理しているため、同じノードから同じノードをトラバースしようとすると、不規則な出力が得られます。

例:path(x,x,P). 予想される出力は次のようになります。

しかし、私は出力を得ています:

どうすればこの不要なケースを取り除くことができますか。ありがとう

ネストされたグループに関連する問題に取り組んでいます。グループがメンバーであるすべてのグループと、そのメンバーであるすべてのグループを特定する必要があります。直接の親と子だけでなく、上下の階層の全員。

私がこれまで行ってきたことは、上から下へのトラバース ロジックです。つまり、スタックを使用してアクセスされていないメモを格納し、ハッシュセットを使用してアクセスされたメモを格納する DFS です。これは、結果のグラフに循環がある場合に、無限再帰に陥らないようにするためです。

この部分は機能します。私が問題を抱えているのは、トラバーサル中に各グループの親と子をどのように保存するかを考え出すことです。グループには他のグループまたはユーザーをメンバーとして含めることができ、重複した情報を保存したくないことに注意してください。

出力は、グループが次のようなグループのリストのようになります。

頂点の数が 5 を超える循環グラフの場合、各ノードで BFS を実行し、それらの長さから最大値を選択すると機能しなくなります。

例えば：

各頂点に 1 から 6 まで循環的に番号を付けます。

ここで、BFS を使用: -ノード 1 から:

1. ノード 1 を取り出し、キューに 2 と 6 を追加し、長さを 1 増やします
2. ノード 2 を取り出し、キューに 3 を追加し、長さを 1 増やします
3. ノード 6 を取り出し、キューに 5 を追加し、長さを 1 増やします
4. ノード 3 を取り出し、キューに 4 を追加し、長さを 1 増やします
5. ノード5を取り出し、何もしません
6. ノード 4 を取り出し、何もしません

長さはすでに 4 に等しく、直径よりも大きくなっています。

このようなグラフからすべてのサイクルを削除するにはどうすればよいですか? すべての辺の長さは 1 で、すべての辺は垂直または水平のいずれかです。グラフがつながりました。

グラフにサイクルが含まれないようにするために削除する必要があるエッジの最小数を計算したいと考えています。

サンプル コード (できれば C++、C、または Java) を含めていただけると大変助かります。

更新:どうやら、頂点とエッジの数を見つける必要があります。私が抱えている問題は、（下、左、上、下、左、左、上、下）のような一連の指示を与えます。座標平面の (0, 0) から開始し、指定された方向に 1 単位移動します。これでグラフが作成されます。この一連の命令から頂点とエッジの数を取得するにはどうすればよいですか?

nノード間で特定の加重巡回グラフをエッジの合計が最小の非巡回グラフに変換するにはどうすればよいですか? 出力グラフでは、各ノードには D を超える入力エッジがないという追加情報があります。重みは正です