% E5 % AE % 9e9% aa % 8c % E5 % 9b % 20 % E5 % 9b % be7 % 9a % 84 % e9 % 81 % 8d % E5 % 8b % 86 % 0a % 20 % E4 % 25 % 2000 5 % 203 % E6 % 9e % 84 % E7 % 9a % 84 % E7 % 89 % B9 % E7 % 82 % B9 % E5 % 8f % e9 % 80 % E7 % 94 % A8 % E8 % 83 % E5 % 20 % 88 4 % ba % 8c % E3 % 80 % 81 % E5 % AE % 9e9% aa % 8c % E7 % af % E5 % a2 % 83 % 0a % 201 % E3 % 80 % 81pc % 20 % B3 % E7 8 % e9 % 82 % bb % E6 % a5 % E7 % 9f % a9 % b5 % BD % 9c % E5 % ad % 98 % E5 % 82 % A8 % E7 % bb % 99 % 204 % BC % 98 % ed 0f % 2f % e9 % a1 % B6 % E7 % 82 % B9 % B0 % 20 % E8 % be9 % 0a % 201 % 2c3 % 202 % 2c5 % 203 % 2c4 % 203 % 203 % 203 % E6 % 90 % E7 % B4 % a2 % E8 % BF % e9 % 97 % ae9 % a1 % ba % E5 % 25 % 20 E3 % 80 % 81 % E6 % b5 % 8b % E8 % af % 95 % E5 % 85 ude % 20 % 27 math.h % 27 % 20 % 23包含% 20 % 27 time.h % 27 % 20 % 23 define % 20 % 200 % 23 define % 20 maxv ex % % 2f % 23 define % 20 infinity % 2065535 % 20 % 2f % 20 % E6 % 97 % A0 % E7 % a9 % B7 % a4 % a7 % 20 % a2f % 200 5 % B0 % 20e7% ad % 89 % 20 % 2a % 2f typedef % 20 char % 20 vertextype % 3b % 20 % 2f % 20 % e9 % a1 % B6 % E7 % 82 % B9 % E7 % E7 % % E7 % 9a % 84 % E6 % 9d % 83 % 25 % 20 % 9a % E4 % B9 % 89 % 20 % 2a % 20 typedef % 20 struct %7bvertextype % 20 vexs %5bmax vedef a5 % E7 % 9f % e9 % b5 % BC % 8c % E5 % 8f % E7 % 25 % 200 % 2f % 20 % E5 % 9b % be4 % b8 % ad % E5 % BD % 93 % E5 % 89 % 7 % 9a % 84 % e9 % 82 % bb % E6 % 8e5% E7 % 25 % 20g % 29 %7bint % 20i % 2cj % 2cw % 23b printf % 28 % E8 % be % 93 % E5 nf % 28 % 27 % 25d % 25d % 27 % 2cg-num nodes % 25 % 20 % 92 % 8c % E8 % be % B9 % E6 % 95 % B0 % 20 % 2a % e9 % a1 % B6 % E7 % 82 % B9 % E8 % a1 % A8 % 20 % 2a %2fscanf % 28g-vexs % 5bi % 29 %3BFF % 20-num nodes % 3bj % 20 5 % 2000 % 3bk % 20g-numedges % 3bk % 20 % 20 % 29 % 2f % 20 % E8 % af % bb % E5 % 85 % a5 numedges % E6 % 9d % a1 29 % E4 % b8 % 8a % E7 % 9a % 25 % 2060 % 5cn % 27 % 29 % 3b扫描% 28 % 27 % 25d % 25d % 27 % 2ci % 2cw % 29 5bi % 5d % 3d % 20g-arc % 5bi % 5d % 5bj % 5d % 5b % 20b % 25 % 20 % 8c % 9f % a9 % e9 % 98 % b5 % E5 % % 29 %7bfor % 28 int % 20j % 3d0% 3b % 20jg.num nodes % 3bj % 20 % 20 % 29 % 7b printf % 28 % 27 % 25
nt; /* 头指针 */int rear;/* 尾指针，若队列不空，指向队列尾元素的下一个位置 */}Queue; /* 初始化一个空队列Q */Status InitQueue(Queue *Q){Q->front=0;Q->rear=0;return OK;} /* 若队列Q为空队列,则返回TRUE,否则返回FALSE */Status QueueEmpty(Queue Q){ if(Q.front==Q.rear) /* 队列空的标志 */return TRUE;elsereturn FALSE;} /* 若队列未满，则插入元素e为Q新的队尾元素 */Status EnQueue(Queue *Q,int e){if ((Q->rear+1)%MAXSIZE == Q->front)/* 队列满的判断 */return ERROR;Q->data[Q->rear]=e;/* 将元素e赋值给队尾 */Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置， *//* 若到最后则转到数组头部 */return OK;} /* 若队列不空，则删除Q中队头元素，用e返回其值 */Status DeQueue(Queue *Q,int *e){if (Q->front == Q->rear)/* 队列空的判断 */return ERROR;*e=Q->data[Q->front];/* 将队头元素赋值给e */Q->front=(Q->front+1)%MAXSIZE;/* front指针向后移一位置， *//* 若到最后则转到数组头部 */return OK;} void CreateMGraph(MGraph *G){int i, j; G->numEdges=9;G->numVertexes=6; /* 读入顶点信息，建立顶点表 */G->vexs[0]='A';G->vexs[1]='B';G->vexs[2]='C';G->vexs[3]='D';G->vexs[4]='E';G->vexs[5]='F'; for (i = 0; i < G->numVertexes; i++)/* 初始化图 */{for ( j = 0; j < G->numVertexes; j++){G->arc[i][j]=0;}} G->arc[0][1]=1;G->arc[0][2]=1; G->arc[0][4]=1; G->arc[1][2]=1; G->arc[1][3]=1; G->arc[2][3]=1; G->arc[2][5]=1; G->arc[3][4]=1;G->arc[3][5]=1; for(i = 0; i < G->numVertexes; i++){for(j = i; j < G->numVertexes; j++){G->arc[j][i] =G->arc[i][j];}} } Boolean visited[MAXVEX]; /* 访问标志的数组 */ /* 邻接矩阵的深度优先递归算法 */void DFS(MGraph G, int i){int j; visited[i] = TRUE; printf("%c ", G.vexs[i]);/* 打印顶点，也可以其它操作 */for(j = 0; j < G.numVertexes; j++)if(G.arc[i][j] == 1 && !visited[j]) DFS(G, j);/* 对为访问的邻接顶点递归调用 */} /* 邻接矩阵的深度遍历操作 */void DFSTraverse(MGraph G){int i; for(i = 0; i < G.numVertexes; i++) visited[i] = FALSE; /* 初始所有顶点状态都是未访问过状态 */for(i = 0; i < G.numVertexes; i++) if(!visited[i]) /* 对未访问过的顶点调用DFS，若是连通图，只会执行一次 */ DFS(G, i);} /* 邻接矩阵的广度遍历算法 */void BFSTraverse(MGraph G){int i, j;Queue Q;for(i = 0; i < G.numVertexes; i++) visited[i] = FALSE; InitQueue(&Q);/* 初始化一辅助用的队列 */ for(i = 0; i < G.numVertexes; i++) /* 对每一个顶点做循环 */ {if (!visited[i])/* 若是未访问过就处理 */{visited[i]=TRUE;/* 设置当前顶点访问过 */printf("%c ", G.vexs[i]);/* 打印顶点，也可以其它操作 */EnQueue(&Q,i);/* 将此顶点入队列 */while(!QueueEmpty(Q))/* 若当前队列不为空 */{DeQueue(&Q,&i);/* 将队对元素出队列，赋值给i */for(j=0;j<G.numVertexes;j++) { /* 判断其它顶点若与当前顶点存在边且未访问过 */if(G.arc[i][j] == 1 && !visited[j]) { visited[j]=TRUE;/* 将找到的此顶点标记为已访问 */printf("%c ", G.vexs[j]);/* 打印顶点 */EnQueue(&Q,j);/* 将找到的此顶点入队列 */} } }}}} int main(void){ MGraph G;CreateMGraph(&G);printf("n深度遍历：");DFSTraverse(G);printf("n广度遍历：");BFSTraverse(G);return 0;}运行结果：
五、实验小结