Hi,欢迎来到中国嵌入式培训高端品牌 - 华清远见嵌入式学院<北京总部官网>,专注嵌入式工程师培养15年!
当前位置: > 嵌入式学院 > 嵌入式学习 > 讲师博文 > 数据结构 图的概念及怎么实现
数据结构 图的概念及怎么实现
时间:2018-01-25作者:华清远见

本文主要想阐述有关图的一些基本概念,及基本的实现方法。图论算法是数据结构中比线性表和树更为复杂的算法,但并不影响它在实践中的重要作用,和实际生活中的应用,所以掌握这种算法还是蛮有用和有趣的。在这里,我会给大家介绍几个生活中发生的问题,他们可以转化成图论问题。然后再给大家介绍一下图的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].华清远见 《数据结构》课件


发表评论

全国咨询电话:400-611-6270,双休日及节假日请致电值班手机:15010390966

在线咨询: 曹老师QQ(3337544669), 徐老师QQ(1462495461), 刘老师 QQ(3108687497)

企业培训洽谈专线:010-82600901,院校合作洽谈专线:010-82600350,在线咨询:QQ(248856300)

Copyright 2004-2018 华清远见教育集团 版权所有 ,京ICP备16055225号,京公海网安备11010802025203号