C语言中实现图(Graph)

图(Graph)是一种较线性表和数更为巨大的数据布局，在线性表中数据元素仅有线性干系，各一个数据元素只有一个直接前驱和一个直接后继，在树形布局中，数据元素之间有着明明的条理干系，而且在每一层上的数据元素大概和下一层中多个元素相关，但只能和上一层中的一个元素相关，而在图形布局中就显得数据元素异常的自由了，在图中的任意两个元素之间大概是相关的。

首先要说的是关于图的存储方法，图中的每一个元素都是存储在一个矩阵中的，对付有向图,无向图,有向网以及无向网均是一样….

下面就提供一种图的成立的要领典型：

typedef int VRType;   
typedef char InfoType;   
typedef char* VertexType;   
       
       
typedef enum{DG, DN, UDG, UDN} GraphKind;   
typedef struct ArcCell   
{   
 VRType adj;   
 InfoType *info;   
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];   
       
       
typedef struct
{   
    VertexType  vexs[MAX_VERTEX_NUM];       // 极点向量   
    AdjMatrix   arcs;                       // 连接矩阵   
    int        vexnum, arcnum;             // 图的当前极点数和弧数   
    GraphKind   kind;                       // 图的种类符号   
}MGraph;   
       
//返回指定极点在极点向量中的位置   
int LocateVex(MGraph G, VertexType elem)   
{   
 int i;   
 for(i = 0; i < G.vexnum; ++i)   
  if(strcmp(elem, G.vexs[i]) == 0)   
   return i;   
          
 return error;   
}   
       
//无向网   
int CreateUDN(MGraph *G)   
{   
 int i, j, k, l, IncInfo, w;//IncInfo暗示弧是否有其他信息   
 char s[MAX_INFO], *info;   
 char va[5], vb[5];   
 printf("请输入有向网的极点数,弧数,弧是否含有其他信息(是：1,否：0)");   
 scanf("%d,%d,%d", &(*G).vexnum, &(*G).arcnum, &IncInfo);   
 printf("请输入每个极点的值(<%d个字符):\n", MAX_NAME);   
 for(i = 0; i < (*G).vexnum; ++i)//结构极点向量   
 {   
  (*G).vexs[i] = (VertexType)malloc(sizeof(char)*5);   
  scanf("%s", (*G).vexs[i]);   
  getchar();   
 }   
 for(i = 0; i < (*G).vexnum; ++i)//初始化连接矩阵   
  for(j = 0; j < (*G).vexnum; ++j)   
  {   
   (*G).arcs[i][j].adj = 0;   
   (*G).arcs[i][j].info = NULL;   
  }   
 printf("请输入%d条弧的弧尾 弧头(以空格为隔断): \n", (*G).arcnum);   
        
 for(k = 0; k < (*G).arcnum; ++k)   
 {   
  scanf("%s %s", va, vb);//输入弧头，弧尾信息   
  printf("请输入该弧对应的权值 : ");   
  scanf("%d", &w);   
  i = LocateVex(*G, va);//定位弧尾位置，   
  j = LocateVex(*G, vb);//定位弧头位置   
  (*G).arcs[i][j].adj = w;//权值巨细   
  (*G).arcs[j][i].adj = w;   
  if(IncInfo)   
  {   
   printf("请输入该弧的相关信息(<%d个字符) ： ", MAX_INFO);   
   scanf("%s", s);   
   l = strlen(s);   
   if(l)   
   {   
    (*G).arcs[i][j].info = (char *)malloc((l+1)*sizeof(char));   
    strcpy((*G).arcs[i][j].info, s);   
   }   
  }   
          
 }   
 (*G).kind = DN;   
 return true;   
}   
       
int main(int argc, char *argv[])   
{   
 ......;   
}

上面的只是无向网的成立步调，对付其他的三种图要领雷同，我就不再这里累赘了。但愿能对正在处于苍茫中的哥们点辅佐，也等候好手拍砖。！！！

本文出自 “驿落薄暮” 博客，请务必保存此出处http://yiluohuanghun.blog.51cto.com/3407300/832537