图的存储结构

2014/12/8 posted in  算法&数据结构

由于图的结构比较复杂,任意两个顶点之间都可能存在联系,因此无法以数据元素在存储区中的物理位置来表示元素之间的关系,即图没有顺序映像的存储结构。

数组表示法

用数组分别表示存储数据元素(顶点)的信息和数据元素之间的关系(边或者弧)的信息

#define INFINITY INT_MAX    //最大值
#define MAX_VERTEX_NUM 20   //最大顶点个数
typedef enum {DG,DN,UDG,UDM} GraphKind; //{有向图,有向网,无向图,无向网}

typedef struct ArcCell
{
    VRType adj;     //VRType是顶点关系类型,对无权图,用0/1
                    //表示相邻与否,对带权图则为权值类型
    InfoType *info;//该弧相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

sypedef struct
{
    VertexTypd vex[MAX_VERTEX_NUM];     //顶点向量
    AdjMatrix arcs;                     //邻接矩阵
    int vexnum,arcnum;                  //图的当前顶点数和弧数
    GraphKind kind;                     //图的种类标志
}MGraph;

若考虑无向图的邻接矩阵的对称性,则可采用压缩存储的方式只存入矩阵的下三角(或上三角)元素。

用邻接矩阵构造图:

Status CreateGraph( MGraph &G ) {
    // 采用数组(邻接矩阵)表示法,构造图G。
    scanf(&G.kind);  // 自定义输入函数,读入一个随机值
    switch (G.kind) {
        case  DG: return CreateDG(G);   // 构造有向图G
        case  DN: return CreateDN(G);   // 构造有向网G
        case UDG: return CreateUDG(G);  // 构造无向图G
        case UDN: return CreateUDN(G);  // 构造无向网G,算法7.2
        default : return ERROR;
    }
} // CreateGraph

Status CreateUDN(MGraph &G) {
  // 采用数组(邻接矩阵)表示法,构造无向网G。
  int i,j,k,w;
  VertexType  v1,v2;
  printf("G.vexnum :" );  scanf("%d",&G.vexnum);
  printf("G.arcnum :");   scanf("%d",&G.arcnum);
  getchar();  /*** 加上此句getchar()!!! ***/
  // scanf("%d,%d,%d",&G.vexnum, &G.arcnum, &IncInfo);
  for (i=0; i的权值
    // if (IncInfo) scanf(G.arcs[i][j].info); // 输入弧含有相关信息
    G.arcs[j][i].adj = G.arcs[i][j].adj; // 置的对称弧
  }
  return OK;
} // CreateUDN

邻接矩阵使用方便,操作简单,但是容易浪费存储空间,如果不是稠密图,动态存储将是更好的选择。

C语言实现:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//邻接矩阵
int G[100][100];
int add1 (int i,int j,int w)
{
    G[i][j] = w;
    return 0;
}

int main()
{
    int i,n;

    //建图
    scanf ("%d",&n);
    for (i = 0;i < n;i++)
    {
        int a,b,w;
        //输入起点、终点、权重
        scanf ("%d%d%d",&a,&b,&w);
        add1 (a,b,w);
        //无向图加上
        add1 (b,a,w);
    }
    return 0;
}

 邻接表表示法

邻接表是图的一种链式存储结构。在邻接表中,对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点vi的边(对有向图是以顶点vi为尾的弧。)每个结点由3个域组成,其中邻接点域指示与顶点vi邻接的点在图中的位置,链域指示下一条边或弧的结点;数据域存储和边或弧相关的信息,如权值等。

每个链表上附设一个表头结点。在表头结点中,除了设有链域只想链表中第一个结点之外,还设有存储顶点vi的名或其他有关信息的数据域。

#define MAX_VERTEX_NUM 20   //最大顶点个数

typedef struct ArcNode
{
    int adjvex;     //该弧所指向的顶点的位置
    struct ArcNode *nextarc;    //指向下一条弧的指针
    InfoType *info;//该弧相关信息的指针
}ArcNode;

typedef struct VNode
{
    VertexType data;    //顶点信息
    ArcNode *firstarc;  //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];

sypedef struct
{
    AdjList vertices;
    int vexnum,arcnum;                  //图的当前顶点数和弧数
    int kind;                       //图的种类标志
}ALGraph;

若无向图中有n个顶点,e条边,则它的邻接表需n个头结点和2e个表结点。显然,在边稀疏(e << (n(n-1))/2)的情况下,用邻接表表示图比邻接矩阵节省存储空间。

邻接表可以根据邻接的是入点还是出点分为邻接表和逆邻接表,两者各有各的优势,如果经常访问下一个结点,统计出度,邻接表将有优势;如果经常访问上一个结点,统计入度,逆邻接表将有优势。

C语言实现:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//邻接表

struct dot
{
    int d;
    int w;
    struct dot *next;
};

struct hed
{
    int v;
    struct dot *next;
}head[100];

int add2(int i,int j,int w)
{
    struct dot * p;
    struct dot * t = new dot;

    t->d = j;
    t->w = w;
    t->next = NULL;

    if (head[i].next == NULL)
    {
        head[i].next = t;
        return 0;
    }

    p = head[i].next;

    while (p->next != NULL)
        p = p->next;

    p->next = t;

    return 0;
}

int main()
{
    int i,n;

    memset (head,0,sizeof (head));
    //建图
    scanf ("%d",&n);
    for (i = 0;i < n;i++)
    {
        int a,b,w;
        //输入起点、终点、权重
        scanf ("%d%d%d",&a,&b,&w);
        add2 (a,b,w);
        //无向图加上
        add2 (b,a,w);
    }
    return 0;
}

建立邻接表的时间复杂度为O(n+e)。

十字链表

十字链表是有向图的另一种存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。

存储表示:

#define MAX_VERTEX_NUM 20   //最大顶点个数

typedef struct ArcBox
{
    int tailvex,headvex;            //该弧的尾和头顶点的位置
    struct ArcBox *hlink,*tlink;    //分别为弧头相同和弧尾相同的弧的链域
    InfoType *info;                 //该弧相关信息的指针
}ArcNode;

typedef struct VexNode
{
    VertexType data;    //顶点信息
    ArcNode *firstin,*firstout; //指向第一条依附该顶点的弧的指针
}VexNode;

sypedef struct
{
    VexNode xlist[MAX_VERTEX_NUM];      //表头向量
    int vexnum,arcnum;                  //图的当前顶点数和弧数
}OLGraph;

用十字链表建图:

Status CreateDG(OLGraph &G) {
  // 采用十字链表存储表示,构造有向图G(G.kind=DG)。
  //scanf(&G.vexnum, &G.arcnum, &IncInfo);
  int i,j,k;
  char v1,v2;
  int IncInfo=0;
  struct ArcBox *p;
  scanfInit();  // 输入初始化
  scanf(&G.vexnum, &G.arcnum, &IncInfo);  // 自定义输入函数
  for (i=0; itailvex=i;
    p->headvex=j;
    p->hlink=G.xlist[j].firstin;
    p->tlink=G.xlist[j].firstout;
    G.xlist[j].firstin = G.xlist[i].firstout = p;
        // 完成在入弧和出弧链头的插入
    //if (IncInfo) Input(*p->info); // 输入弧含有相关信息,此略!!!
  }
  return OK;
} // CreateDG

C语言实现:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//十字链表

struct dot
{
    int d;
    int w;
    struct dot *next;
};

struct hed
{
    int v;
    struct dot *to;
    struct dot *next;
}head[100];

int add3(int i,int j,int w)
{
    struct dot * p;
    struct dot * t = new dot;

    t->d = j;
    t->w = w;
    t->next = NULL;

    //正邻接表构建
    if (head[i].next == NULL)
    {
        head[i].next = t;
    }else
    {
        p = head[i].next;

        while (p->next != NULL)
            p = p->next;

        p->next = t;
    }

    //逆邻接表打十字
    if (head[i].to == NULL)
    {
        head[i].to = t;
        return 0;
    }else
    {
        p = head[i].to;

        while (p->next != NULL)
            p = p->next;

        p->next = t;
    }

    return 0;
}

int main()
{
    int i,n;

    memset (head,0,sizeof (head));
    //建图
    scanf ("%d",&n);
    for (i = 0;i < n;i++)
    {
        int a,b,w;
        //输入起点、终点、权重
        scanf ("%d%d%d",&a,&b,&w);
        add3 (a,b,w);
    }
    return 0;
}

十字链表中和了邻接表和逆邻接表的优势。

邻接多重表

邻接多重表示无向图的另一种链式存储结构。虽然邻接表是无向图的一种很有效的存储结构,在邻接表中容易求得顶点和边的各种信息。但是在邻接表中每一条边(vi,vj)有两个结点,分别周四第i个和第j个链表中,这些给某些图的操作带来了不便。如对已被搜索过的边作标记或删除一条边等。如果一个结点能表示一条边的两个点的数据结构比较适宜。

因此,邻接多重表诞生了。他的核心就是用一个结点代表了一条边。

#define MAX_VERTEX_NUM 20   //最大顶点个数
typedef emnu{unvisited,visited} VisitIf
;
typedef struct EBox
{
    VisitIf mark;                   //访问标记
    int ivex,jvex;                  //该边依附的两个顶点的位置
    struct EBox *ilink,*jlink;      //分别为指向依附这两个顶点的下一条边
    InfoType *info;                 //该弧相关信息的指针
}ArcNode;

typedef struct VexBox
{
    VertexType data;    //顶点信息
    EBox *firstedge;    //指向第一条依附该顶点的弧的指针
}VexBox;

sypedef struct
{
    VexBox adjmulist[MAX_VERTEX_NUM];
    int vexnum,arcnum;                  //无向图的当前顶点数和弧数
}AMLGraph;

C语言实现:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//邻接多重表(无向图)

struct dot
{
    int i,j;
    int w;
    struct dot *inext;
    struct dot *jnext;
};

struct hed
{
    int v;
    struct dot *next;
}head[100];

int add4(int i,int j,int w)
{
    struct dot *t = new dot;
    struct dot *p = NULL,*tp = NULL;

    t->i = i;
    t->j = j;
    t->w = w;
    t->inext = NULL;
    t->jnext = NULL;

    if (head[i].next == NULL)
    {
        head[i].next = t;
    }else
    {
        p = head[i].next;

        while (p != NULL)
        {
            tp = p;
            if (p->i == i)
                p = p->inext;
            else
                p = p->jnext;
        }

            if (tp->i == i)
                tp->inext = t;
            else
                tp->jnext = t;
    }

    if (head[j].next == NULL)
    {
        head[j].next = t;
    }else
    {
        p = head[j].next;

        while (p != NULL)
        {
            tp = p;
            if (p->i == j)
                p = p->inext;
            else
                p = p->jnext;
        }

        if (tp->i == j)
                tp->inext = t;
            else
                tp->jnext = t;
    }

    return 0;
}

int main()
{
    int i,n;

    memset (head,0,sizeof (head));
    //建图
    scanf ("%d",&n);
    for (i = 0;i < n;i++)
    {
        int a,b,w;
        //输入起点、终点、权重
        scanf ("%d%d%d",&a,&b,&w);
        add4 (a,b,w);
    }
    return 0;
}