#include "stdafx.h"
#define MAX 999999
trid_tree* T; //字母樹 
Status initALGraph(ALGraph* G)
{
  //圖的初始化，是針對有向圖的，從文件ALGraph.txt中讀入，構(gòu)造圖的鄰接表,數(shù)據(jù)都是從1開始
   int n;//表示與結(jié)點相接的結(jié)點總數(shù);
   VertexType data; //該結(jié)點的信息 
   int vexnum=0;//圖的當(dāng)前頂點總數(shù)
   int arcnum=0 ;//圖的弧數(shù)總數(shù)
   int j;    
   ArcNode* p =NULL;
   ArcNode* temp = NULL;
   FILE* fp = fopen("ALGraph.txt","r");
   T= (trid_tree*) malloc(sizeof(trid_tree)); //構(gòu)造字母樹T
   init_trid_tree(T);//并初始化 
   
   if(fp==NULL)return ERROR; //文件打開失敗，返回-1
   fscanf(fp,"%d",&G->kind);
   printf("%d\n",G->kind);
   while(fscanf(fp,"%s",data)!=EOF)
   { printf("%s\n",data);
     vexnum=insert(T,data); //由頂點信息映射到數(shù)組下標(biāo)
     if(vexnum>=MAX_VERTEX_NUM)return ERROR;
     G->vertices[vexnum].firstarc=NULL;
     strcpy(G->vertices[vexnum].data,data);
     fscanf(fp,"%d",&n);
     arcnum+=n;   
     printf("%d ",n);      
     for( j=0;j<n;j++)
     { 
      p =(ArcNode*) malloc(sizeof(ArcNode));
      if(p==NULL) return ERROR; //申請空間失敗
      fscanf(fp," %d %s",&p->weight,data);
        printf(" %d %s",p->weight,data); 
      
      p->adjvex = insert(T,data);
      p->nextarc =NULL;
      temp =(G->vertices[vexnum]).firstarc;
      (G->vertices[vexnum]).firstarc=p;
      p->nextarc = temp;
     }
     printf("\n"); 
   }
   G->arcnum =arcnum;
   G->vexnum=T->vexnum; //0--T->vexnum-1
   return OK;
}

Status DestroyALGraph(ALGraph* G)
{//對圖G進行空間的釋放，從此之后就在也不能用G了
  int i=0;
  ArcNode* p=NULL;
  for(;i<G->vexnum;i++)
  {
      while(G->vertices[i].firstarc!=NULL)
      {
          p=G->vertices[i].firstarc;
          G->vertices[i].firstarc=G->vertices[i].firstarc->nextarc;
          free(p);
      }
  }
  G->arcnum=0;
  G->vexnum=0;
  free(G); 
  return OK;
}
 
int LocalVex(ALGraph* G,VertexType data)
{//初始條件：圖G存在，data和G中有頂點有相同的特征
//若G中存在頂點data，則返回該頂點在圖中的位置，否則返回其它信息
 int xiabiao = find(T,data);
 if(xiabiao==-1) return -1; //不存在該頂點
 return xiabiao ;
}

int LocalArc(ALGraph* G,VertexType v_data,VertexType w_data)
{//初始條件：圖G存在，由<v_data,w_data>確定的弧<v,w>存在于圖G中
//操作結(jié)果：返回<v,w>的權(quán)值，大于0，要是不存在該弧，則返回-1
 int v =LocalVex(G,v_data);
 int w = LocalVex(G,w_data);
 ArcNode* p=NULL; 
 if(w==-1||v==-1) return -1;
 for(p=G->vertices[v].firstarc;p!=NULL;p=p->nextarc)
     if(p->adjvex==w) return p->weight;
   return -1;
}

Status DFSTraverse(ALGraph* G,int* visited)
{//初始條件：圖G存在，v是G中的某個頂點
//操作結(jié)果：從頂點v起，進行深度優(yōu)先遍歷
    int i; 
    for(i=0;i<G->vexnum;i++)visited[i]=0;
    for(i=0;i<G->vexnum;i++)
        if(!visited[i])
        {
         DFS(G,G->vertices[i].data,visited);
         printf("\n");
        }
    return OK;
}

Status DFS(ALGraph* G, VertexType data,int* visited)
{//初始條件：圖G存在，v是G中的某個頂點，visited數(shù)組是圖中頂點的訪問情況
//操作結(jié)果：從頂點v開始，對圖G進行一次深度優(yōu)先遍歷,同時把遍歷到的頂點的visited置為true;
  ArcNode* p=NULL; 
  int v = find(T,data);
  if(v<=-1) return -1;
  visited[v]=1;
  printf("%s ",G->vertices[v].data);
  for(p=G->vertices[v].firstarc;p!=NULL;p=p->nextarc)
   //對v的尚未訪問的鄰接頂點，遞歸調(diào)用DFS
   if(!visited[p->adjvex]) DFS(G,G->vertices[p->adjvex].data,visited);
  
   return OK;
}
Status BFSTraverse(ALGraph* G,int* visited)
{//初始條件：圖G存在，visited數(shù)組是圖中頂點的訪問情況
//操作結(jié)果：從頂點1起，對全圖G進行廣度優(yōu)先遍歷,同時把遍歷到的頂點的visited置為true;
    int i; 
    for(i=0;i<G->vexnum;i++)visited[i]=0;
    for(i=0;i<G->vexnum;i++)
    if(!visited[i])
    {
     BFS(G,i,visited);
     printf("\n");
    }
  
return OK;
}

Status BFS(ALGraph* G,int v,int* visited)
{//初始條件：圖G存在，v是圖G中的某個頂點，visited數(shù)組是圖中頂點的訪問情況
//操作結(jié)果：從頂點v開始，對圖進行一次遍歷，同時把遍歷到的頂點的visited置為true;
  ArcNode* p=NULL; 
  int* w = (int*) malloc(sizeof(int));
  LinkQueue* Q =(LinkQueue*)malloc(sizeof(LinkQueue)); //定義一個隊列
  InitQueue(Q); //并初始化
  EnQueue(Q,v); 
  while(!QueueEmpty(Q))
  {
    DeQueue(Q,w); // 若隊列不空，則刪除Q的隊頭元素，并用w返回隊頭元素的值
    if(!visited[*w])
    {
      visited[*w]=1;
      printf("%s ",G->vertices[*w].data);
      for(p=G->vertices[*w].firstarc;p!=NULL;p=p->nextarc)
         if(!visited[p->adjvex])
          EnQueue(Q,p->adjvex);
       
    }
  }
  free(w);
  DestroyQueue(Q); //銷毀隊列 
  return OK;
}

Status InsertVex(ALGraph* G, VertexType v)
{//初始條件：圖G存在，v和圖中的頂點有相同特征
//操作結(jié)果： 在圖G中增加新頂點v，字母樹中加入該頂點的信息
 if(G->vexnum>=MAX_VERTEX_NUM-1||G->vexnum<0) return ERROR; //圖項點數(shù)已滿
 
 if( LocalVex(G,v)!= -1) return OK; //該頂點已在圖中
  strcpy(G->vertices[G->vexnum].data,v);
  G->vertices[G->vexnum].firstarc = NULL;
   ++G->vexnum;
  insert(T,v); //加入到字母樹
  return OK;
}


Status DeleteVex(ALGraph* G, VertexType data)
{//初始條件：圖G存在，data是G中的某個頂點的信息
//操作結(jié)果：刪其除G中的頂點及與相關(guān)的弧,刪除它在字母樹的信息，并做相應(yīng)調(diào)整
    ArcNode* p =NULL;
    int xiabiao,i; 
    int n=0; //出度為0
    if(G->vexnum<=0) return ERROR;
    xiabiao = LocalVex(G,data);
    if(xiabiao==-1) return ERROR; //表示該頂點不存在
    for(p=G->vertices[xiabiao].firstarc;p!=NULL;++n) //銷毀鄰接表
    {
        G->vertices[xiabiao].firstarc = p->nextarc ;
        free(p);
        p=G->vertices[xiabiao].firstarc;
    }
    for(i=xiabiao;i<G->vexnum-1;i++) //圖的映射數(shù)組中其它頂點補齊
    {       
       strcpy(G->vertices[i].data,G->vertices[i+1].data);
       G->vertices[i].firstarc =G->vertices[i+1].firstarc;
    }
    //刪除字母樹中num值為xiabiao的頂點
    delete_node(T,G->vertices[xiabiao].data);
    // 字母樹中num值比xiabiao大的都減1
    adjust_num(T->root,xiabiao);
      
    G->vertices[G->vexnum-1].firstarc = NULL; //最后一個頂點的firstarc為空
    // 頂點數(shù)-1,弧數(shù)減出度
    --G->vexnum;
    G->arcnum -= n;
    return OK;
}

int VexOutDegree(ALGraph* G,VertexType data)
{//初始條件：圖G存在，data和G中有頂點有相同的特征
//操作結(jié)果:返回頂點data的出度，
  ArcNode* p =NULL;
  int xiabiao; 
  int n=0; //出度為0
  if(G->vexnum>MAX_VERTEX_NUM-1||G->vexnum<=0) return ERROR; //圖不存在
  xiabiao = LocalVex(G,data);
  if(xiabiao==-1) return -2; //表示該頂點不存在
  for(p=G->vertices[xiabiao].firstarc;p!=NULL;p=p->nextarc,++n);
  return n;  
}

int VexInDegree(ALGraph* G,VertexType data)
{//初始條件：圖G存在，data和G中有頂點有相同的特征
//操作結(jié)果：返回頂點data的入度
    int i,n=0; //入度為0
    ArcNode* p=NULL; 
    for(i=0;i<G->vexnum;i++)
    {
      for(p=G->vertices[i].firstarc;p!=NULL;p=p->nextarc )
          if(strcmp(G->vertices[p->adjvex].data,data)==0) 
              ++n;
    }
    return n;
}

int isArc(ALGraph* G,VertexType v_data,VertexType w_data)
{//初始條件：圖G存在，v_data，w_data和G中的頂點有相同的特征
//操作結(jié)果：若圖G中存在<v,w>則返回 true,否則返回false
 int v = LocalVex(G,v_data);
 int w = LocalVex(G,w_data);
 ArcNode* p=NULL; 
 if(v==-1||w==-1) return 0;//弧的兩個頂點不在圖G中
 for(p =G->vertices[v].firstarc;p!=NULL;p=p->nextarc)
   if(p->adjvex==w) return 1;
   return 0;
}

int InsertArc(ALGraph* G,VertexType v_data,VertexType w_data,int weight)
{
  //初始條件：圖G存在，v和w是G中的兩個頂點,其信息值分別為v_data和w_data
 //操作結(jié)果：在G中增加弧<v,w>,且弧的權(quán)值是weight,若G是無向的，則還要增添對稱弧<w,v>
 ArcNode* p; 
 ArcNode* temp; 
 int v=LocalVex(G,v_data);
 int w=LocalVex(G,w_data);
 if(v==-1||w==-1) return -1; //頂點不在圖G中
 if(isArc(G,v_data,w_data)) return 0; //圖G中已經(jīng)存在<v,w>這條弧了 
 temp=G->vertices[v].firstarc;
 p =(ArcNode*) malloc(sizeof(ArcNode));
 if(p==NULL) return -2; //申請空間失敗
 p->weight = weight;
 p->adjvex = w;
 G->vertices[v].firstarc = p;
 p->nextarc = temp ;
 ++G->arcnum;
 if(G->kind==2||G->kind==3) //無向圖或無向網(wǎng)
 {  
    
    p =(ArcNode*) malloc(sizeof(ArcNode));
    if(p==NULL) return -2; //申請空間失敗
     p->weight = weight;
     p->adjvex = v;
     temp=G->vertices[w].firstarc;
     G->vertices[w].firstarc = p;
     p->nextarc = temp ;
     ++G->arcnum;
 }
 return 0;
}

Status updateArc(ALGraph* G,VertexType v_data,VertexType w_data,int weight)
{//初始條件：圖G存在，v_data，w_data和G中的頂點有相同的特征，且存在<v,w>這條弧
//操作結(jié)果：把<v,w>這條弧的權(quán)值改為weight,成功返回0，失敗返回-1
  ArcNode* p; 
  int v=LocalVex(G,v_data);
  int w=LocalVex(G,w_data);
  if(!isArc(G,v_data,w_data)) return ERROR; //不存在該弧
  for(p=G->vertices[v].firstarc;p!=NULL;p=p->nextarc)
    if(p->adjvex==w) 
    {
        p->weight = weight;
        return OK;
    }

   if(G->kind==2||G->kind==3) //無向圖或無向網(wǎng)
  {
    for(p=G->vertices[w].firstarc;p!=NULL;p=p->nextarc)
    if(p->adjvex==v) 
    {
        p->weight = weight;
        return OK;
    }
  }
   return ERROR;
}

Status DeleteArc(ALGraph* G,VertexType v_data,VertexType w_data)
{//初始條件：圖G存在，v和w是G中的兩個頂點,其信息值分別為v_data和w_data
//操作結(jié)果：在G中，刪除弧<v,w>,若G是無向的，則還要刪除對稱弧<w,v>
  ArcNode* p=NULL; 
  ArcNode* before =NULL;
  int v=LocalVex(G,v_data);
  int w=LocalVex(G,w_data);
  if(!isArc(G,v_data,w_data)) return ERROR; //不存在該弧
   
   for(p=G->vertices[v].firstarc;p!=NULL;before=p,p=p->nextarc)
    if(p->adjvex==w) 
    {
       if(p->nextarc==NULL)
         before->nextarc = NULL;
       else     
        before->nextarc = p->nextarc;    
        free(p);
        --G->arcnum; 
        return OK;
    }
   if(G->kind==2||G->kind==3) //無向圖或無向網(wǎng)
   {
     for(p=G->vertices[w].firstarc;p!=NULL;before=p,p=p->nextarc)
     if(p->adjvex==v) 
     {
        if(p->nextarc==NULL)
         before->nextarc = NULL;
        else       
         before->nextarc = p->nextarc;       
        free(p);
        --G->arcnum; 
        return OK;
     }
   }
   return ERROR;
}

Status DFSFinished(ALGraph* G, int v, int visited[], int finished[], int* count)
{//初始條件：圖G存在,且是連通圖，頂點v在G中，finished向量和visited向量，count值；
//從頂點v出發(fā)，正向深度優(yōu)先遍歷，計算遍歷結(jié)束序，記入finished向量中；
  ArcNode* p=NULL; 
  visited[v]=1;
  for(p =G->vertices[v].firstarc;p!=NULL;p=p->nextarc)
  {
      if(!visited[p->adjvex])
          DFSFinished(G, p->adjvex,visited,finished,count); 
  }
  finished[(*count)++]=v;
  return OK;
}

int** get_list(ALGraph* G)
{//初始條件：存在圖G，是用鄰接表存儲的
//操作結(jié)果：返回逆向的鄰接矩陣，
    int i,j; 
    ArcNode* p=NULL; 
    int**  Matrix =(int**) malloc(G->vexnum*sizeof(int*)) ;
    for(j=0;j<G->vexnum;j++)
    {
      Matrix[j] = (int*) malloc(G->vexnum*sizeof(int));
      memset(Matrix[j],0,G->vexnum*sizeof(int));
    }
    for(i=0;i<G->vexnum;i++)
    {
        for(p =G->vertices[i].firstarc;p!=NULL;p=p->nextarc)
            Matrix[p->adjvex][i]=1;
    }
    return Matrix;
}

Status DFSConnect(ALGraph* G,int* visited,int**  Matrix,int i)
{//初始條件：存在連通圖G，和訪問向量visited,和該圖的逆向鄰接矩陣Matrix,和i為遍歷的起點
//操作結(jié)果：輸出強連通分量的頂點集，
    int j=0; 
    visited[i]=1;   
    printf("%s ",G->vertices[i].data);
   for(j=0;j<G->vexnum;j++)  
    if(Matrix[i][j]&&!visited[j])
    DFSConnect(G,visited,Matrix,j);
  
    return OK;
}
 
int get_connect(ALGraph* G,int finished[],int* visited,int**  Matrix)
{//初始條件：存在連通圖G，和遍歷完成序finished,和該圖的逆向鄰接矩陣Matrix
//操作結(jié)果：輸出強連通分量的頂點集，
    int i; 
    for(i=G->vexnum-1;i>=0;i--) //按照finished倒序選擇起點，逆向深度優(yōu)先遍歷
    { 
       
      if(!visited[finished[i]])
      { 
         DFSConnect(G,visited,Matrix,finished[i]);
      }
      printf("\n");
    }
  return 0;
}

 
Status count_connect(ALGraph* G)
{//初始條件：存在連通圖G
//操作結(jié)果：輸出強連通分量的頂點集，
   int i;