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