图(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[])
{
......;
}
|
上面的只是无向网的建立步骤，对于其他的三种图方法类似，我就不再这里累赘了。希望能对正在处于迷茫中的哥们点帮助，也期待高手拍砖。！！！
本文转自 驿落黄昏 51CTO博客，原文链接：http://blog.51cto.com/yiluohuanghun/832537，如需转载请自行联系原作者
