int** Matrix; //鄰接逆向矩陣 
   int* count=(int*) malloc(sizeof(int));
   int* finished = (int*) malloc(G->vexnum*sizeof(int));
   int* visited = (int*) malloc(G->vexnum*sizeof(int));
   if(finished==NULL||visited==NULL) return ERROR;
   memset(finished,0,G->vexnum*sizeof(int));
   memset(visited,0,G->vexnum*sizeof(int));
   *count =0; 
   DFSFinished(G, 0, visited, finished, count);//獲得遍歷完成序
   Matrix = get_list(G); //獲得鄰接逆向矩陣
    memset(visited,0,G->vexnum*sizeof(int));       
    get_connect(G,finished, visited, Matrix);
      free(finished);
      for(i=0;i<G->vexnum;i++)
        free(Matrix[i]);
        free(Matrix);
        free(count); 
    return OK;
}

int getArc(ALGraph* G,int v,int w)
{//初始條件：圖G存在，弧的起點w和終點v
//操作結果：返回弧的權值，要是弧不屬于圖G，則返回-1
   ArcNode* p =NULL; 
    for(p =G->vertices[v].firstarc;p!=NULL;p=p->nextarc)
        if(p->adjvex==w) return p->weight;
        return -1;
}

void DFSTree(ALGraph* G,int v,CSTree* T,int* visited)
{//從第v個頂點出發深度優先遍歷圖G，建立以T為根的生成樹 
  ArcNode* h=NULL;
  CSTree p,q; 
  int i,w; 
  int first=1; 
  visited[v] =1;
  for(h = G->vertices[v].firstarc;h!=NULL;h=h->nextarc)
  { 
    w= h->adjvex; 
   
    if(!visited[w]) 
    {
      p=(CSTree) malloc(sizeof(CSNode)) ; //分配孩子 結點 
      p->data = w;
      p->firstchild =NULL;
      p->nextsibing = NULL; 
      if(first)
      {
        (*T)->firstchild =p;
         first =0;      
      }else
      {
       q->nextsibing = p;    
      }  
      q=p;  
      DFSTree(G,w,&q,visited);         
    }      
  }    
     
} 
void DFSForest(ALGraph* G,CSTree* T)
{//建立無向圖G的深度優先生成森林
//（最左）孩子（右）兄弟鏈表T 
  int v;
  CSTree p,q;
  int* visited= (int*) malloc(sizeof(int)); 
  *T=NULL; 
  for(v=0;v<G->vexnum;v++)
  visited[v] =0;
  for(v=0;v<G->vexnum;v++)
  if(!visited[v])
  {
    p=(CSTree) malloc(sizeof(CSNode));     
    p->data = v;
    p->firstchild =NULL;
    p->nextsibing = NULL;
    if(!*T)
    {
      *T=p;       
    }else
    {
      q->nextsibing = p;     
    }     
    q=p;
    DFSTree(G,v,&p,visited); 
  }        
} 

void ForestTraverse(CSTree* T) 
{  CSTree temp; 
  if(*T!=NULL)
  { printf("%d ",(*T)->data ); 
    if((*T)->firstchild!=NULL)
    {
   
     ForestTraverse(&(*T)->firstchild);
     temp =  (*T)->firstchild;          
     while(temp->nextsibing!=NULL)
     {
       ForestTraverse(&temp->nextsibing); 
       temp=temp->nextsibing;                             
     } 
           
    }
  }     
} 
Status MiniSpanTree_PRIM(ALGraph* G,VertexType data)
{//初始條件：無向圖G存在，data是與頂點有相同特征的頂點
//操作結果：輸出G的最小生成樹
 
//記錄從頂點集U到V-U的代價最小的邊的輔助數組定義：
 struct 
 {
   int adjvex;//存儲該邊依附在U中的頂點
   int lowcost;//表示V-U中的一個頂點到達U中的最短路徑,也就是<i,closege[i].adjvex>
 }closedge[MAX_VERTEX_NUM]; 
 int mincost =MAX; //先初始化最小的權值為最大值，在不斷更新。
 int v=LocalVex(G,data);
 int i; 
 ArcNode* p=NULL; 
 int count=1;  //U中頂點的個數
 int k=0; //V-U中最小的cost的下標
 if(v==-1) return ERROR;
 //closedge 的初始化
 for(i=0;i<G->vexnum;i++)
 {
   closedge[i].adjvex = v;
   closedge[i].lowcost = MAX;
 }
 for(p=G->vertices[v].firstarc;p!=NULL;p=p->nextarc)
 {
   closedge[p->adjvex].adjvex = v; 
   closedge[p->adjvex].lowcost = p->weight; //最小值為它們之間的弧
 } 
 closedge[v].lowcost=0;  //初始化U={v}

 
 while(count<G->vexnum)
  {   
      mincost =MAX;//V-U中的最小cost
          
      for( i=0;i<G->vexnum;i++)
      if(closedge[i].lowcost && mincost>closedge[i].lowcost) //在V-U中找出mincost
      {
        k=i;
        mincost = closedge[i].lowcost;
      }
      printf("%s %d %s,",G->vertices[closedge[k].adjvex].data,mincost,G->vertices[k].data); //輸出最小生成樹
      closedge[k].lowcost=0; //加入到U中
      //找到之后，在V-U中修改與k點相連接的相應closedge的值 
      for(p=G->vertices[k].firstarc;p!=NULL;p=p->nextarc)
      {
          if(closedge[p->adjvex].lowcost && p->weight<closedge[p->adjvex].lowcost)
        {
            closedge[p->adjvex].lowcost = p->weight;
            closedge[p->adjvex].adjvex = k;
        }
      }
   ++count;
 }
 return OK;
}



Status MiniSpanTree_Kruskal(ALGraph* G)
{//初始條件：無向圖G存在,data是與頂點有相同特征的頂點
//操作結果：輸出G的最小生成樹

/*從E中選擇代價最小的
 邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到
 T中，否則舍去此邊而選擇下一條代價最小的邊
 具體通過并查集和優先隊列來實現
*/
    int i=0;
    ArcNode* p=NULL; 
    Edge* t; 
    Edge* temp; 
    int count =0;//加入的邊條數 
    priority_queue* pq = (priority_queue*)malloc(sizeof(priority_queue)); //優先隊列
    UFSet* set = (UFSet*) malloc(G->vexnum*sizeof(UFSet)); //并查集
    InitUFSet(set,G->vexnum);//并查集初始化
    init_priority_queue(pq);//優先隊列初始化
    //初始化：把所有弧都加入到優先隊列中
    for(i=0;i<G->vexnum;i++)
    {
        for(p=G->vertices[i].firstarc;p!=NULL;p=p->nextarc)
        {  // t= (Edge*)InitEdge(i,p->adjvex,p->weight);
             t=(Edge*) malloc (sizeof(Edge)); 
             t->v=i;
             t->w=p->adjvex;
             t->weight = p->weight;   
            insert_priority_queue(pq,t);      
        }
    }
  
    
    while(!isEmpty(pq)&&count < G->vexnum-1)
    {
      temp = extract_min(pq); //獲取權值最小的邊
      if(UFSetFind(set,temp->v)!=UFSetFind(set,temp->w)) //邊上的兩個頂點在不同的連通分量上
      {
        Union(set,temp->v,temp->w);//加入該邊
        ++count; //邊數加1
        printf("%s %d %s,",G->vertices[temp->v].data,temp->weight,G->vertices[temp->w].data);
      }        
      free(temp); 
    }
    Destory_priority_queue(pq);// 釋放優先隊列 
    free(set); //釋放set
    return OK;
}

Status DFSArticul(ALGraph* G,int v,int* count,int* visited,int* low)
{//從第v個頂點出發深度優先遍歷圖G，查找并輸出關節點，
//count為第幾個訪問，visited記錄頂點初訪問到的次序
 //   low[v] = min{visited[v],low[w],visited[k]};w為沒訪問過的鄰接點，k為訪問過的
  ArcNode* p=NULL; 
  int w; 
  int min =++(*count); //記錄v頂點的low[v]最小值
  visited[v] = *count;//v是第count個訪問的結點
  for( p=G->vertices[v].firstarc;p!=NULL;p=p->nextarc)
  { 
    w= p->adjvex ;
    if(visited[w]==0) //沒訪問過的鄰接點
    {
      DFSArticul(G,w,count,visited,low);
      if(low[w]<min) min = low[w];
      if(low[w]>=visited[v]) printf("%s ",G->vertices[v].data); //輸出關節點
      //只要有回邊，則low[w]<visited[v]
    }
    else if(visited[w]<min)
     min = visited[w];
  }
  low[v] = min;
  return OK;
}
 
Status FindArticul(ALGraph* G)
{//連通圖G以鄰接表作為存儲結構，查找并輸出G上的全部關節點
  int i; 
  ArcNode* p=G->vertices[0].firstarc;//設定鄰接表上0號頂點為生成樹的根
  int v=p->adjvex; //根的第一個孩子結點
  int* count = (int*) malloc(sizeof(int));  
  int* visited =( int* )malloc(G->vexnum*sizeof(int));
  int* low = (int*) malloc(G->vexnum*sizeof(int));
  visited[0] =1; //設定鄰接表上0號頂點為生成樹的根
  for(i=1;i<G->vexnum;i++)visited[i]=0;
  *count =1;
  DFSArticul(G,v,count,visited,low);//從v點出發深度優先查找關節點
  if(*count<G->vexnum)
  {
      printf("%s ",G->vertices[0].data);//輸出根結點
      while(p->nextarc!=NULL) //根的其它孩子結點
      {
          p = p->nextarc;
          if(!visited[p->adjvex])
          DFSArticul(G,p->adjvex,count,visited,low);
      }
  }
  free(visited);
  free(low);
  free(count); 
  return OK;
}
 
Status TopologicalSort(ALGraph* G)
{//有向圖G采用鄰接表存儲結構，若G無回路，則輸出G的
//頂點的一個拓撲序列并返回0，否則返回-1    
    int i;
    ArcNode* p; 
    int* v=(int*) malloc(sizeof(int));//出棧的頂點
    stack* s = (stack*) malloc(sizeof(stack));
    //存儲各頂點的一個入度數組
    int* indegree = (int*) malloc (G->vexnum*sizeof(int));
    int count =0;//對輸出頂點計數
    if(indegree==NULL) return ERROR;
    memset(indegree,0,G->vexnum*sizeof(int));//各頂點入度初始化為0
    //求頂點的入度
    for (i=0;i<G->vexnum;i++)
    {
        for(p=G->vertices[i].firstarc;p!=NULL;p=p->nextarc)
            indegree[p->adjvex]++;
    }  
    InitStack(s);
    //入度為0的點，進棧
    for( i=0;i<G->vexnum;i++)
    {
       if(!indegree[i])
       Push(s,i);
    }
    
    while(!StackEmpty(s))
    {
      Pop(s,v); //通過v獲得，出棧的頂點
      count++;
      printf("%s ",G->vertices[*v].data); //輸出拓撲排序
      for(p=G->vertices[*v].firstarc;p!=NULL;p=p->nextarc)
          if(!--indegree[p->adjvex]) Push(s,p->adjvex);
    }
    DestroyStack(s);
    free(indegree);
    if(count<G->vexnum) return -1; //有環
    return OK;
}
 
Status TopologicalOrder(ALGraph* G,stack* T,int* ve)
{//有向網G采用鄰接表存儲結構，求各頂點事件的最早發生時間ve
//T為拓撲序列頂點棧，s為零入度頂點棧
    int i;
    ArcNode* p=NULL;
    int* v=(int*) malloc(sizeof(int));//出棧的頂點 
  //存儲各頂點的一個入度數組
    int* indegree = (int*) malloc (G->vexnum*sizeof(int));
    int count =0;//對輸出頂點計數
    stack* s = (stack*) malloc(sizeof(stack));
    if(indegree==NULL) return -1;
    memset(indegree,0,G->vexnum*sizeof(int));//各頂點入度初始化為0
    //求頂點的入度
    for( i=0;i<G->vexnum;i++)
    {
        for(p=G->vertices[i].firstarc;p!=NULL;p=p->nextarc)
            indegree[p->adjvex]++;
    }
    
    InitStack(s);
    //入度為0的點，進棧
    for(i=0;i<G->vexnum;i++)
    {
       if(!indegree[i])
       Push(s,i);
    }
    
    InitStack(T);
    while(!StackEmpty(s))
    {
      Pop(s,v); //通過v獲得，出棧的頂點
      Push(T,*v); //*v加入到拓撲序列頂點棧中
      count++;
      for(p=G->vertices[*v].firstarc;p!=NULL;p=p->nextarc)
      {
        if(!--indegree[p->adjvex]) Push(s,p->adjvex);
        // <v,p->adjvex>
        if(ve[*v]+p->weight > ve[p->adjvex])
          ve[p->adjvex] =ve[*v]+p->weight;
      }  
    }
    DestroyStack(s);
    free(indegree);
    if(count<G->vexnum) return ERROR; //有環
    return OK;
}

Status CriticalPath(ALGraph* G)
{//G為有向網，輸出G的各項關鍵活動
  int i,t,k;
  int ee;//弧的最早開始
  int el;//弧的最遲發生
  int* j=(int*) malloc(sizeof(int));//出棧用的 
   ArcNode* p=NULL; 
  stack* T = (stack*) malloc(sizeof(stack));//T為拓撲序列頂點棧
  int* ve =(int*) malloc(G->vexnum*sizeof(int));//頂點的最早開始時間
  int* vl =(int*) malloc(G->vexnum*sizeof(int));//頂點的最遲開始時間
  if(ve==NULL||vl==NULL) return -1;//申請空間失敗
  memset(ve,0,G->vexnum*sizeof(int));//ve都初始化為0
  
  if(TopologicalOrder(G,T,ve)==ERROR) return ERROR; //有環
  
  for(t=0;t<G->vexnum;t++)
   vl[t]=ve[G->vexnum-1];//最遲開始時間都初始化為ve[G.vexnum-1]
  
 
  //按拓撲逆序求各頂點的最遲開始時間vl
   while(!StackEmpty(T))
  { 
    Pop(T,j);
    for(p=G->vertices[*j].firstarc;p!=NULL;p=p->nextarc)
    { 
       k =p->adjvex;
       //<j,k>
       if(vl[k]-p->weight<vl[*j])
       vl[*j] = vl[k]-p->weight ;
    }
  }
 
 
   for(i=0;i<G->vexnum;i++)
     for(p=G->vertices[i].firstarc;p;p=p->nextarc)
     {
        k =p->adjvex;
        ee=ve[i]; el=vl[k]-p->weight;
        if(ee==el) 
        printf("%s %d %s ,",G->vertices[i].data,p->weight,G->vertices[k].data);//輸出關鍵路徑
     }
     DestroyStack(T);
     free(ve);
     free(vl);
     free(j); 
     return OK; 
}