《数据结构实验与实训教程(第4版)》程序代码

head = tail = 0; /* 队列置空 */ printf( \/* 访问出发顶点 */ visited[s] = 1; /* 置该顶点已被访问标志 */ queue[ tail++ ] = s; /* 出发顶点进队 */ while(_18_____ ) { /* 队不空循环 */ v = queue[ head++ ]; /* 取队列首顶点 */ for( j = 0; j < n; j++ ) { /* 按邻接矩阵, 顺序考察与顶点v邻接的各顶点w */ if(__19____ && visited[j] == 0 ) { /* 如果该顶点有边且未被访问过 */ printf( \/* 访问顶点j */ visited[j] = 1; /* 置顶点w已被访问标志 */

__20_____; /* 顶点j进队 */

}

} } }

void main() { lgraph lg; mgraph mg; int n, i; n = creat_graph( lg, mg ); for( i = 0; i < n; i++ ) visited[i] = 0; /* 置全部顶点为未访问标志 */ printf( \邻接表表示的图的递归深度优先遍历 \\n\ __21____; getch(); for( i = 0; i < n; i++ ) visited[i] = 0; /* 置全部顶点为未访问标志 */ printf( \邻接矩阵表示的图的递归深度优先遍历\\n\ ___22___; getch();

printf( \邻接表表示的图的广度优先遍历\\n\ ___23_____; getch();

printf( \邻接矩阵表示的图的广度优先遍历\\n\ ___24____; }

56

程序2：题3 求最少换车次数 #include #define M 20 #define N 50 int a[N+1]; /* 用于存放一条线路上的各站编号 */ int g[N][N]; /* 存储对应的邻接矩阵 */ int dist[N];

/* 存储站0到各站的最短路径 */

int m=0, n=0;

void buildG() /* 建图 */

{ int i, j, k, sc, dd; while( 1 ) { printf( \输入公交线路数[1-%d], 公交站数[1-%d]\\n\, M, N );

scanf( \%d%d\ if( m >= 1 && m <= M && n >= 1 && n <= N ) break; }

for( i = 0; i < n; i++ ) /* 邻接矩阵清0 */

for( j = 0; j < n; j++ ) g[i][j] = 0; for( i = 0; i < m; i++ ) { printf( \沿第%d条公交车线路前进方向的各站编号(0<=编号<=%d, -1结束):\\n\, i+1,

sc = 0;

/* 当前线路站计数器 */

n-1);

}

while( 1 ) { scanf( \%d\ if( dd == -1 ) break;

if( dd >= 0 && dd < n ) a[_1__] = dd; /* 保存站点编号 */ <