C语言中实现图（Graph）

C语言中实现图（Graph）2013-06-07图（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{ VertexTypevexs[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵 intvexnum, 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个字符）:
", 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条弧的弧尾 弧头（以空格为间隔）: 
", （*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