跳到主要内容

09、数据结构与算法 - 基础:图

图的基本概念

图是由一个顶点集 V 和一个边集 E构成的数据结构。Graph=(V,E)

图中代表一条边的顶点的偶对如果无方向性,即无序,则称此图为无向图。

例:

 

V={V1,V2,V3,V4,V5};

E={(V1,V2),(V1,V4), (V2,V3),(V3,V4), (V2,V5)}

在无向图中,(x, y)与(y, x)表示同一条边。

图中代表一条边的顶点的偶对如果有序的,则称此图为有向图。在有向图中,用<x, y>表示一条有向边,在有向图中也称边为“弧”,x称为边的弧尾或始点,称此边为顶点x 的一条出边;y称为边的弧头或终点,称此边为顶点y 的一条入边。

例:

 

V={V1,V2,V3,V4};

E={<V1,V2>,<V1,V3>,<V3,V4>,<V4,V1>}

有向图中<x,y>与<y,x>是方向相反的两条弧。

顶点的度

一个顶点V的度是和顶点V关联的边的数目,记作D(V)。 在有向图中,一个顶点依附的弧头数目,称为该顶点的入度,记作ID(V)。一个顶点依附的弧尾数目,称为该顶点的出度,记作OD(V)。 某个顶点的入度和出度之和称为该顶点的度,即D(V)=ID(V)+OD(V)

网(带权图)

在一个图中,每条边或弧可以标上具有某种含义的数值,此数值称为该边的权(weight)。弧或边带权的图分别称作有向网或无向网****。

 

图的存储结构

邻接矩阵

邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图,则G的邻接矩阵是具有如下性质的n阶方阵。

 

无向图的邻接矩阵是对称的,有向图的邻接矩阵不一定是对称的。

例如(网的邻接矩阵):

 

 

c语言实现:

typedef int VertexType; /*图中结点的数据类型为整型*/
typedef struct  
{
    VertexType v[MAX_VERTEX_NUM];     /*顶点表*/
    int A[MAX_VERTEX_NUM][MAX_VERTEX_NUM];   /*邻接矩阵*/
    int vexnum,arcnum; /*图的顶点数和弧数*/
}MGraph;

邻接矩阵法优点:

容易实现图的操作,如:求某顶点的度、判断顶点之间是否有边(弧)、找顶点的邻接点等等。

邻接矩阵法缺点:

n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 对稀疏图而言尤其浪费空间。

邻接表

邻接表是图的一种链式存储结构。类似于树的孩子链表表示法。

1)为每个顶点建立一个单链表,

2)第i个单链表中包含顶点Vi的所有邻接顶点。

 

例如

无向图的邻接表:

 

无向图中邻接表所有边结点的度数总和等于边数的2倍。

有向图的邻接表

 

 

在有向图的邻接表中,链接的是每个结点的出边。

在有向图的邻接表中,第i个链表中边结点的个数是顶点Vi的出度;但不容易计算该顶点的入度。

有向图的逆邻接表

 

有向图的逆邻接表中,连接的是每个结点的入边。

在有向图的逆邻接表中,第i个链表中边结点的个数是顶点Vi的入度。

有向图的邻接表(或逆邻接表)中所有边结点的个数总和等于边数。

带权图的邻接表存储形式

 

 

邻接表c语言实现

/*边结点结构*/
typedef struct ArcNode {  
    int    adjvex;  /*该弧所指向的顶点的位置*/
    struct ArcNode  *nextarc; /*下一条弧*/
    //InfoType   info;   /*该弧上的权值*/
} ArcNode;

 /*顶点的结点结构*/
typedef int VertexType; 
typedef struct VNode { 
    VertexType  data;   
    ArcNode  *firstarc; //边表头指针
}VNode;

typedef struct {  
    VNode  vertices[MAX_VERTEX_NUM]; 
    int   vexnum, arcnum; /*图的顶点数和弧数*/
}ALGraph;

邻接表的优点:

空间效率高;容易寻找顶点的邻接点;

邻接表的缺点:

判断两顶点间是否有边或弧,需搜索两结点对应的单链表,没有邻接矩阵方便。

图的两种存储方式比较