algraph.c

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

#include "stdafx.h"
#define MAX 999999
trid_tree* T; //字母树 
Status initALGraph(ALGraph* G)
{
  //图的初始化，是针对有向图的，从文件ALGraph.txt中读入，构造图的邻接表,数据都是从1开始
   int n;//表示与结点相接的结点总数;
   VertexType data; //该结点的信息 
   int vexnum=0;//图的当前顶点总数
   int arcnum=0 ;//图的弧数总数
   int j;    
   ArcNode* p =NULL;
   ArcNode* temp = NULL;
   FILE* fp = fopen("ALGraph.txt","r");
   T= (trid_tree*) malloc(sizeof(trid_tree)); //构造字母树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); //由顶点信息映射到数组下标
     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中
//操作结果：返回<v,w>的权值，大于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中的某个顶点
//操作结果：从顶点v起，进行深度优先遍历
    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数组是图中顶点的访问情况
//操作结果：从顶点v开始，对图G进行一次深度优先遍历,同时把遍历到的顶点的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的尚未访问的邻接顶点，递归调用DFS
   if(!visited[p->adjvex]) DFS(G,G->vertices[p->adjvex].data,visited);
  
   return OK;
}
Status BFSTraverse(ALGraph* G,int* visited)
{//初始条件：图G存在，visited数组是图中顶点的访问情况
//操作结果：从顶点1起，对全图G进行广度优先遍历,同时把遍历到的顶点的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数组是图中顶点的访问情况
//操作结果：从顶点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和图中的顶点有相同特征
//操作结果： 在图G中增加新顶点v，字母树中加入该顶点的信息
 if(G->vexnum>=MAX_VERTEX_NUM-1||G->vexnum<0) return ERROR; //图项点数已满
 
 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中的某个顶点的信息
//操作结果：删其除G中的顶点及与相关的弧,删除它在字母树的信息，并做相应调整
    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++) //图的映射数组中其它顶点补齐
    {       
       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为空
    // 顶点数-1,弧数减出度
    --G->vexnum;
    G->arcnum -= n;
    return OK;
}

int VexOutDegree(ALGraph* G,VertexType data)
{//初始条件：图G存在，data和G中有顶点有相同的特征
//操作结果:返回顶点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中有顶点有相同的特征
//操作结果：返回顶点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中的顶点有相同的特征
//操作结果：若图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
 //操作结果：在G中增加弧<v,w>,且弧的权值是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中已经存在<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) //无向图或无向网
 {  
    
    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>这条弧
//操作结果：把<v,w>这条弧的权值改为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) //无向图或无向网
  {
    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
//操作结果：在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) //无向图或无向网
   {
     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出发，正向深度优先遍历，计算遍历结束序，记入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，是用邻接表存储的
//操作结果：返回逆向的邻接矩阵，
    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为遍历的起点
//操作结果：输出强连通分量的顶点集，
    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
//操作结果：输出强连通分量的顶点集，
    int i; 
    for(i=G->vexnum-1;i>=0;i--) //按照finished倒序选择起点，逆向深度优先遍历
    { 
       
      if(!visited[finished[i]])
      { 
         DFSConnect(G,visited,Matrix,finished[i]);
      }
      printf("\n");
    }
  return 0;
}

 
Status count_connect(ALGraph* G)
{//初始条件：存在连通图G
//操作结果：输出强连通分量的顶点集，
   int i;