void Dijkstra(int n,int[] Distance,int[] iPath)
{
int MinDis,u;
int i,j;
//從鄰接矩陣復(fù)制第n個(gè)頂點(diǎn)可以走出的路線，就是復(fù)制第n行到Distance[]
for(i=0;i<VerNum;i++)
{
   Distance[i]=Arc[n,i];
   Visited[i]=0;
}//第n個(gè)頂點(diǎn)被訪問(wèn)，因?yàn)榈趎個(gè)頂點(diǎn)是開(kāi)始點(diǎn)
Visited[n]=1;
//找到該頂點(diǎn)能到其他頂點(diǎn)的路線、并且不是開(kāi)始的頂點(diǎn)n、以前也沒(méi)走過(guò)。
//相當(dāng)于尋找u點(diǎn)，這個(gè)點(diǎn)不是開(kāi)始點(diǎn)n
for(i=0;i<VerNum;i++)
{
   u=0;
   MinDis=No;
   for(j=0;j<VerNum;j++)
    if(Visited[j] == 0&&(Distance[j]<MinDis))
    {
     MinDis=Distance[j];
     u=j;
    }
//如范例P1871圖G6，Distance=[No,No,10,No,30,100]，第一次找就是V2，所以u(píng)=2
//找完了，MinDis等于不連接，則返回。這種情況類(lèi)似V5。
   if(MinDis==No) return ;
//確立第u個(gè)頂點(diǎn)將被使用，相當(dāng)于Arc[v,u]+Arc[u,w]中的第u頂點(diǎn)。
   Visited[u]=1;
//尋找第u個(gè)頂點(diǎn)到其他所有頂點(diǎn)的最小路，實(shí)際就是找Arc[u,j]、j取值在[0，VerNum]。
//如果有Arc[i,u]+Arc[u,j]<Arc[i,j]，則Arc[i,j]=Arc[i,u]+Arc[u,j]<Arc[i,j]
//實(shí)際中，因?yàn)镈istance[]是要的結(jié)果，對(duì)于起始點(diǎn)確定的情況下，就是：
//如果(Distance[u] + Arc[u,j]) <= Distance[j] 則：
//Distance[j] = Distance[u] + Arc[u, j]；
//而iPath[]保存了u點(diǎn)的編號(hào)；
//同理：對(duì)新找出的路線，要設(shè)置Visited[j]=0，以后再找其他路，這個(gè)路可能別利用到。例如V3
   for(j=0;j<VerNum;j++)
    if(Visited[j]==0&&Arc[u,j]<No&&u!= j) 
    {
     if ((Distance[u] + Arc[u,j]) <= Distance[j])
     {
      Distance[j] = Distance[u] + Arc[u, j];
      Visited[j]=0;
      iPath[j] = u;
     }
    }
}
}

//輔助函數(shù)

void Prim()
{
int i,m,n=0;
for(i=0;i<VerNum;i++) 
{
   Visited[i]=0;
   T[i]=new TreeNode();
   T[i].Text =V[i];
}
Visited[n]++;
listBox1.Items.Add (V[n]); 
while(Visit()>0)
{
   if((m=MinAdjNode(n))!=-1)
   {
    T[n].Nodes.Add(T[m]); 
    n=m;
    Visited[n]++;
   }
   else
   {
    n=MinNode(0);
    if(n>0) T[Min2].Nodes.Add(T[Min1]); 
    Visited[n]++;
   }
   listBox1.Items.Add (V[n]); 
}
treeView1.Nodes.Add(T[0]); 
}
void TopoSort()
{
int i,n;
listBox1.Items.Clear(); 
Stack S=new Stack();
for(i=0;i<VerNum;i++)
   Visited[i]=0;
for(i=VerNum-1;i>=0;i--)
   if(InDegree(i)==0)
   {
    S.Push(i);
    Visited[i]++;
   }
while(S.Count!=0)
{
   n=(int )S.Pop();
   listBox1.Items.Add (V[n]); 
   ClearLink(n);
   for(i=VerNum-1;i>=0;i--)
    if(Visited[i]==0&&InDegree(i)==0)
    {
     S.Push(i);
     Visited[i]++;
    }
}
}
void AOETrave(int n,TreeNode TR,int w)
{
int i,w0;
if(OutDegree(n)==0) return;
for(i=0;i<VerNum;i++)
   if((w0=Arc[n,i])!=0)
   {
    listBox1.Items.Add (V[i]+"\t"+(w+w0).ToString()+"\t"+i.ToString()+"\t"+n.ToString());
    TreeNode T1=new TreeNode();
    T1.Text =V[i]+" [W="+(w+w0).ToString()+"]"; 
    TR.Nodes.Add(T1); 
    AOETrave(i,T1,w+w0);
   }
}
void AOE()
{
int i,w=0,m=1;
TreeNode T1=new TreeNode();
for(i=0;i<VerNum;i++)
{
   Visited[i]=0;
}
T1.Text =V[0];
listBox1.Items.Add ("雙親表示法顯示這個(gè)生成樹(shù)："); 
listBox1.Items.Add ("V\tW\tID\tPID");
for(i=0;i<VerNum;i++)
{
   if((w=Arc[0,i])!=0)
   {
    listBox1.Items.Add (V[i]+"\t"+w.ToString()+"\t"+i.ToString()+"\t0");
    TreeNode T2=new TreeNode();
    T2.Text=V[i]+" [W="+w.ToString()+"]";
    AOETrave(i,T2,w);
    T1.Nodes.Add (T2); 
    listBox1.Items.Add("\t\t樹(shù)"+m.ToString());
    m++;
   }
}
treeView1.Nodes.Clear(); 
treeView1.Nodes.Add (T1);
}
int IsZero()
{
int i;
for(i=0;i<VerNum;i++)
   if(LineIsZero(i)>=0) return i;
return -1;
}
int LineIsZero(int n)
{
int i;
for(i=0;i<VerNum;i++)
   if (Arc[n,i]!=0) return i;
return -1;
}
void DepthTraverse()
{
int i,m;
for(i=0;i<VerNum;i++)
{
   Visited[i]=0;
   T[i]=new TreeNode();
   T[i].Text =V[i];
   R[i]=0;
}
while((m=IsZero())>=0)
{
   if(Visited[m]==0) 
   {
    listBox1.Items.Add (V[m]);
    R[m]=1;
   }
   Visited[m]++;
   DTrave(m);
}
for(i=0;i<VerNum;i++)
{
   if(R[i]==1)
    treeView1.Nodes.Add (T[i]); 
}
}
void DTrave(int n)
{
int i;
if (LineIsZero(n)<0) return;
for(i=VerNum-1;i>=0;i--)
   if(Arc[n,i]!=0)
   {
    Arc[n,i]=0;
    Arc[i,n]=0;
    if(Visited[i]==0)
    {
     listBox1.Items.Add (V[i]);
     T[n].Nodes.Add (T[i]); 
     R[i]=0;
    }
    Visited[i]++;
    DTrave(i);
   }
}
void BreadthTraverse()
{
int i,m;
for(i=0;i<VerNum;i++)
{
   Visited[i]=0;
   T[i]=new TreeNode();
   T[i].Text =V[i];
   R[i]=0;
}
while((m=IsZero())>=0)
{
   if(Visited[m]==0) 
   {
    listBox1.Items.Add (V[m]);
    R[m]=1;
   }
   Visited[m]++;
   BTrave(m);
}
   for(i=0;i<VerNum;i++)
{
   if(R[i]==1)
    treeView1.Nodes.Add (T[i]); 
}
}
void BTrave(int n)
{
int i;
Queue Q=new Queue();
Q.Enqueue(n);
while(Q.Count!=0)
{
   for(i=0;i<VerNum;i++)
   {
    if(Arc[n,i]!=0)
    {
     Arc[n,i]=0;
     Arc[i,n]=0;
     if(Visited[i]==0)
     {
      listBox1.Items.Add(V[i]); 
      T[n].Nodes.Add (T[i]); 
      R[i]=0;
     }
     Visited[i]++;
     Q.Enqueue(i);
    }
   }
   n=(int )Q.Dequeue(); 
}
}
int MinNode(int vn)
{
int i,j,n,m,Min=No;
n=-1;m=-1;
for (i=vn;i<VerNum;i++)
   for(j=0;j<VerNum;j++)
    if(Arc[i,j]!=No&&Arc[i,j]<Min&&Visited[i]==0&&Visited[j]==1)
    {
     Min=Arc[i,j];n=i;m=j;
    }
Min1=n;Min2=m;
return n;
}
int MinAdjNode(int n)
{
int i,Min,m;
Min=No;m=-1;
for(i=0;i<VerNum;i++)
   if(Arc[n,i]!=No&&Visited[i]==0&&Min>Arc[n,i]&&Visited[n]==1)
   {
    Min=Arc[n,i];m=i;
   }
return m;
}
int Visit()
{
int i,s=0;
for(i=0;i<VerNum;i++)
   if(Visited[i]==0) s++;
return s;
}