幅優先探索

[MORIRIN]

[/code]

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

enum {S = 0, A, B, C, D, E, F, G};

#define N 7
#define M 4

// 隣接リスト
int adjacent[N + 1][M] = {
{S},
{B, C, S},
{A, C, D, S},
{A, B, E, S},
{B, E, F, S},
{C, D, G, S},
{D, S},
{E, S},
};

// 経路
typedef struct {
int path[N];
int len;
} Path;

// 現在地点を求める
int top(Path *p)
{
return p->path[p->len - 1];
}

// 経路に頂点が含まれているか
bool visited(Path *p, int x)
{
for (int i = 0; i < p->len; i++) {
if (p->path == x) return true;
}
return false;
}

// 経路の表示
void print_path(Path *p)
{
for (int i = 0; i < p->len; i++)
printf("%c ", 'A' + p->path - 1);
printf("\n");
}

// キュー
#define Q 64

Path buff[Q];
int front, rear;

// 初期化
void init_queue(int start)
{
buff[0].path[0] = start;
buff[0].len = 1;
rear = 1;
}

// データの取り出し
Path *deq(void)
{
return &buff[front++];
}

// データの追加
void enq(Path *p, int x)
{
buff[rear] = *p;
buff[rear].path[p->len] = x;
buff[rear++].len++;
}

// キューは空か
bool is_empty(void)
{
return front == rear;
}

// 幅優先探索
void bfs(int start, int goal)
{
init_queue(start);
while (!is_empty()) {
Path *p = deq();
int x = top(p);
if (x == goal) {
print_path(p);
} else {
for (int i = 0; i < M; i++) {
int y = adjacent[x];
if (y == 0) break;
if (!visited(p, y)) enq(p, y);
}
}
}
}

int main(void)
{
bfs(A, G);
return 0;
}

int main(void)
{
bfs(A, G);
return 0;
}
[/code]

A~Gの経路を求めるのですが
// 現在地点を求める
int top(Path *p)
{
return p->path[p->len - 1];
}
現在地を求めるコードが以下のようになるというのが理解できませんでした。
どなたか教えていただけると助かります。

[asd]

[/code]
A~Gの経路を求めるのですが
// 現在地点を求める
int top(Path *p)
{
return p->path[p->len - 1];
}
現在地を求めるコードが以下のようになるというのが理解できませんでした。
どなたか教えていただけると助かります。

見たところ下記のページに掲載されているプログラムを抜き出したものでしょうか？

お気楽Ｃ言語プログラミング超入門－経路探索
http://www.geocities.jp/m_hiroi/linux/clang16.html

引用元がある場合はURLや書籍名等を一緒に書いておいたほうがより回答が付きやすくなるかと思います。

上記で正しいものとして回答しますが、このPath構造体はメンバpathにたどってきた頂点を古い順に格納し、
その頂点の数をlenに格納することで経路を表現しています。

例えば頂点をA->B->Dとたどった場合はpathはA,B,Dの順に値が格納され、lenは3になります。
pathには古い順に頂点が格納されているので今どこにいるかはこの配列の末尾の頂点になるはずです。
(上の例だと現在地は頂点D)

配列の要素番号は0から始まるため末尾の要素番号はlen-1で表せます。
そのため現在地はpath[len-1]となります。

提示されているものは関数なので引数のpを使うとp->path[p->len-1]になるわけです。

長くなりましたがわからない部分があれば遠慮なく聞いてくださいね。

あと関連する質問についてリンクを貼っておきます。

勉強サイトについて
http://dixq.net/forum/viewtopic.php?f=3&t=17903

深さ優先探索
http://dixq.net/forum/viewtopic.php?f=3&t=17902