• ベストアンサー

【アルゴリズム】隣接リストに関する質問です

皆さんこんにちは。当方、情報系の学生です。 こちらの問題の考え方が分からず困っています。 「下図のような無向グラフを頂点Aより深さ優先探索したところ、数字で示したように訪問順序が得られた。このとき、隣接リストはどうなるか示せ。」 自分は、単純に実線でリンクしている頂点のみをピックアップして A→C B→D C→A→F D→B→F ・ ・ ・ のようにリストにすれば良いかと考えたのですが、間違いでしょうか。 お詳しい方、ご助言いただけましたら幸いです。 よろしくお願いいたします。

画像を拡大する

質問者が選んだベストアンサー

  • ベストアンサー
  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

本当にそのような問題だとしたら, 問題がおかしい. 「無向グラフ」と「隣接リスト」との関係が文章に書かれていないので, 「どうなるか」といわれても答えようがない.

nun00nun
質問者

補足

ご回答ありがとうございます。問題を見直してみたところ「無向」とは書かれておらず、「×隣接リスト→○隣接頂点リスト」でした。 ただ、これでも結局グラフとリストの関係性は曖昧ですよね...

  1. カテゴリ
  2. 学問・教育
  3. 応用科学（農工医）
  4. 情報工学

関連するQ&A

  • リストの高速検索アルゴリズム

    1.　Aを使用→Aを登録→（A=1） 2.　Bを使用→Bを登録→（B=1,A=2) 3.　Cを使用→Cを登録→（C=1,B=2,A=3) 4.　Dを使用→Dを登録→（D=1,C=2,B=3,A=4) 5.　Bを使用→順序のみ更新→(B=1,D=2,C=3,A=4) 6. 一番古いのを削除　→Aを削除→(B=1,D=2,C=3) 上記のような１０００個のデータ(A,B…)を使用したら、使用履歴に登録していくプログラムを作るとして 高速に検索するには、どうすればよろしいでしょうか。 検索したいのは以下の２つです。 ・一番古いデータの検索（削除するため） ・データが登録有無の検索 汎用的な手法があればその名称をお教え願えないでしょうか。ちなみに二分木はちょっと違うような気がしました。

  • 巨大数生成アルゴリズム

    次のようなアルゴリズムで巨大数を生成していくのは効率がいいと言えますか おそらく、いえると思いますが、これを論理的に示すにはどうしたらよいでしょうか？ 1. F(a,b,0)=a+b , F(a,0,c)=a+c 　　F(a,b,c)=F(a,b-1,F(a,b,c-1)) 2. F(a,b,c,0)=F(a,b,c) 　　F(a,b,0,d)=F(a,b,d) 　　F(a,b,c,d)=F(a,b,c-1,F(a,b,c,d-1)) 3. F(a,b,c,d,0)=F(a,b,c,d) 　　F(a,b,c,0,e)=F(a,b,c,e) 　　F(a,b,c,d,e)=F(a,b,c,d-1,F(a,b,c,d,e-1)) ・・・ おそろらく添え字か5つか6つ位でグラハム数オーダーではないかと思ったりしますが。。 いかがなものでしょうか？

  • メーリングリストって

    メーリングリストについてお聞きしたいのですが、 質問１．メーリングリストって送られてくる人以外のアドレスも表示されるのですか。要するにAさんからB,C,D,E,Fに送るとBさんはC,D,E,Fのアドレスが表示されているのですか。BCCそれともCCで送られてくるのでしょうか。 質問２．同じくCさんからDさんに送ることはできるのですか、できるとしたらAさんはそれを見たり参加したりできるのですか？

  • 隣接しないパーティッションの結合

    現在、パーティションが以下のようにあります。 A｜B｜C｜D A：リカバリデータ収納領域（１８GBのうち９GB使用） B：Windows７起動情報格納（サイズ１００MB） C:システムドライブ D:データドライブ 今、A（1８GB）を９GBまで圧縮してEを作ります。 A｜E｜B｜C｜D EをDと結合してFを作り、最終的にこのようにしたいのです。できますか？ A｜B｜C｜F（DとE結合） 隣接するパーティションのリサイズなどは簡単にできるんですが、 この場合、パーティション位置を移動することが必要になります。

  • エクセルでリストを使って特定の文字列を数える

    エクセル2003を使っています。 シート３に A B C というリストAと D E F というリストB そして A B C D E F と一緒になっているリストCを作りました。 そしてシート１にリストCを使ってこのような表を作りました。 A D A C B D F E C B A B と選択したとします。 そのとき、左側にリストAの中に含まれている文字列を数える方法はないでしょうか。 使っているのは、 Windows XP Professional SP2 Microsoft Office Excel 2003 SP3 です。

  • リストファイルと一致する行の抽出

    ２つのファイルがありまして、list.txtでリストアップしたキーワードに一致するinput.txt一行目の行を抽出したいです. fgrep -f list.txt input.txt ではout of memoryで行えません。 他に何かいい方法がありませんでしょうか？ あれば教えていただきたいです。 list.txtはsortせずにこの順序を維持したいです。 <list.txt> d c a h g x k . . <input.txt> a 12 43 .. b 29 44 .. c 12 66 .. c 33 55 .. d 44 55 ..

  • 乗積 Π のアルゴリズム

    　はじめまして。 　質問内容が表題と多少ズレる事をご承知下さい。 　アルゴリズムを教えて頂きたいと思っています。 　＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ 　Π(2x-1) ,x=1～m 　上式においてm=3とすると、総数は15となります。 　今、A～Fまで6つのアルファベットがあります。 　このうち2つをペアにしてグループを作ります。 　上式により、グループ総数は15となります。 　ペアの組み方は以下のようになります。 　＜例＞ 　(1) A-B、 C-D、 E-F 　(2) A-B、 C-E、 D-F 　(3) A-B、 C-F、 D-E 　　・ 　　・ 　　・ 　(14) A-F、 B-D、 C-E 　(15) A-F、 B-E、 C-D 　＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ 　このような取り方をプログラムしようと思うのですが 　どこから手をつけてよいかわかりません。 　是非アドバイスをお願いします。 　 　

  • リストからの選択

    エクセルにて文字を入れる際にデータの入力規制を用いてリストから選択するようにしているのですが、そのリストを可変的にしたいのですが可能でしょうか？ A1のセル：　A,B,C　から選択 A2のセル：　A1が"A"の場合D,E,F 　　　　　　A1が"B"の場合D,G,H 　　　　　　A1が"C"の場合E,I,J の選択させたいです。

  • 隣接行列の表示

    MATLAB初心者です。 隣接行列をグラフにしたいのですが、 gplotで描こうとするとgplot(A,B)のBの部分を 入れないといけません。 今１０００＊１０００の隣接行列のデータはあるのです(Aはできている)がこれらを自動でうまく配置して表示するにはどうしたらよいのでしょうか？

  • 隣接行列プログラム

    隣接行列を使ったグラフ探索のプログラムを作りたいのですが。。 手も足もでません。どなたか助けていただけないでしょうか？？ まずstate.txt 1 2 3 0 といったフォーマットに従った状態空間が記述された テキストファイルを読み込んで、隣接行列を動的に作成し、 さらにその状態空間をfwrite()を用いてバイナリ形式のファイルにする。 実行時のコマンドラインは次の書式に従う。 > ./MakeGraph テキストファイル(読み込み元）　状態空間(書き込み元）　状態数 [Enter] もうひとつは、上で作成した状態空間ファイル（バイナリ形式）をmalloc(),fread()を用いて メモリ上に復元し、経路探索を行う。 ただし、オプション指定で縦型探索と横型探索を切り替えられるようにすること。 実行時のコマンドラインは次の書式に従う。 > ./Search [-bd] 状態空間ファイル　 状態数 　開始状態 　終了状態 [Enter] ちなみに、 使用例 > ./MakeGraph state.txt state.bin 4 [Enter] > ./Search -d state.bin 4 1 0 [Enter] > ./Search -b state.bin 4 3 3 [Enter] > ./Search -bd state.bin 4 2 0 [Enter] 結果例 1-0 : d : 0 <- 3 <- 1 3-3 : b : 3 <- 1 <- 0 <- 3 2-0 : b : Not Found... 2-0 : d : Not Found... これらを作るうえでのヒントのようなものもあるのですが、さっぱりで。。 状態空間をファイルから取り込むため、隣接行列で表現した状態空間のサイズは可変、 （たとえば、状態数５ならば、２５個）である。したがって、メモリは動的に確保する必要がある。 また探索時に容易に扱えるようにするため、隣接行列は２次元配列であることが望ましい。 しかし、２次元の動的確保は難易度が高いので、１次元配列の動的確保を応用することで考える。 １次元配列を状態数２個確保し、２点の座標を指定することで、要求する要素へ アクセスできるマクロCoordinates(x, y, size)を用意する。 このマクロを利用すれば、１次元配列で確保したデータを２次元として扱うことができる。 ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ MakeGraph.cとSearch.cは次にあります。 ここにはのせきれなかったので。。 お手数おかけします。 http://mugen.cc.osaka-kyoiku.ac.jp/pg/ あとstate.txt のフォーマットは次のようになっています。 これはデータ構造などででてくる有向グラフを隣接行列で示した場合、 スタート地点の状態０から状態１に（０→１） 状態１から状態２と、ゴールの状態３に（１→２、１→３） ゴールの状態３からスタート地点の状態０に（３→０） となっていた場合に、状態０～３までのリンク先をあらわしたものです。 単に、机上において、隣接行列で表現すると 　　０　１　２　３ ０　０　１　０　０ １　０　０　１　１ ２　０　０　０　０ ３　１　０　０　０ となります。（線がはいっていないのでややこしいかもしれませんが。。） これと同じ意味で、 1 （状態０のリンク先で、１の直後に￥ｎ） 2 3 （状態１のリンク先で、２と３の間に空白、さらに３の後ろに￥ｎ） 　　（状態２のリンク先はなにもないので、まっしろ） 0 （状態３のリンク先） となっています。こういう説明で伝わっているかわかりませんが、 よろしくおねがいします！！

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する