探索のアルゴリズムについて

[つい]

探索のアルゴリズムが間違っています

スタックとキューについてアドバイスお願いします

コード:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 8

void print_matrix(int a[][N]);

int main(void){

  int stack[N],Adjacency_matrix[N][N],visit[N];
  int top,i,j,count_l,k;

  /*-------------------------------------------------------------------*/
  //隣接行列の作成
 
 srand(time(NULL));

  for(i=0;i<8;i++){
    for(j=0;j<8;j++){
     
      Adjacency_matrix[i][j] = rand() % 2;
      //printf("%d\n",Adjacency_matrix[i][j]);
      if(i == j){
	Adjacency_matrix[i][j] = 0;
      }
    }
    //sleep(1);
  }

  //行列の表示
  print_matrix(Adjacency_matrix);
  /*------------------------------------------------------------------*/
  //深さ優先探索開始。。。。
  printf("-------------------------深さ優先探索------------------------\n");
  
  //配列の初期化
  for(i=0;i<8;i++){ 
  
    visit[i] = 0; stack[i] = 0;
}

  //topと出発点を定める。。。。。 
  top = 0;   stack[top] = 0;   top++;
  printf("出発点は0です →");

  //出発点を訪問済みと定義
  visit[0] = 1;

  for(k=0;k<8;k++){

      for(i=0;i<8;i++){
      
      if(Adjacency_matrix[0][i] == 1 && visit[i] == 0){

      stack[top] = i;top++;visit[i] += 1;
      printf("%d→",stack[top - 1]);

      for(j=0;j<8;j++){

	if(Adjacency_matrix[i][j] == 1 && visit[j] == 0){

	    stack[top] = j;top++; visit[j] += 1;
            printf("%d→",stack[top - 1]);


            break;
	}
 
	    top--; stack[top] = -1;
    } 
  }
     }
          
	    top = 0;

	    for(i=0;i<8;i++){
	      if(visit[i] == 0){
		stack[top] = i;top++;
                visit[i] = 1;
                printf("終了\n");
		printf("出発点は%d→",i);
		break; }
	    
	    if(i == 7)break;
  }
  }
  printf("終了\n");
      /*-----------------------------------------------------------*/  	   
//幅優先探索
 printf("-------------------------幅優先探索-------------------------\n");

  int queue[N];
  int first,last;

  first = 0; last = 0;

    for(i=0;i<8;i++){ 
  
    visit[i] = 0; queue[i] = 0;
}

  //出発点を定める。。。。。 
  printf("出発点は0です →");

  //出発点を訪問済みと定義
  visit[0] = 1;
  
  for(k=0;k<8;k++){
    for(i=0;i<8;i++){
      
      if(Adjacency_matrix[queue[first % N]][i] == 1 && visit[i] == 0){
	
	queue[last] = i; last = (last + 1) % 8; visit[i] += 1;
	printf("%d→",i);     
      }
      
      if(i == 7){
	queue[first] = -1; first =  (first + 1) % 8;
      }
      
      
    }    

    first = 0; last = 0;

	    for(i=0;i<8;i++){
	      if(visit[i] == 0){
		queue[last] = i;last++;
                visit[i] = 1;
                printf("終了\n");
		printf("出発点は%d→",i);
		break; }
	    
	    if(i == 7)break;

  }
    
	    /* printf("\n");
    for(i = 0;i < 8;i++){
      printf(" %d ",visit[i]);
    }
    printf("\n");
	    */
    
    
  }

  printf("終了\n");

  }
  
//行列を表示する関数
void print_matrix(int a[][N]) 
{
  int i, j;
  
  for(i=0;i<N;i++) {
    for(j=0;j<N;j++){ 
      printf("%d ", a[i][j]);}
    printf("\n");
  }
  return;
}

[かずま]

質問のが不明瞭で、プログラムもインデントが変なためか、
回答が付きませんね。
フォーラム(掲示板)ルールに従って、質問すれば回答が付いたでしょう。

探索のアルゴリズムは Wikipedia に載っているので、
深さ優先探索と、幅優先探索に従って書いてみました。

コード:

#include <stdio.h>   // printf
#include <stdlib.h>  // srand, rand
#include <time.h>    // time

#define N 8

void print_matrix(int a[][N]);

int main(void)
{
	int Adjacency_matrix[N][N], visit[N] = { 0 }, i, j;

	/*-------------------------------------------------------------------*/
	//隣接行列の作成
	srand(time(NULL));
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			Adjacency_matrix[i][j] = rand() % 2;
			if (i == j) {
				Adjacency_matrix[i][j] = 0;
			}
		}
	}
	//行列の表示
	print_matrix(Adjacency_matrix);

	/*------------------------------------------------------------------*/
	//深さ優先探索開始。。。。
	int stack[N], top = 0;

	printf("-----------------------深さ優先探索------------------------\n");
  
	printf("出発点 ");
	stack[top++] = 0;  visit[0] = 1;

	while (top) {
		int v = stack[--top];
		printf("→%d", v);
		for (i = 0; i < N; i++) {
			if (Adjacency_matrix[v][i] == 1 && visit[i] == 0) {
				stack[top++] = i;  visit[i] = 1;
			}
		}
	}
	printf(" 終了\n");

	/*-----------------------------------------------------------*/  	   
	//幅優先探索
	printf("------------------------幅優先探索-------------------------\n");

	int queue[N * 2], first = 0, last = 0;

	for (i = 0; i < N; i++) visit[i] = 0;

	printf("出発点 [");
	queue[last++] = 0;  visit[0] = 1;
  
	while (first != last) {
		int v = queue[first++];
		while (v == N) {
			printf("]→[");
			if (first == last) goto end;
			v = queue[first++];
		}
		printf(" %d", v);
		queue[last++] = N;
		for (i = 0; i < N; i++) {
			if (Adjacency_matrix[v][i] == 1 && visit[i] == 0) {
				queue[last++] = i;  visit[i] = 1;
			}
		}    
	}
end:
	printf("] 終了\n");
}
  
void print_matrix(int a[][N])  //行列を表示する関数
{
	int i, j;
  
	printf("    ");
	for (i = 0; i < N; i++) printf(" %d", i);
	printf("\n   +-----------------\n");
	for (i = 0; i < N; i++) {
		printf(" %d |", i);
		for (j = 0; j < N; j++)
			printf(" %d", a[i][j]);
		printf("\n");
	}
}

実行結果

コード:

     0 1 2 3 4 5 6 7
   +-----------------
 0 | 0 1 0 1 1 0 0 0
 1 | 1 0 1 0 1 1 0 1
 2 | 1 1 0 0 0 1 0 1
 3 | 0 1 1 0 0 0 0 1
 4 | 0 0 1 1 0 0 1 0
 5 | 0 1 1 0 1 0 1 1
 6 | 0 0 0 0 1 0 0 1
 7 | 1 1 0 1 0 0 0 0
-----------------------深さ優先探索------------------------
出発点 →0→4→6→7→2→5→3→1 終了
------------------------幅優先探索-------------------------
出発点 [ 0]→[ 1 3 4]→[ 2 5 7]→[]→[ 6]→[]→[]→[]→[] 終了

深さ優先探索は、最初に見つかった経路を示しています。

幅優先探索の表示は、次の通りです。
0 から行けるのは [1 3 4] です。
1 から行けるのは [0 2 4 5 7] ですが、未訪問の [2 5 7] に行きます。
3 から行けるのは [1 2 7] ですが、未訪問はありません。
4 から行けるのは [2 3 6] ですが、未訪問の [6] に行きます。
この時点ですべての点を訪問しているので、
[2 5 7 6] からはどこにも行きません。

[かずま]

実行結果

コード:

     0 1 2 3 4 5 6 7
   +-----------------
 0 | 0 1 0 1 1 0 0 0
 1 | 1 0 1 0 1 1 0 1
 2 | 1 1 0 0 0 1 0 1
 3 | 0 1 1 0 0 0 0 1
 4 | 0 0 1 1 0 0 1 0
 5 | 0 1 1 0 1 0 1 1
 6 | 0 0 0 0 1 0 0 1
 7 | 1 1 0 1 0 0 0 0
-----------------------深さ優先探索------------------------
出発点 →0→4→6→7→2→5→3→1 終了

深さ優先探索は、最初に見つかった経路を示しています。

すみません。
最初に見つかった経路ではありません。
7 から 2 には行けません。

出発点では、スタックは [0]。
0 を取り出して、スタックには [1 3 4] を入れる。
4 を取り出して、4 から行ける [2 3 6] のうち未訪問の [2 6] を
追加し、スタックは [1 3 2 6]。
6 を取り出して、6 から行ける [4 7] のうち未訪問の 7 を追加し、
スタックは [1 3 2 7]。
7 を取り出して、7 から行ける [0 1 3] は全部訪問済みなので
スタックは [1 3 2]
2 を取り出して、2 から行ける [0 1 5 7] のうち未訪問の 5 を
追加し、スタックは [1 3 5]。
5 を取り出して、5 から行ける [4 7] は全部訪問済みなので
スタックは [1 3]。
3 を取り出して、3 から行ける [1 2 7] は全部訪問済みなので
スタックは [1]。
1 を取り出して、3 から行ける [0 2 4 5 7] は全部訪問済みなので
スタックは []
スタックが空になったので終了。
0→4→6→7→2→5→3→1 は、スタックから取り出したものの列で、
訪問順の点でした。経路ではありません。

[かずま]

では、経路を求めてみましょう。

まずは、すべての点を通る経路。

コード:

#include <stdio.h>

#define N 8

void print_matrix(int a[][N]);

int route[N], nr = 0, visit[N];

void dfs(int a[][N], int v)  // depth first search
{
	route[nr++] = v;
	visit[v] = 1;
	for (int i = N; --i; )
		if (a[v][i] && !visit[i]) dfs(a, i);
	if (nr == N) {
		for (int i = 0; i < nr; i++) printf(" %d", route[i]);
		putchar('\n');
	}
	visit[v] = 0;
	nr--;
}

int main(void)
{
	int a[N][N] = {
		0, 1, 0, 1, 1, 0, 0, 0,
		1, 0, 1, 0, 1, 1, 0, 1,
		1, 1, 0, 0, 0, 1, 0, 1,
		0, 1, 1, 0, 0, 0, 0, 1,
		0, 0, 1, 1, 0, 0, 1, 0,
		0, 1, 1, 0, 1, 0, 1, 1,
		0, 0, 0, 0, 1, 0, 0, 1,
		1, 1, 0, 1, 0, 0, 0, 0,
	};
	print_matrix(a);
	dfs(a, 0);
} 

void print_matrix(int a[][N])  //行列を表示する関数
{
	int i, j;
  
	printf("    ");
	for (i = 0; i < N; i++) printf(" %d", i);
	printf("\n   +-----------------\n");
	for (i = 0; i < N; i++) {
		printf(" %d |", i);
		for (j = 0; j < N; j++)
			printf(" %d", a[i][j]);
		putchar('\n');
	}
	putchar('\n');
}

実行結果

コード:

     0 1 2 3 4 5 6 7
   +-----------------
 0 | 0 1 0 1 1 0 0 0
 1 | 1 0 1 0 1 1 0 1
 2 | 1 1 0 0 0 1 0 1
 3 | 0 1 1 0 0 0 0 1
 4 | 0 0 1 1 0 0 1 0
 5 | 0 1 1 0 1 0 1 1
 6 | 0 0 0 0 1 0 0 1
 7 | 1 1 0 1 0 0 0 0

 0 4 6 7 3 2 5 1
 0 4 6 7 3 2 1 5
 0 4 6 7 3 1 5 2
 0 4 6 7 3 1 2 5
 0 4 3 7 1 2 5 6
 0 4 3 2 7 1 5 6
 0 4 3 2 5 6 7 1
 0 4 3 2 1 5 6 7
 0 4 3 1 2 5 6 7
 0 4 2 7 3 1 5 6
 0 4 2 5 6 7 3 1
 0 4 2 1 5 6 7 3
 0 3 7 1 5 6 4 2
 0 3 7 1 4 2 5 6
 0 3 7 1 2 5 6 4
 0 3 7 1 2 5 4 6
 0 3 2 7 1 5 6 4
 0 3 2 7 1 5 4 6
 0 3 2 5 7 1 4 6
 0 3 2 5 6 7 1 4
 0 3 2 5 4 6 7 1
 0 3 2 5 1 4 6 7
 0 3 2 1 5 4 6 7
 0 3 1 5 6 4 2 7
 0 3 1 4 2 5 6 7
 0 3 1 2 5 4 6 7
 0 1 7 3 2 5 6 4
 0 1 7 3 2 5 4 6
 0 1 5 6 4 3 2 7
 0 1 5 6 4 2 7 3
 0 1 5 4 6 7 3 2
 0 1 4 6 7 3 2 5
 0 1 4 3 2 5 6 7
 0 1 4 2 5 6 7 3
 0 1 2 5 6 4 3 7
 0 1 2 5 4 6 7 3
 

次は行き詰まるまでのすべての経路

コード:

#include <stdio.h>

#define N 8

void print_matrix(int a[][N]);

int route[N], nr = 0, visit[N];

void dfs(int a[][N], int v)  // depth first search
{
	route[nr++] = v;
	visit[v] = 1;
	int next = 0;
	for (int i = N; --i; )
		if (a[v][i] && !visit[i]) dfs(a, i), next = 1;
	if (next == 0) {
		for (int i = 0; i < nr; i++) printf(" %d", route[i]);
		putchar('\n');
	}
	visit[v] = 0;
	nr--;
}

int main(void)
{
	int a[N][N] = {
		0, 1, 0, 1, 1, 0, 0, 0,
		1, 0, 1, 0, 1, 1, 0, 1,
		1, 1, 0, 0, 0, 1, 0, 1,
		0, 1, 1, 0, 0, 0, 0, 1,
		0, 0, 1, 1, 0, 0, 1, 0,
		0, 1, 1, 0, 1, 0, 1, 1,
		0, 0, 0, 0, 1, 0, 0, 1,
		1, 1, 0, 1, 0, 0, 0, 0,
	};
	print_matrix(a);
	dfs(a, 0);
} 

void print_matrix(int a[][N])  //行列を表示する関数
{
	int i, j;
  
	printf("    ");
	for (i = 0; i < N; i++) printf(" %d", i);
	printf("\n   +-----------------\n");
	for (i = 0; i < N; i++) {
		printf(" %d |", i);
		for (j = 0; j < N; j++)
			printf(" %d", a[i][j]);
		putchar('\n');
	}
	putchar('\n');
}

実行結果

コード:

     0 1 2 3 4 5 6 7
   +-----------------
 0 | 0 1 0 1 1 0 0 0
 1 | 1 0 1 0 1 1 0 1
 2 | 1 1 0 0 0 1 0 1
 3 | 0 1 1 0 0 0 0 1
 4 | 0 0 1 1 0 0 1 0
 5 | 0 1 1 0 1 0 1 1
 6 | 0 0 0 0 1 0 0 1
 7 | 1 1 0 1 0 0 0 0

 0 4 6 7 3 2 5 1
 0 4 6 7 3 2 1 5
 0 4 6 7 3 1 5 2
 0 4 6 7 3 1 2 5
 0 4 6 7 1 5 2
 0 4 6 7 1 2 5
 0 4 3 7 1 5 6
 0 4 3 7 1 5 2
 0 4 3 7 1 2 5 6
 0 4 3 2 7 1 5 6
 0 4 3 2 5 7 1
 0 4 3 2 5 6 7 1
 0 4 3 2 5 1 7
 0 4 3 2 1 7
 0 4 3 2 1 5 7
 0 4 3 2 1 5 6 7
 0 4 3 1 7
 0 4 3 1 5 7
 0 4 3 1 5 6 7
 0 4 3 1 5 2 7
 0 4 3 1 2 7
 0 4 3 1 2 5 7
 0 4 3 1 2 5 6 7
 0 4 2 7 3 1 5 6
 0 4 2 7 1 5 6
 0 4 2 5 7 3 1
 0 4 2 5 7 1
 0 4 2 5 6 7 3 1
 0 4 2 5 6 7 1
 0 4 2 5 1 7 3
 0 4 2 1 7 3
 0 4 2 1 5 7 3
 0 4 2 1 5 6 7 3
 0 3 7 1 5 6 4 2
 0 3 7 1 5 4 6
 0 3 7 1 5 4 2
 0 3 7 1 5 2
 0 3 7 1 4 6
 0 3 7 1 4 2 5 6
 0 3 7 1 2 5 6 4
 0 3 7 1 2 5 4 6
 0 3 2 7 1 5 6 4
 0 3 2 7 1 5 4 6
 0 3 2 7 1 4 6
 0 3 2 5 7 1 4 6
 0 3 2 5 6 7 1 4
 0 3 2 5 6 4
 0 3 2 5 4 6 7 1
 0 3 2 5 1 7
 0 3 2 5 1 4 6 7
 0 3 2 1 7
 0 3 2 1 5 7
 0 3 2 1 5 6 7
 0 3 2 1 5 6 4
 0 3 2 1 5 4 6 7
 0 3 2 1 4 6 7
 0 3 1 7
 0 3 1 5 7
 0 3 1 5 6 7
 0 3 1 5 6 4 2 7
 0 3 1 5 4 6 7
 0 3 1 5 4 2 7
 0 3 1 5 2 7
 0 3 1 4 6 7
 0 3 1 4 2 7
 0 3 1 4 2 5 7
 0 3 1 4 2 5 6 7
 0 3 1 2 7
 0 3 1 2 5 7
 0 3 1 2 5 6 7
 0 3 1 2 5 6 4
 0 3 1 2 5 4 6 7
 0 1 7 3 2 5 6 4
 0 1 7 3 2 5 4 6
 0 1 5 7 3 2
 0 1 5 6 7 3 2
 0 1 5 6 4 3 7
 0 1 5 6 4 3 2 7
 0 1 5 6 4 2 7 3
 0 1 5 4 6 7 3 2
 0 1 5 4 3 7
 0 1 5 4 3 2 7
 0 1 5 4 2 7 3
 0 1 5 2 7 3
 0 1 4 6 7 3 2 5
 0 1 4 3 7
 0 1 4 3 2 7
 0 1 4 3 2 5 7
 0 1 4 3 2 5 6 7
 0 1 4 2 7 3
 0 1 4 2 5 7 3
 0 1 4 2 5 6 7 3
 0 1 2 7 3
 0 1 2 5 7 3
 0 1 2 5 6 7 3
 0 1 2 5 6 4 3 7
 0 1 2 5 4 6 7 3
 0 1 2 5 4 3 7