1. DS图—最小生成树
题目描述
根据输入创建无向网。分别用Prim算法和Kruskal算法构建最小生成树。（假设：输入数据的最小生成树唯一。）
输入
顶点数n
n个顶点
边数m
m条边信息,格式为：顶点1顶点2权值
Prim算法的起点v
输出
输出最小生成树的权值之和
对两种算法，按树的生长顺序，输出边信息(Kruskal中边顶点按数组序号升序输出)
输入样例
6
v1 v2 v3 v4 v5 v6
10
v1 v2 6
v1 v3 1
v1 v4 5
v2 v3 5
v2 v5 3
v3 v4 5
v3 v5 6
v3 v6 4
v4 v6 2
v5 v6 6
v1
输出样例
15
prim:
v1 v3 1
v3 v6 4
v6 v4 2
v3 v2 5
v2 v5 3
kruskal:
v1 v3 1
v4 v6 2
v2 v5 3
v3 v6 4
v2 v3 5
参考代码
#include<iostream> #include<cstring> using namespace std; const int maxx= 100; int n; int array[maxx][maxx]; class Kru{//存储kruskal算法中的节点 public: int bef; int aft; int data; int flag; Kru(){ bef= -1; aft= -1; data= 0; flag= 0; } }; void prim(string str[], int n, int po){//prim算法 int index= po;//开始遍历的顶点 int sum= 0; int visit[n+ 5];//记录每个顶点是否被访问 int dist[n+ 5];//最小树的权重集合 int pos[n+ 5]; //最小树与dist[]对应的顶点 memset(visit, false, sizeof(visit)); visit[index]= true; int bef= index; for(int i= 0; i< n ; i++){//初始dist集合为开始顶点的相邻点 dist[i]= array[index][i]; pos[i]= index* 100+ i;//表示index 与i连通，记录x坐标和y坐标 } //string ss= ""; string beff[n+ 5];//每条边的头 string aft[n+ 5];//每条边的尾 int quan[n+ 5];//每条边的权重 int r= 0; for(int i= 1; i< n; i++){ int minn= 10000; for(int j= 0; j< n; j++){ if(!visit[j]&&dist[j]< minn){//找出dist[]中的最小的那条边 minn= dist[j]; index= j; } } visit[index]= true; beff[r]= str[pos[index]/100]; aft[r]= str[index]; quan[r++]= dist[index]; sum+= dist[index]; for(int j= 0; j< n; j++){ if(!visit[j]&&dist[j]> array[index][j]){//查找下一个顶点相连的边是否还有更小的， //有则更新 dist[j]= array[index][j]; pos[j]= index* 100+ j; } } } cout<<sum<<endl<<"prim:"<<endl; for(int i= 0; i< r; i++){ cout<<beff[i]<<' '<<aft[i]<<" "<<quan[i]<<endl; } } int findmin(Kru kr[], int in){//找出kr[]数组中权重最小的边 int minn= 10000; int index= 0; int flag= 0; for(int i= 0; i< in; i++){ if(!kr[i].flag&&kr[i].data< minn){//如果该边没被访问且最小 minn= kr[i].data; index= i; flag= 1; } } return index; } int find(string str[], int n, string st){//返回st字符串的下标 for(int i= 0; i< n; i++) if(str[i]== st) return i; } void change(int visit[], int n, int a, int b){//将两个顶点及与他们相通的顶点改成同样的值表示 //他们相通 for(int i= 0; i< n; i++) if(visit[i]== a) visit[i]= b; } void kruskal(string str[], int in, int n, Kru kr[]){//kruskal算法 int visit[n+ 5]; for(int i= 0; i< n; i++) visit[i]= i;//初始visit[]数组 //int k= 0; cout<<"kruskal:"<<endl; int k= 0; while(true){ int minn= findmin(kr, in);//找出权重最小的边 kr[minn].flag= 1; int t1= kr[minn].bef; int t2= kr[minn].aft; if(visit[t1]!= visit[t2]){//如果两个顶点的visit值不一样说明还没相通 if(t1> t2){ int t= t1; t1= t2; t2= t; } cout<<str[t1]<<" "<<str[t2]<<" "<<kr[minn].data<<endl; change(visit, n, visit[t1], visit[t2]);//将两个顶点连通 } k++; if(k>= in) break; } } int main(){ cin>>n; string str[100]; for(int i= 0; i< n; i++) cin>>str[i]; for(int i= 0; i< n; i++) for(int j= 0; j< n; j++) array[i][j]= 10000; int in; cin>>in; Kru kr[in+ 5]; for(int j= 0; j< in; j++){ string s1; string s2; int shu; cin>>s1>>s2>>shu; //prim int t1= find(str, n, s1); int t2= find(str, n, s2); array[t1][t2]= shu; array[t2][t1]= shu; //krushal kr[j].bef= t1; kr[j].aft= t2; kr[j].data= shu; kr[j].flag= 0; } string s; cin>>s; int d= find(str, n, s); prim(str, n, d) ; kruskal(str, in, n, kr); return 0; }
2. DS图—图的连通分量
题目描述
输入无向图顶点信息和边信息，创建图的邻接矩阵存储结构，计算图的连通分量个数。
输入
测试次数t
每组测试数据格式如下：
第一行：顶点数 顶点信息
第二行：边数
第三行开始，每行一条边信息
输出
每组测试数据输出，顶点信息和邻接矩阵信息
输出图的连通分量个数，具体输出格式见样例。
每组输出直接用空行分隔。
输入样例
3
4 A B C D
2
A B
A C
6 V1 V2 V3 V4 V5 V6
5
V1 V2
V1 V3
V2 V4
V5 V6
V3 V5
8 1 2 3 4 5 6 7 8
5
1 2
1 3
5 6
5 7
4 8
输出样例
A B C D
0 1 1 0
1 0 0 0
1 0 0 0
0 0 0 0
2
V1 V2 V3 V4 V5 V6
0 1 1 0 0 0
1 0 0 1 0 0
1 0 0 0 1 0
0 1 0 0 0 0
0 0 1 0 0 1
0 0 0 0 1 0
1
1 2 3 4 5 6 7 8
0 1 1 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 1 0
0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0
3
参考代码
#include<iostream> #include<cstring> using namespace std; int find(string str[], string st, int n){ for(int i= 0; i< n; i++) if(str[i]== st) return i; } int main(){ int t; cin>>t; while(t--){ int n; cin>>n; string str[200]; for(int i= 0; i< n; i++) cin>>str[i]; int array[n+ 5][n+5]; for(int i= 0; i< n+ 5; i++) for(int j= 0 ; j< n+ 5; j++) array[i][j]= 0; int in; cin>>in; for(int i= 0 ; i< in; i++){ string s1; string s2; cin>>s1>>s2; int a= find(str, s1, n); int b= find(str, s2, n); array[a][b]= 1; array[b][a]= 1; } for(int i= 0; i< n; i++){ cout<<str[i]; if(i!= n- 1) cout<<" "; } cout<<endl; for(int i= 0; i< n; i++){ for(int j= 0; j< n; j++){ cout<<array[i][j]; if(j!= n- 1) cout<<" "; } cout<<endl; } int arr[n+ 5]; for(int i= 0; i< n+ 5; i++) arr[i]= i; for(int i= 0; i< n; i++){ for(int j= 0; j< n ;j++){ if(array[i][j]){ for(int k= 0; k< n;k++) if(arr[k]== arr[i]) arr[k]= arr[j]; } } } // for(int i= 0; i< n; i++){ // cout<<arr[i]<<"--"; // } // cout<<endl; int shu[n+ 5]; for(int i= 0; i< n ;i++) shu[i]= 0; for(int i= 0; i< n+ 5; i++) shu[arr[i]]++; int sum= 0; for(int i= 0; i< n; i++){ if(shu[i]) sum++; } cout<<sum<<endl<<endl; } return 0; }
