}
cin>>i>>j>>w; arc[i][j]=w; arc[j][i]=w; } for(i=0;i
9087:邻接矩阵遍历
Problem Description
给出一个无向图的各个点之间的邻接关系，输出遍历序列。 Input
有多组数据，每组数据第一行有两个整数n、m,(0 分别输出从标号为1点开始深度和广度优先搜索的序列，每个数之后有一个空格。每个序列分别占一行。 Sample Input 8 9 1 2 1 3 2 4 2 5 3 6 3 7 4 5 4 8 6 7 Sample Output 1 2 4 5 8 3 6 7 1 2 3 4 5 6 7 8 //9087ANSWER CODE1 #include int n,visited[100],visited2[100],arc[100][100]; void DFS(int v) { cout< void BFS(int v) { int front=-1,rear=-1,Q[100]; cout< void main() { int m,i,j,k; while(cin>>n>>m) { for (i=1; i<=n; i++) { for (j=1; j<=n; j++)arc[i][j]=0;} for(k=0;k } 第十一次作业：图的生成树9076，9077，9088 9076:深度优先生成树 Problem Description 设有一连通无向图，其顶点值为字符型并假设各值互不相等，采用邻接矩阵表示法存储表示。利用DFS算法求其深度优先生成树（从下标0的顶点开始遍历），并在遍历过程中输出深度优先生成树的每一条边。 Input 有多组测试数据，每组数据的第一行为两个整数n和e，表示n个顶点和e条边（0 输出深度优先生成树的每一条边，每组输出占一行，每条边信息之间有一空格，每行最后均有一空格，具体格式见样例。 Sample Input 4 4 ABCD 0 1 0 3 1 2 1 3 Sample Output (A,B) (B,C) (B,D) //9076ANSWER CODE1 #include int n,visited[100],arc[100][100];char vertex[20]; void DFS_spanningTree(int v) { visited[v]=1; for (int j=0; j void main() { int e,i,j,k; while(cin>>n>>e>>vertex) { for (i=0; i } 9077:广度优先生成树 Problem Description 设有一连通无向图，其顶点值为字符型并假设各值互不相等，采用邻接矩阵表示法存储表示。利用BFS算法求其广度优先生成树（从下标0的顶点开始遍历），并在遍历过程中输出广度优先生成树的每一条边。 Input 有多组测试数据，每组数据的第一行为两个整数n和e，表示n个顶点和e条边（0 输出广度优先生成树的每一条边，每组输出占一行，每条边信息之间有一空格，每行最后均有一空格，具体格式见样例。 Sample Input 4 4 ABCD 0 1 0 3 1 2 1 3 Sample Output (A,B) (A,D) (B,C) //9077ANSWER CODE1 #include int n,visited[100],arc[100][100];char vertex[20]; void BFS_spanningTree(int v) { int front=-1,rear=-1,Q[100];; visited[v]=1;Q[++rear]=v; while (front!=rear) { v=Q[++front]; for (int j=0; j void main() { int e,i,j,k; while(cin>>n>>e>>vertex) { for (i=0; i 9088:村村相连 Problem Description 漳州市政府调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。市政府的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度 为最小。请计算最小的公路总长度。 Input 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N(N<100)和M；随后的M行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N、M为0时，输入结束，该用例不被处理。 Output 对每个测试用例，在1行里输出最小的公路总长度，如果未能找到请输出\。 Sample Input 3 3 1 2 1 1 3 2 2 3 4 4 6 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0 0 Sample Output 3 5 //9088ANSWER CODE1 #include int i,j,k,count_cc=1;//当count_cc=n时连通，否则不连通输出no found! int length=0;//最小的公路总长度（即最小生成树的代价） int lowcost[100],adjvex[100]; for (i=2; i<=n; i++) //初始化lowcost[]和adjvex[] { lowcost[i]=arc[1][i]; adjvex[i]=1; } lowcost[1]=0; //将顶点0加入集合U中 for (i=2; i<=n; i++) { int weight_min=10000;k=0; for(j=2;j<=n;j++) { if(lowcost[j]!=0 && lowcost[j]!=10000 && lowcost[j]