本文主要想阐述有关图的一些基本概念，及基本的实现方法。图论算法是数据结构中比线性表和树更为复杂的算法，但并不影响它在实践中的重要作用，和实际生活中的应用，所以掌握这种算法还是蛮有用和有趣的。在这里，我会给大家介绍几个生活中发生的问题，他们可以转化成图论问题。然后再给大家介绍一下图的c语言基本实现。

一、图的基本概念

概念1：图。一个图(graph)G=(V,E)由顶点(vertex)集和边(edge)集组成。每一条变就是一个点对(v,w)，其中v,w∈V。有时也把边称作弧。如果点对是有序的，那么图就叫做是有向的。有向的图有时也叫有向图。顶点v和w邻接当且仅当(v,w)∈E。点对可以无向，我们称作无向图。有时候边还具有第三种成分，称作权或值。

图(Graph)也可以形式化描述为： Graph = (V,E) 其中，V={Vi | Vi ∈datatype, i=0,1,……,n-1} 是图中元素Vi(称为顶点Vertex )的集合，n=0时，V为空集，记为φ。

概念2：强连通的。如果在一个无向图中从每一个顶点到每个其他顶点都存在一条路径，则称该无向图是连通的。具有这样性质的有向图称为是强连通的。

概念3：顶点的度(Degree)。用图形来说明。设E为无向图G中边的集合，V、V’为图中的顶点。若(V,V’)∈E，则称V和V’互为邻接点，或称V与V’相邻接，边(V,V’)与V、V’相关联。某顶点V的度记为D(V)，代表与V相关联的边的条数。如：

D(V1)=3 ，D(V2)=2。

又设A为有向图G中弧的集合，若∈A，则称V邻接到V’，V’邻接自V，与V、V’相关联。顶点V的入度记为ID(V)，是图中以V为弧头的弧的条数;而顶点V的出度记为OD(V)，是图中以V为弧尾的弧的条数。

顶点V的度D(V)=ID(V)+OD(V)。如：

ID(V2)=2，OD(V2)=2，故D(V2)=4。

现实生活中能够用图进行模拟的实例：

比如航空系统。每个机场是一个顶点，在由两个顶点表示的机场间如果存在一条直达航线，那么这两个顶点就用一条边连接。边可以有一个权，表示时间、距离或飞行的费用。有理由假设，这样的一个图是有向图，因为在不同的方向上飞机可能所用时间或所花的费用会不同(例如，依赖于地方税)。可能我们更愿意航空系统是强连通的，这样就总能够从任一机场飞到领带的任意一个机场，我们也可能愿意迅速确定任意两个机场之间的佳航线。佳可以是指边数少的路径，也可以是根据一种或所有的全中量度所算出的佳者。

交通可以用一个图来模型化。每一条接到交叉口表示一个顶点，而每一条街道就是一条边。边的值可能代表速度限度，伙食容量，等等。此时我们可能是需要找出一条短路，或用该信息找出可能产生交通瓶颈的位置。

一、图的c语言实现

如下：
#define MAXN 64           ∥大顶点数∥
typedef char vtype;            ∥设顶点为字符类型∥
typedef int adjtype;           ∥设邻接矩阵A中元素aij为整型∥
typedef struct
{
vtype V[MAXN];             ∥顶点存储空间∥
    adjtype A[MAXN][MAXN];     ∥邻接矩阵∥
} mgraph;               
void createmgraph(mgraph G)    ∥建立无向图的数组表示法∥
{  
int  i, j, n;
    vtype  ch, u, v;
    adjtype  w;
    i = n = 0;
    ch=getchar( );             ∥输入顶点∥ 
    while (ch!=‘#’)          ∥#为结束符∥
{  
n++;                   ∥顶点计数∥
        if (n>MAXN-1) 
ERROR(n);          ∥溢出处理∥
        G.V[i++]=ch; ch=getchar( ); ∥存入顶点, 并读下一顶点∥
}
    for (i=0; i<n; i++)    ∥初始化邻接矩阵∥
        for (j=0; j<n; j++)
            G.A[i][j]=max;       ∥设max为机器表示的∞∥
  scanf(“%c %c %d”, &u, &v, &w);   ∥读入一条边<u, v>及权值 ∥
    while (u != ‘#’)           ∥u=‘#’时结束∥
    {   
i = locatevex(G,u);      ∥求u的序号∥
        j = locatevex(G,v);      ∥求v的序号∥
        G.A[i][j] = G.A[j][i] = w;      ∥邻接矩阵赋值（对称）∥
        scanf (“%c %c %d”,&u,&v,&w);  ∥读下一条边∥
}                        
}  

设图中顶点数为n，边的条数为e。第一个while循环执行次数为n;后两个for循环的执行次数约为n2;后一个while循环执行次数为e;故算法的时间复杂度为T(n,e)=O(n2+e)。若n2>>e，则时间复杂度为O(n2)。

说明：mgraph G;则G为存储图的一个结构体变量，G.V[MAXN]为顶点的存储空间，而G.A[MAXN][MAXN]为邻接矩阵。

数组表示法存储结构的建立算法比较简单：读入顶点和关系集(弧、边)，建立顶点表和邻接矩阵即可。

由于篇幅的限制，关于图的存储问题，关于广度优先搜索、深度优先搜索、拓扑结构的处理，我会在后续的篇幅中，整理总结。

本文参照文献：

[1]. 《数据结构体与算法分析--c语言描述》 Mark Allen Weiss 著 机械工业出版社出版。

[2].华清远见 《数据结构》课件