最長経路のプログラム

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら
返信
FISH

最長経路のプログラム

#1

投稿記事 by FISH » 8年前

初めて投稿します。FISHと申します。グラフの最短経路ではなく最長経路を解こうとしています。
あまりcの知識はないのでご教授いただければと思います。

問題：最長パスを求めるプログラム
仕様：プログラム＋グラフファイル＋出力されるルートのパスファイル

グラフファイルの形式の例
# graphfile
4
1 2 3
0 3
0
0 1

１行目はコメント行
２行目は頂点数
３行目からは各頂点の隣接リスト
（３行目の最初の123とは0と決めた頂点がつながっている頂点が1 2 3であることを示している）

出力されるパスファイルは
2
0
1
3
です。

ノード数は10<n<10000　何個でもいい
2度同じところを通らない


アルゴリズムとしてはクリティカルパスなどを使うのかなとは思うのですが、どうしても作ることができませんでした。よろしくお願いします。
ページトップ
かずま

Re: 最長経路のプログラム

#2

投稿記事 by かずま » 8年前

書いてみました。ちょっと怪しいところがあります。

コード: 

#include <stdio.h>   // fopen, fclose, fgets, sscanf, printf, putchar
#include <stdlib.h>  // malloc, free
 
#define SIZE 10000

int size;
int *paths[SIZE];
int path[SIZE];
int cur_size, longest_size;
int route[SIZE], longest_route[SIZE];
int used[SIZE];
char buf[SIZE * 5];

void step(int i)
{
    if (used[i]) return;
    used[i] = 1;
    route[cur_size++] = i;
    for (int j = 1; j <= paths[i][0]; j++) {
        step(paths[i][j]);
        if (cur_size > longest_size) {
            longest_size = cur_size; 
            for (int j = 0; j < cur_size; j++)
                longest_route[j] = route[j];
        }
    }
    cur_size--;
    used[i] = 0;
}

int main(void)
{
    FILE *fp = fopen("graph.txt", "r");
    if (!fp) return 1;
    fgets(buf, sizeof buf, fp); // skip a comment line
    if (!fgets(buf, sizeof buf, fp)) return 2;
    if (sscanf(buf, "%d", &size) != 1 || size > SIZE) return 3;
    for (int i = 0; i < size; i++) {
        if (!fgets(buf, sizeof buf, fp)) return 4;
        int k, n;
        char *p = buf;
        for (k = 0; sscanf(p, "%d%n", path + k, &n) == 1; k++)
            p += n;
        paths[i] = malloc((k+1) * sizeof(int));
        if (!paths[i]) return 5;
        paths[i][0] = k;
        for (int j = 0; j < k; j++)
            paths[i][j+1] = path[j];
    }
    fclose(fp);
    for (int i = 0; i < size; i++)
        step(i);
    for (int i = 0; i < longest_size; i++)
        printf("%d\n", longest_route[i]);
    for (int i = 0; i < size; i++)
        free(paths[i]);
}
graph.txt

コード: 

# graphfile
4
1 2 3
0 3
0
0 1
実行結果

コード: 

1
3
0
2
1 3 0 2
2 0 1 3
2 0 3 1
3 1 0 2
の順に見つかり、最初の 1 3 0 2 を出力しています。
21行目を if (cur_size >= longest_size) { にすると
最後の 3 1 0 2 を表示します。
2 0 1 3 を表示するようにしないといけませんか？
ページトップ
FISH

Re: 最長経路のプログラム

#3

投稿記事 by FISH » 8年前

返信ありがとうございます。
自分の環境はwindowsなのでEasyIDECを使用しています。
「19行目」で記述エラーを発見しました。
「identifier」を付け忘れています。というエラーが出たので

コード: 

#include <stdio.h>   // fopen, fclose, fgets, sscanf, printf, putchar
#include <stdlib.h>  // malloc, free

#define SIZE 10000

int size;
int *paths[SIZE];
int path[SIZE];
int cur_size, longest_size;
int route[SIZE], longest_route[SIZE];
int used[SIZE];
char buf[SIZE * 5];
int j;
int i;
int k, n;
char *p = buf;
void step(int i)
{
   if (used[i]) return;
   used[i] = 1;
   route[cur_size++] = i;
   for ( j = 1; j <= paths[i][0]; j++) {
       step(paths[i][j]);
       if (cur_size > longest_size) {
           longest_size = cur_size;
           for ( j = 0; j < cur_size; j++)
               longest_route[j] = route[j];
       }
   }
   cur_size--;
   used[i] = 0;
}

int main(void){
    
   FILE *fp = fopen("graph-file.txt", "r");
   if (!fp) return 1;
   fgets(buf, sizeof buf, fp); // skip a comment line
   if (!fgets(buf, sizeof buf, fp)) return 2;
   if (sscanf(buf, "%d", &size) != 1 || size > SIZE) return 3;
   for ( i = 0; i < size; i++) {
       if (!fgets(buf, sizeof buf, fp)) return 4;
       
       for (k = 0; sscanf(p, "%d%n", path + k, &n) == 1; k++)
           p += n;
       paths[i] = malloc((k+1) * sizeof(int));
       if (!paths[i]) return 5;
       paths[i][0] = k;
       for ( j = 0; j < k; j++)
           paths[i][j+1] = path[j];
   }
   fclose(fp);
   for ( i = 0; i < size; i++)
       step(i);
   for ( i = 0; i < longest_size; i++)
       printf("%d\n", longest_route[i]);
   for ( i = 0; i < size; i++)
       free(paths[i]);
}
for文の中などにあったintを全て上に持っていって実行したのですが、何も起こりませんでした。
コメントいただければ幸いです。
ページトップ
かずま

Re: 最長経路のプログラム

#4

投稿記事 by かずま » 8年前

main() の for (k = 0; の前に、p = buf; が必要です。
step() の for (j = 1; のループの中に for (j = 0; があるのはまずいです。
内側のループを k のループにしてください。

コード: 

           for ( k = 0; k < cur_size; k++)
               longest_route[k] = route[k];

これでどうですか？

i, j, k, n, p はグローバル変数にするのではなく、
step() や main() のローカル変数にしてほしかったなあ。
step() では、中の先頭で、int j, k;
main() では、int i, j, k, n; char *p;
ページトップ
FISH

Re: 最長経路のプログラム

#5

投稿記事 by FISH » 8年前

こんな感じでしょうか。
自分の環境では実行はできましたが動作が停止してしまいました。
VMにlinuxいれて動かしてみようと思います。

コード: 

#include <stdio.h>   // fopen, fclose, fgets, sscanf, printf, putchar
#include <stdlib.h>  // malloc, free

#define SIZE 10000

int size;
int *paths[SIZE];
int path[SIZE];
int cur_size, longest_size;
int route[SIZE], longest_route[SIZE];
int used[SIZE];
char buf[SIZE * 5];

void step(int i){
   int i,j,k;
  if (used[i]) return;
  used[i] = 1;
  route[cur_size++] = i;
  for ( j = 1; j <= paths[i][0]; j++) {
      step(paths[i][j]);
      if (cur_size > longest_size) {
          longest_size = cur_size;
          for ( k = 0; k < cur_size; k++)
              longest_route[k] = route[k];
      }
  }
  cur_size--;
  used[i] = 0;
}

int main(void){
  int i,j,k, n;
  char *p = buf;
  FILE *fp = fopen("graph.txt", "r");
  if (!fp) return 1;
  fgets(buf, sizeof buf, fp); // skip a comment line
  if (!fgets(buf, sizeof buf, fp)) return 2;
  if (sscanf(buf, "%d", &size) != 1 || size > SIZE) return 3;
  for ( i = 0; i < size; i++) {
      if (!fgets(buf, sizeof buf, fp)) return 4;
      for (k = 0; sscanf(p, "%d%n", path + k, &n) == 1; k++)
          p += n;
      paths[i] = malloc((k+1) * sizeof(int));
      if (!paths[i]) return 5;
      paths[i][0] = k;
      for ( j = 0; j < k; j++)
          paths[i][j+1] = path[j];
  }
  fclose(fp);
  for ( i = 0; i < size; i++)
      step(i);
  for ( i = 0; i < longest_size; i++)
      printf("%d\n", longest_route[i]);
  for ( i = 0; i < size; i++)
      free(paths[i]);
}
ページトップ
かずま

Re: 最長経路のプログラム

#6

投稿記事 by かずま » 8年前

41行目の直前に p = buf;
意味を考えてください。
ページトップ
かずま

Re: 最長経路のプログラム

#7

投稿記事 by かずま » 8年前

void step(int i) なので、中で int i; を
宣言してはいけません。
ページトップ
FISH

Re: 最長経路のプログラム

#8

投稿記事 by FISH » 8年前

修正したら通りました。本当にありがとうございます。
ご指摘いただいた点は今から理解しようと思います。

コード: 

#include <stdio.h>   // fopen, fclose, fgets, sscanf, printf, putchar
#include <stdlib.h>  // malloc, free
 
#define SIZE 10000
 
int size;
int *paths[SIZE];
int path[SIZE];
int cur_size, longest_size;
int route[SIZE], longest_route[SIZE];
int used[SIZE];
char buf[SIZE * 5];
 
void step(int i){
   int j,k;
  if (used[i]) return;
  used[i] = 1;
  route[cur_size++] = i;
  for ( j = 1; j <= paths[i][0]; j++) {
      step(paths[i][j]);
      if (cur_size > longest_size) {
          longest_size = cur_size;
          for ( k = 0; k < cur_size; k++)
              longest_route[k] = route[k];
      }
  }
  cur_size--;
  used[i] = 0;
}
 
int main(void){
  int i,j,k, n;
  char *p = buf;
  FILE *fp = fopen("graph.txt", "r");
  if (!fp) return 1;
  fgets(buf, sizeof buf, fp); // skip a comment line
  if (!fgets(buf, sizeof buf, fp)) return 2;
  if (sscanf(buf, "%d", &size) != 1 || size > SIZE) return 3;
  for ( i = 0; i < size; i++) {
      if (!fgets(buf, sizeof buf, fp)) return 4;
      p = buf;
      for (k = 0; sscanf(p, "%d%n", path + k, &n) == 1; k++)
          p += n;
      paths[i] = malloc((k+1) * sizeof(int));
      if (!paths[i]) return 5;
      paths[i][0] = k;
      for ( j = 0; j < k; j++)
          paths[i][j+1] = path[j];
  }
  fclose(fp);
  for ( i = 0; i < size; i++)
      step(i);
  for ( i = 0; i < longest_size; i++)
      printf("%d\n", longest_route[i]);
  for ( i = 0; i < size; i++)
      free(paths[i]);
}
ページトップ
返信

“C言語何でも質問掲示板” へ戻る