強連結判定を行うプログラムについて（C言語）

隣接行列の形で与えられたグラフが強連結であるか否かの判定を行うプログラムを教えて下さい。言語はＣ言語でお願いします。

質問者からの補足コメント

• ある頂点から行って戻ってこれるのが強連結だというのは分かったのですが、それをプログラムにするのが分かりません…プログラムが苦手で、頂点のアドレスをたどっていくかんじかな（間違っていたらすみません）くらいしか分かりません。
  こんな感じですがよろしくお願いします。

    補足日時：2018/12/04 17:01

No.1 回答者： usa3usa 回答日時： 2018/12/04 13:37

＞プログラムを教えて下さい

グラフが強連結であるとは、どういうことか？
その判定をプログラムで記述するとどうなるのか？
どこまでできていて、どこがわからないのでしょうか？

No.2 回答者： usa3usa 回答日時： 2018/12/04 22:34

＞ある頂点から行って戻ってこれるのが強連結

「頂点のアドレスをたどっていって戻ってこれる道」
が全ての頂点で見つけられるかをプログラミングすればいいだけでは？

メインは
for(i=0; i<n; i++)
　if( findpath(i) ==0) return 0;　// 強連結ではない
return 1; // 強連結
でしょうか。

あとは、頂点 i を起点に戻って来れる道が見つかれば１，見つからなければ０を返す関数findpath(int i) を作れば良いだけでしょう。

No.3 回答者： usa3usa 回答日時： 2018/12/05 10:24

回答の順番が逆になってしまってごめんなさい。

＞ある頂点から行って戻ってこれるのが強連結だというのは分かったのですが、
まずは数学の勉強を先にすべきでしょうかね。

https://ja.wikipedia.org/wiki/連結グラフ

強連結
有向グラフが強連結であるとは、グラフ上の任意の2点間に有向路が存在することである。

メインは
for(i=0; i<n; i++)
　for(j=0; j<n; j++)
　　if( findpath(i,j) ==0) return 0;　// 強連結ではない
return 1; // 強連結
でしょうか。

あとは、頂点 i を起点に頂点jに至る道が見つかれば１，見つからなければ０を返す関数findpath(int i, int j) を作れば良いだけでしょう。

この回答へのお礼

ありがとうございます

お礼日時：2018/12/05 15:42