form1.cs

图的遍历

				return true;
			}
			else
			{
				for(int j=0;j<i;j++)
				{
					if (IsDifferent==NodeName[j])
					{
						return false;
					}
				}
			}
			return true;


		}

		private void button4_Click(object sender, System.EventArgs e)
		{
			if(this.comboBox1.Text==this.comboBox2.Text || this.comboBox1.Text=="" || this.comboBox2.Text=="" || this.textBox4.Text=="")
			{
				if (this.comboBox1.Text=="" || this.comboBox2.Text=="" || this.textBox4.Text=="")
				{
					MessageBox.Show("数据不能为空","错误",MessageBoxButtons.OK,MessageBoxIcon.Warning);
				}
				else
				{
					MessageBox.Show("不能从自身连接到自身","错误",MessageBoxButtons.OK,MessageBoxIcon.Warning);
				}
			}
			else
			{
				this.x=System.Convert.ToInt32(this.comboBox1.Items.IndexOf(this.comboBox1.Text));
				this.y=System.Convert.ToInt32(this.comboBox2.Items.IndexOf(this.comboBox2.Text));
				this.weight[x,y]=this.textBox4.Text;
				this.weight[y,x]=this.textBox4.Text;
				MessageBox.Show("请输入下个连接，若所有连接都已完成，按“完成”","输入成功",MessageBoxButtons.OK,MessageBoxIcon.Information);
				this.comboBox1.Text="";
				this.comboBox2.Text="";
				if(this.textBox4.Enabled==true)
				{
					this.textBox4.Text="";
				}
//				this.textBox4.Text="";
			}		
		}

		private void button8_Click(object sender, System.EventArgs e)
		{
			this.groupBox1.Visible=false;
			this.groupBox2.Visible=false;
			this.label1.Text="图的遍历：";
			this.groupBox4.Top=this.groupBox2.Top;
			this.groupBox3.Visible=true;
			this.groupBox4.Visible=true;
			this.groupBox3.Top=this.groupBox1.Top;
			this.groupBox4.Top=this.groupBox2.Top;
			if (this.textBox4.Enabled==true)
			{
				this.label9.Visible=true;
				this.label3.Visible=true;
				this.label9.Top=this.groupBox3.Top+this.groupBox3.Height+this.label4.Height;
				this.label3.Top=this.groupBox3.Top+this.groupBox3.Height+this.label4.Height;
			}
		}

		private void button1_Click(object sender, System.EventArgs e)
		{
			this.label2.Text="队列的出入情况：";
			this.groupBox3.Text="队列";
			this.p=0;
			this.q=0;
			for (x=0;x<i;x++)
				this.vvisitied[x]=false;
			this.button1.Enabled=false;
			this.button2.Enabled=true;
			this.label4.Visible=true;
			this.label8.Visible=true;
			this.label4.Top=this.groupBox3.Top+this.groupBox3.Height+8;
			this.label8.Top=this.label4.Top;
			this.textBox3.Text="";
			this.label8.Text="";
			this.label8.Text=this.cl[0].NodeName;
			this.allvisit[0]=this.cl[0].NodeName;
			BFS(cl[0].NodeName,this.weight,this.vvisitied);
			if(this.textBox3.Text==null)
				this.textBox3.Text=this.cl[0].NodeName;
//			if (this.IsNone(this.vvisitied))
//			{
				MessageBox.Show("所有节点都已访问完毕","广度优先遍历结果",MessageBoxButtons.OK,MessageBoxIcon.Information);
//			}
		}

		
		private void Form1_Load(object sender, System.EventArgs e)
		{
		   this.z=0;
		   this.LoadFlash.Play();
           this.timer1.Enabled=true;
			
		      
		
		}

		private void timer1_Tick(object sender, System.EventArgs e)
		{
            this.z=this.z+0.1;
			if (z>1.5)
			{
				this.label1.Visible=true;
				this.groupBox2.Visible=true;
				if(z>2.5)
					this.groupBox1.Visible=true;
			}
		
		}

		private void button2_Click(object sender, System.EventArgs e)
		{
			this.label2.Text="栈的出入情况：";
			this.groupBox3.Text="栈";
			this.p=0;
			this.q=0;
			for (x=0;x<i;x++)
				this.vvisitied[x]=false;
			this.button2.Enabled=false;
			this.button1.Enabled=true;
			this.label4.Visible=true;
			this.label8.Visible=true;
			this.label4.Top=this.groupBox3.Top+this.groupBox3.Height+8;
			this.label8.Top=this.label4.Top;
			this.textBox3.Text="";
			this.label8.Text=this.cl[0].NodeName;
			this.allvisit[0]=this.cl[0].NodeName;
			DFS(cl[0].NodeName,this.weight,this.vvisitied);
		}

	
		private void DFS(string v,string[,] w,bool[] visited)
		{
			int a=getnum(v);
			this.vvisitied[a]=true;
			Visit1(v,this.textBox3);
			string now=getnext(this.weight,this.vvisitied,v);
			this.allvisit[++p]=now;
			if (now=="none")
			{
				if(IsNone(this.vvisitied))
					MessageBox.Show("所有节点都已访问完毕","深度优先遍历结果",MessageBoxButtons.OK,MessageBoxIcon.Information);
				else
				{
					try
					{
						p--;
						DFS(this.allvisit[--p],this.weight,this.vvisitied);
					}
					catch
					{
						for(int n=0;n<i;n++)
						{
							if (visited[n]==false)
							{
								this.allvisit[++p]=this.cl[n].NodeName;
								this.Visit2(this.cl[n].NodeName,this.label8);
								DFS(this.cl[n].NodeName,this.weight,this.vvisitied);
							}
						}
					}

				}

			}
			else
			{
				this.label8.Text=this.label8.Text+", "+now;
				DFS(now,this.weight,this.vvisitied);
			}			
		}
		private void BFS(string v,string[,] w,bool[] visited)
		{
			this.allvisit[q++]=v;
			try
			{
				for(;!this.IsNone(visited) && q<i;)
					this.visitall(this.allvisit[p],w,visited);
			}
			catch
			{
				for(int n=0;n<i;n++)
				{
					if (visited[n]==false)
					{
						p=0;
						q=0;
						//						this.allvisit[p++]=this.cl[n].NodeName;
						if(this.textBox3.Text=="")
						{
							this.textBox3.Text=this.cl[0].NodeName;
						}
						this.Visit2(this.cl[n].NodeName,this.label8);
						this.Visit1(this.cl[n].NodeName,this.textBox3);
						BFS(this.cl[n].NodeName,this.weight,this.vvisitied);
					}											
				}
			}
			finally
			{
				
			}			

		}
		private int getnum(string v)
		{
			int t;
			for(t=0;t<i;t++)
				if(v==this.cl[t].NodeName)
					return t;
			return 21;
		}
		private void Visit1(string v,System.Windows.Forms.TextBox l)
		{
			if (l.Text=="")
				l.Text=v ;
			else
		        l.Text=l.Text+ ", " +v;
		}
		private void Visit1(string v1,string v2,System.Windows.Forms.TextBox l)
		{
			if (l.Text=="")
				l.Text=v1 +", "+ v2;
			else
				l.Text=l.Text+ ", "+","+v1+","+v2;
		}
		private void Visit2(string v1,System.Windows.Forms.Label l)
		{
			if (l.Text=="")
				l.Text=v1 ;
			else
				l.Text=l.Text+ ", "+v1;
		}
		private void Visit3(string v1,string v2,System.Windows.Forms.Label l)
		{
			if(l.Text=="")
				l.Text="("+v1+","+v2+")";
			else
				l.Text=l.Text+", "+"("+v1+","+v2+")";
		}

		private string getnext(string[,] w,bool[] visited,string v)
		{
			int n,m;
			for(n=0;n<i;n++)
					for(m=0;m<i;m++)
					if(w[n,m]!="0" && n==getnum(v) && visited[m]==false)
						return this.cl[m].NodeName;
//			for(n=0;n<20;n++)
//			{
//				if (visited[n]==false && n<i)
//					return this.cl[n].NodeName;
//			}
			return "none";
		}
		/// <summary>
		/// 求两点之间的权值
		/// </summary>
		/// <param name="w"></param>
		/// <param name="visited"></param>
		/// <param name="v1"></param>
		/// <param name="v2"></param>
		/// <returns></returns>
		private string getweight(string[,] w,bool[] visited,string v1,string v2)
		{
			int n,m;
			for(n=0;n<i;n++)
				for(m=0;m<i;m++)
					if(w[n,m]!="0" && n==getnum(v1) && m==getnum(v2) && visited[m]==false)
						return w[n,m];
			return "none";
		}
		private string getweight(string[,] w,string v1,string v2)
		{
			int n,m;
			for(n=0;n<i;n++)
				for(m=0;m<i;m++)
					if(w[n,m]!="0" && n==getnum(v1) && m==getnum(v2))
						return w[n,m];
			return "none";
		}
		/// <summary>
		/// 求与该点相连的权值最小的点
		/// </summary>
		/// <param name="w"></param>
		/// <param name="visited"></param>
		/// <param name="v"></param>
		/// <returns></returns>
		private string minweight(string[,] w,bool[] visited,string v)
		{
			bool[] visit11=new bool[20];
            int a;
			int[] minw=new int[100];
			string[] minn=new string[100];
			for (a=0;a<100;a++)
			{
				minw[a]=0;
			}
			for(a=0;a<20;a++)
			{
				visit11[a]=visited[a];
			}
			a=0;
			int b=0;
			string nowpoint;
			for(;(nowpoint=getnext(w,visited,v))!="none";)
			{
				visited[getnum(v)]=true;
				minw[a]=System.Convert.ToInt32(getweight(w,this.vvisitied,v,nowpoint));
				visited[getnum(nowpoint)]=true;
				minn[a++]=nowpoint;
			}
			int nowpoint1=minw[0];
			for (int d=0;d<a;d++)
			{
				if (minw[d]<nowpoint1)
				{
					nowpoint1=minw[d];
					b=d;
				}
			}
			for(a=0;a<20;a++)
			{
				visited[a]=visit11[a];
			}
			return minn[b];
		}
//		/// <summary>
//		/// 是否构成回路的函数
//		/// </summary>
//		/// <param name="points"></param>
//		/// <param name="v"></param>
//		/// <param name="w"></param>
//		/// <returns></returns>
//		private bool IsCircle(string[] points,string v,string[,] w)
//		{
//			for (int n=0;n<points.Length;n++)
//				if(getweight(w,this.vvisitied,v,points[n]!=0))
//					return false;
//			return true;
//		}

		private bool IsNone(bool[] visited)
		{
			for (int a=0;a<i;a++)
				if(visited[a]==false)
					return false;
			return true;
		}
		private void visitall(string v,string[,] w,bool[] visited)
		{
			string nowpoint;
			p++;
			visited[getnum(v)]=true;
//			this.allvisit[q++]=v;
			for(;(nowpoint=getnext(w,visited,v))!="none";)
			{
				visited[getnum(nowpoint)]=true;
				visited[getnum(v)]=true;
				this.allvisit[q++]=nowpoint;
				this.Visit1(v,nowpoint,this.textBox3);
				this.Visit2(nowpoint,this.label8);
			}
		}

		private void button5_Click(object sender, System.EventArgs e)
		{
//			for (x=0;x<i;x++)
//				this.vvisitied[x]=false;
			try
			{
				for(int n=0;n<i;n++)
					this.vvisitied[n]=false;
				this.vvisitied[0]=true;
				int z=i;
				string[] points=new string[i];
				points[0]=this.cl[0].NodeName;
				prim(points,this.vvisitied,this.weight,z);
				//			this.label2.Text=this.label3.Text+" 该最小生成树的权值为："+this.ssum;
				MessageBox.Show("成功！该最小生成树的权值为："+this.ssum,"消息",MessageBoxButtons.OK,MessageBoxIcon.Information);
				
				if(this.label3.Text=="")
					label3.Text=this.cl[0].NodeName+" 权值="+this.ssum;
				else
					label3.Text=label3.Text+" 权值="+this.ssum;
				this.button5.Enabled=false;
			}
			catch
			{
				this.label3.Text=null;
				MessageBox.Show("无法得到最小生成树,可能是因为这个图存在孤立的点或分支,请尝试重新输入边值","错误",MessageBoxButtons.OK,MessageBoxIcon.Warning);

			}

		}
		private void prim(string[] points,bool[] visited,string[,] weight,int z)
		{
			if (IsNone(visited)==true)			
				return;			
			z--;
			c++;
			string[] results=mweightinmanypoins(points,visited,weight,c,z);
            this.Visit3(results[0],results[1],this.label3);
			this.ssum=this.ssum+System.Convert.ToInt32(getweight(weight,results[0],results[1]));
			if(IsNone(visited)==false)
			{
				prim(points,visited,weight,z);
			}
		}
			

		
		/// <summary>
		/// 求与点集相连的权值最小的点
		/// </summary>
		/// <param name="points"></param>
		/// <param name="visited"></param>
		/// <param name="weight"></param>
		/// <returns>返回一个数组，有两个值，第一个是原点集中的点，第二个是与它连接的点</returns>
		private string[] mweightinmanypoins(string[] points,bool[] visited,string[,] weight,int c,int z)
		{
			string[] wweights=new string[100];
			string[] results=new string[2];   
			int a=0;
			string current1;
			int current2;
			int nowpoint=10000;
			for(a=0;a<c;a++)
			{
				if((current1=minweight(weight,visited,points[a]))!=null)
				{
					if(nowpoint>(current2=System.Convert.ToInt32(getweight(weight,current1,points[a]))))
					{
						nowpoint=current2;
						results[0]=points[a];
						results[1]=minweight(weight,visited,points[a]);
					}
				}
			}

//				wweights[b++]=current;
//			}
//			int nowpoint=System.Convert.ToInt32(getweight(weight,wweights[0],points[0]));
//			for(a=0;a<b;a++)
//			{
//				if (nowpoint>System.Convert.ToInt32(getweight(weight,wweights[a],points[a])))
//					nowpoint=System.Convert.ToInt32(getweight(weight,wweights[a],points[a]));
//				d=a;
//			}
//			results[0]=points[d];
//			results[1]=minweight(weight,visited,points[d]);
			visited[getnum(results[1])]=true;
			points[c]=results[1];
			return results;
		}
			 

			

	
	}
}