图(Graph)是一种较线性表和数更为复杂的数据结构，在线性表中数据元素仅有线性关系，各一个数据元素只有一个直接前驱和一个直接后继，在树形结构中，数据元素之间有着明显的层次关系，
并且在每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中的一个元素相关，而在图形结构中就显得数据元素异常的自由了，在图中的任意两个元素之间可能是相关的。
首先要说的是关于图的存储方式，图中的每一个元素都是存储在一个矩阵中的，对于有向图,无向图,有向网以及无向网均是一样....
下面就提供一种图的建立的方法范例：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
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
原文：http://www.cnblogs.com/LiuDaohui0805/p/5296622.html