問題タブ [undirected-graph]

mathworks で見つかった次の方法で、MATLAB でグラフをプロットしようとしました。

しかし、それは私を返します

タイプ 'double' の入力引数に対して未定義の関数 'graph'。

基本的に、この無向グラフをプロットして、そのパス マトリックスを見つけたいと考えています。パス行列は、行の数が考慮中のソース ノードからデマンド ノードへのパスの数に等しく、列の数がエッジの数に等しい行列です。この行列は、エントリとして 1 を持つ 0-1 の行列です。エッジがデマンド ノードへのパスに存在する場合、存在しない場合はそのエントリとして 0 を返します。たとえば、ネットワークに 3 つのエッジ A、B、および C があり、ソース ノードからデマンド ノードへの可能なパスは AB および AC です。次に、パス行列は次のように表されます。

最初の列はAを表し、最初の行は最初の可能なパスを表します。無向グラフをプロットしてそのパス行列を見つけるにはどうすればよいですか?

単位辺の長さを持つ無向グラフで最短のサイクルの長さを見つけることになっているアルゴリズムが与えられています。反例を示して、アルゴリズムが常に機能するとは限らないことを示さなければなりません。このアルゴリズムが常に機能するとは限らないことを示す例を考え出すのに問題があります。

アルゴリズム：

• 各頂点のレベルを追跡しながら、深さ優先検索を実行します。
• バック エッジが検出されるたびに、サイクルの長さを計算し、それが以前に見た最短のものよりも小さい場合は保存します。

任意の提案/ヘルプをいただければ幸いです

まず、お読みいただき、ご返信いただきありがとうございます。

次に、質問:
対称隣接行列 から加重無向グラフを作成しようとしていますA。ここで、ij番目の要素はノードiとjの間のエッジの重みです。

私はすぐにこれを名前エラーにします：

これで、次の方法で有向グラフを無向グラフに変換できます。

しかし、私は問題が何であるか疑問に思っています。

これは古い中間試験の問題の例です。

G = (V, E) を連結無向グラフとし、辺には正の整数の辺の重みが関連付けられており、頂点 s ∈ V がソースです。各頂点 t ∈ V について、s から t への非減少パス (そのようなパスがない場合は ∞) の最小の最後のエッジの重みを報告するアルゴリズムを提供します。パス v1、v2、. . . i = 1, 2, ...r−2 に対して w(v_i, v_i+1) ≤ w(v_i+1, v_i+2) の場合、vr は非減少です。

問題は、開始頂点を持つグラフが与えられ、最短パスの長さを見つけることができ、パスを下るにつれてエッジの重みが増加するアルゴリズムを考え出すことを問題が望んでいると考えて正しいですか?到達できる頂点？

私の質問は主にアルゴリズム関連であり、特定のプログラミング言語に固有のものではありません

各内部リストが 2 つのノードと番号付きエッジを表すリストのリストで表されるグラフがあると仮定すると、次の 12 個の関数のみを使用して再帰的 BFS (幅優先検索) 関数を実装することは可能ですか? 私たちの bfs 再帰関数は 5 つの引数を取ることになっています:

• 検索するグラフ
• 見つける要素
• 検索キュー
• 訪問したノードのリスト
• 現在見ている要素

グラフの例:

以下の関数では、グラフ内の個々のリストをグラフ要素と呼んでいます

関数は次のとおりです。

これは、再帰的な BFS 関数を実装した方法です。

• 再帰呼び出しには、実際には 2 つの基本ケースがあります。キューが空の場合 (つまり、検索していた要素に到達できなかったことを意味します)、およびキューからポップされる要素が検索していた要素である場合です。
• 各呼び出しで、現在のノードからパスを検索する関数を定義し (移動できるノードを検索するため)、これらのノードをキューにプッシュします。
• 次に、現在のノードを訪問済みリストにプッシュし、繰り返します

私の問題は、上記の関数リストにない 2 つの関数 (パスを検索する関数と、それらのパスのターゲット ノードを検索キューにプッシュする関数) を定義したことです。

これらの関数のみを使用して再帰的な BFS を実行できるかどうか疑問に思っていましたか?

PS: グラフのリストは無向グラフを表すはずですが、それが問題をどのように変えるかはわかりません

どんな種類の助けも心から感謝しています...

私は以下によって与えられる無向グラフを持っています:

そして、これを行列 N に変換する必要があります。

それを行う最も速い方法は何ですか？

注意: グラフは文字列の numpy 配列として格納されます。

期待される出力:

ありがとう

無向グラフで実行する DFS アルゴリズムを作成する必要がある大学の演習があります。また、すべてのノードの値を合計して、ノードがアクセスされた順序を表示するプログラムを作成する必要があります。

与えられた構造は次のとおりです。

この演習を開始する方法がわからない

n 個の頂点を持つ無向グラフの場合、接続するために必要なエッジの最小数は n - 1 であることを知っています。しかし、グラフに n 個の頂点と n - 1 個のエッジがある場合、それは常に接続されていますか?