Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > Data structs > View Code
(13)最小生成树.cpp
Package: datastruct1　[view]
Upload User: wxj1219
Upload Date: 2013-01-31
Package Size: 6k
Code Size: 2k
Category:

Data structs

Development Platform:

C/C++

(13)最小生成树.cpp：Code Content
  1. #include<iostream.h>
  2. #include<conio.h>
  3. #include<stdio.h>
  5. int NodeCount;
  6. char Node[20];
  7. char Graph[20][20];
  8. char Queue[20];
  9. char Checked[20];
  11. char Locate(char Char)
  12. {
  13. char Temp;
  14. for(Temp=0;Temp<NodeCount;Temp++)
  15. if(Node[Temp]==Char)
  16. break;
  17. return Temp;
  18. }
  20. void main()
  21. {
  22. char Temp1,Temp2;
  23. int Temp3;
  24. char min,mintemp,mintemp1;
  25. clrscr();
  26. for(Temp2=0;Temp2<20;Temp2++)
  27. for(Temp1=0;Temp1<20;Temp1++)
  28. Graph[Temp2][Temp1]=0;
  29. for(Temp1=0;Temp1<20;Temp1++)
  30. {
  31. Queue[Temp1]=0;
  32. Checked[Temp1]=0;
  33. }
  34. cout<<"Input the node count:";
  35. cin>>NodeCount;
  36. cout<<"Input the node:";
  37. for(Temp1=0;Temp1<NodeCount;Temp1++)
  38.   cin>>Node[Temp1];
  39. cout<<"Input the link"<<endl;
  40. Temp1=0;
  41. while(1)
  42. {
  43. cout<<"Input the first node:";
  44. cin>>Temp1;
  45. cout<<"Input the second node:";
  46. cin>>Temp2;
  47. cout<<"Input the weight:";
  48. cin>>Temp3;
  49. if(Temp1=='$')
  50. break;
  51. Temp1=Locate(Temp1);
  52. Temp2=Locate(Temp2);
  53. Graph[Temp2][Temp1]=Temp3;
  54. Graph[Temp1][Temp2]=Temp3;
  55. }
  56. for(Temp2=0;Temp2<NodeCount;Temp2++)
  57. {
  58. for(Temp1=0;Temp1<NodeCount;Temp1++)
  59. cout<<(int)Graph[Temp2][Temp1]<<" ";
  60. cout<<endl;
  61. }
  62. Queue[0]=0;
  63. Checked[0]=1;
  64. for(Temp1=1;Temp1<NodeCount;Temp1++)
  65. {
  66. min=100;
  67. for(Temp2=0;Temp2<Temp1;Temp2++)
  68. for(Temp3=0;Temp3<NodeCount;Temp3++)
  69. if((!Checked[Temp3])&&(Graph[Queue[Temp2]][Temp3]>0)&&(Graph[Queue[Temp2]][Temp3]<min))
  70. {
  71. min=Graph[Queue[Temp2]][Temp3];
  72. mintemp=Temp3;
  73. mintemp1=Queue[Temp2];
  75. }
  76. cout<<Node[mintemp1]<<"->"<<Node[mintemp]<<endl;
  77. Checked[mintemp]=1;
  78. Queue[Temp1]=mintemp;
  79. }
  80. }