強連結成分分解

質問

連接行列のみ与えられたときに、強連結成分を返すアルゴリズムを作成したいのですが。。
私自身はC++のみ少し理解できる程度でしかないのです(；口；)
しかし、いろいろ調べてみても、グラフについてはほとんどC言語で書かれているものが多く、理解できません。
もし、よろしければ、C++でどのように表現していったらいいか指導をお願いします。
もし、無知識なトンチンカンな質問だったりしたら、ごめんなさい。
プログラム初心者なので、どこから考えていいかもわからなくて…。
おねがいします。

回答No.1

process9 · ベストアンサー

process9です。
ちょっと微妙な話ですね～。学生さんでしょうか？
＞連接行列のみ与えられたときに、強連結成分を返すアルゴリズムを作成したいのですが
新規のアルゴリズムを作るのが目的ですか？
であれば、研究レベルの話になるので、ここで質問しても無理かな～と。

ということで以下は、
既存のアルゴリズムをもって、プログラム（実装）したい。
という意味として考えますね。

C++は理解しているけど、Cは理解していないと思っていいですか？
あと、机上のプログラムでなく、実際に実行して確認したいんですよね。？

まず、C言語は理解できなくてもアルゴリズムとデータ構造は理解できてますか？
ここが理解できないでいるのなら、C言語を勉強して、
C言語で実際書かれている例などを読んで理解できるようになるしかないでしょうね。

アルゴリズムとデータ構造が分かっているのならば、
連接行列をどう入力表現するかを考え、
強連結成分をどう出力表現するかを考えます。
入力表現は、データ構造に落とし込みやすい方法でかつ入力容易性を考えた
表現方法とするのがコツです。（テキストファイル、データベース、キーボード・マウス入力）
出力表現は、出力デバイスを選択（画面、プリンタなど）し内容（数式にするとか、図で出力するとか）を考えます。
そのあとは、本来ならクラス設計を行うのですが、そこはすっとばして、
　データ構造を表現するクラス（極論、パブリックフィールドだけのクラスでもいい）。
　アルゴリズムを表現したクラス（メソッドだけのクラスでもよい）。
　mainクラス（上記２つのクラスを呼び出して実行するクラス。入出力はここに実装するかな）
の３つのクラスを作ったらどうですか？

お礼

返信遅くなりました。丁寧にありがとうございます。
process9さんの予想通りです。
学生で、C++は少しわかってるつもりでCはまったくわかりません。
なんとか、アルゴリズムとデータ構造は知っているのですが。
強連結成分をどう表現していくかで思考が止まってます。
深さ優先探索をしていこうかと考えているのですが、
その時強連結成分はどう表現されるか考え中です。
さらに、授業とかではCでグラフの表現を勉強したのですが、
それをC++ではどう表現しようか悩んだり…。
ほんとに勉強不足だろうなとは思うのですが、学生の１つの授業の課題なので、あまり時間がかけられず…(；口；)
でも、アウトラインはprocess9さんのおかげでつかめました。
ありがとうございます◎