algraph.c

完全由C语言实现的图的相关操作

   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; 
}