mgraph.c

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

#include "MGraph.h" 
Status GreateGraph(MGraph* G)
{//采用邻接矩阵表示法，构造图G 
  scanf("%d",&G->kind); 
  switch(G->kind)
  {
    case DG: return GreateDG(G); //构造有向图 G
    case DN: return GreateDN(G); //构造有向网 G
    case UDG: return GreateUDG(G) ; //构造无向图 G
    case UDN: return GreateUDN(G); //构造无向网 G
    default : return ERROR ;           
  }  
  return OK ; 
}  

Status GreateUDN(MGraph* G)
{//采用邻接矩阵表示法，构造无向网G
  int i=0;
  int j=0; 
  int k=0; 
  scanf("%d %d",&G->vexnum,&G->arcnum);  
  // 构造顶点向量  
  for(i=0;i<G->vexnum;i++)
  {
    scanf("%d",&G->vexs[i]);                        
  }  
  //构造邻接矩阵 
  for(i=0;i<G->vexnum;i++)
   for(j=0;j<G->vexnum;j++)
   {        
    scanf("%d",&G->arcs[i][j]);      
     if(G->arcs[i][j]<0)   
     G->arcs[i][j] = INT_MAX ;            
   }   
   return OK;    
}  

Status GreateUDG(MGraph* G)
{//采用邻接矩阵表示法，构造无向图G
 GreateUDN(G); 
 return OK;      
} 
Status GreateDG(MGraph* G)
{//采用邻接矩阵表示法，构造有向图G
   GreateUDN(G); 
   return OK;      
}

Status GreateDN(MGraph* G)
{//采用邻接矩阵表示法，构造有向网G
 GreateUDN(G);
  return OK;     
} 

int MGraphMGraphLocalVex(MGraph* G,int v)
{ //返回图中顶点的位置 ,没找到返回-1 
  int i; 
  for(i=0;i<G->vexnum;i++)
  {
    if(G->vexs[i]==v)
    return i;                        
  }    
 return -1;   
} 

void ShortestPath_DIJ(MGraph* G,int v0,int** P,int* D)
{//用DiJstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其带权长度D[v]
//若p[v][w]为1，则w是从v0到v当前求得最短路径上的顶点
//final[v]为1，当且仅当v属于S，即已经求得从v0到v的最短路径 
 int v,w,min,k,i;  
 int* final=(int*) malloc(G->vexnum*sizeof(int)) ; 
 for(v=0;v<G->vexnum;++v)
 {
   final[v]= 0; D[v] =G->arcs[v0][v]; 
   for(w=0;w < G->vexnum ;++w)
   P[v][w] = 0 ;//设空路径
   if(D[v]<INT_MAX)
   {
     P[v][v0] =1; P[v][v] =1; //与v0与v有弧相连接                
   }                       
 } 
  D[v0] =0; final[v0] =1; //初始化，v0属于S集 
  //开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集 
   for(i=1;i<G->vexnum;++i)
   {
     min= INT_MAX;// 当前所知离v0顶点最近的距离 
     for(w=0;w<G->vexnum;++w)
      if(!final[w]&&D[w]<min)
      {
        min=D[w]; v=w;   //w顶点离v0 更近                   
      } 
      final[v]=1; // 离v0最近的 v加入S集 
     
      for(w=0;w<G->vexnum;++w)
      {
        if(!final[w]&&min+G->arcs[v][w]<D[w])
        {
          D[w] = min+G->arcs[v][w];
          for(k=0;k<G->vexnum;k++)  //p[w] =p[v] +[w] 
          P[w][k] = P[v][k] ;
          P[w][w] =1;                                      
        }                        
      }                
   } 
   free(final); 
} 

void ShortestPath_FLOYD(MGraph* G,int***P,int**D) 
{//用FLOYD算法求有向网G中各顶点v到w之间的最短路径P[v][w]及
//带权长度D[v][w]，若P[v][w][u]为1，则u是从v到w当前求得最短路径上的顶点
  int v,w,u,i; 
  for(v=0;v<G->vexnum;++v)//各对结 点 之间初始已知路径 及距离  
   for(w=0;w<G->vexnum;++w)
    {
      D[v][w] =G->arcs[v][w] ;
      for(u=0;u<G->vexnum;++u)
       P[v][w][u]=0; 
       if(D[v][w] < INT_MAX)
       {
         P[v][w][v]=1 ;  P[v][w][w]=1 ;        
       }                      
    } 

  for(u=0;u<G->vexnum;++u)
   for(v=0;v<G->vexnum;++v) 
     for(w=0;w<G->vexnum;++w)    
       if(D[v][u]+D[u][w]<D[v][w])
       {
          D[v][w] = D[v][u]+D[u][w] ;
          for(i=0;i<G->vexnum;i++)
          P[v][w][i]=P[v][u][i]||P[u][w][i] ;                     
       }                             
}