这里先抽象一个队列：
QUEUE Q;
SETNULL(Q); // 队列清空
EMPTY(Q); // 队列Q为空返回true
n = DEQUEUE(Q); // 出队
ENQUEUE(Q, n); // 入队
。
使用邻接矩阵存储，先假设已有定义 以及 初始化：
typedef struct {
sometype matrix [X+1] [X+1]; // 邻接矩阵，习惯上数组标号0的元素不用，故 X+1，下同
string vertex[X+1]; // 顶点的名字
int n, e; // n 是顶点，e 是边数
} Graph;
Graph graph;
。
bool visited[n+1]; // all of false
void BFS(int vex)
{
SETNULL(Q);
ENQUEUE(Q, vex);
//
// access the first vertex, ex, cout << graph.vertex[vex] <<endl;
visited[vex] = true;
while( !EMPTY(Q) ) {
int i = DEQUEUE(Q);
for(int j = 1; j <= graph.n; j++)
if( graph.matrix[i][j] == 1 && !visited[j] ) // == 1 因存储结构而异
{
// access other vertex, ex, cout << graph.vertex[j] <<endl;
visited[j] = true;
ENQUEUE(Q, j);
}
}
}
。
这是来自于十一五的书，里面的一些注释是自己加的。
。
我的疑问是，如果图式 有向图 的话，那么假设一个图：
如果图是这样的话，那么
if( graph.matrix[i][j] == 1 && !visited[j] )
好像更本就进不去吧？
。
所以我认为这句应改为
if( (graph.matrix[i][j] == 1 || graph.matrix[j][i] == 1) && !visited[j] )
。
大家看下我这个分析是不是正确的。