邻接表

一、基本概念

邻接表(Adjacency List)是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图 G 中的每个顶点 vi,将所有邻接于 vi 的顶点 vj 链成一个单链表,这个单链表就称为顶点 vi 的邻接表;再将所有点的邻接表表头放到数组中,就构成了图的邻接表。其中,单链表中的结点称为表结点,每个单链表设的一个头结点称为顶点结点。在邻接表表示中有两种结点结构,如下图所示:

邻接表的两种结点结构

一种是顶点结点结构,它由顶点域(vertex)和指向第一条邻接边的指针域(firstedge)构成;另一种是表结点结构,它由邻接点域(adjvertex)和指向下一条邻接边的指针域(next)构成。对于带权图的边表,需再增设一个存储边上信息(如权值等)的域(info)。带权图的边表结构如下图所示:

带权图的边表结构

下面两张图显示了图与其对应的邻接表表示:

无向图
无向图的邻接表表示

二、 邻接表的实现

#define MaxVertexNum 30   //最大顶点数为30

typedef struct node {   //表结点
  int adjvertex;    //邻接点域,一般是存放顶点对应的序号或在表头向量中的下标
  InfoType info;    //与边(或弧)相关的信息
  struct node *next;  //指向下一个邻接点的指针域
} EdgeNode;

typedef struct vnode {   //顶点结点
  VertexType vertex;  //顶点域
  EdgeNode *firstedge; //边表头指针
} VertexNode;

//ALGraph 是以邻接表方式存储的图类型
class ALGraph {
  public:
    void CreateALGraph();
    void DFStraverse();
    void DFS(int v);    //从顶点 v 开始深度遍历算法
    void BFS(int v);    //从顶点 v 开始广度遍历算法
    //其他算法定义略

  private:
    VertexNode adjlist[MaxVertexNum];  //邻接表

    int vertexNum, edgeNum;    //顶点数和边数
    int visited[MaxVertexNum];    //访问标志数组
};

建立一个有向图的邻接表存储的算法如下:

//建立有向图的邻接表存储,不带边上权值信息的图
void ALGraph::CreateALGraph() {
  int i, j, k;

  EdgeNode *p;

  cout << "请输入顶点数和边数" << endl;

  cin >> vertexNum >> edgeNum;  //读入顶点数和边数
  
  //建立有 n 个顶点的顶点表
  for (i = 0; i < vertexNum; i++) {
    cout << "请输入第 " << i << " 个顶点信息:" << endl;

    cin >> adjlist[i].vertex;  //读入顶点信息

    adjlist[i].firstedge=NULL; //顶点的边表头指针设为空
  }

  cout << "下面输入边表信息:" <<endl;

  //建立边表
  for(k = 0; k < edgeNum; k++) {
    cout << "输入边<i, j>对应的顶点编号i, j" << endl;

    cin >> i >> j;     //读入边<vi, vj>的顶点对应序号

    p = new EdgeNode;  //生成新边表结点 p

    p->adjvertex = j;  //邻接点序号为 j

    p->next = adjlist[i].firstedge; //将新边表结点 p 插入顶点 vi 的链表头部

    adjlist[i].firstedge=p;
  }
}

若无向图中有 n 个顶点、e 条边,则它的邻接表需 n 个头结点和 2e 个表结点。显然,在边稀疏(e<<n(n-1)/2时)的情况下,用邻接表表示图比邻接矩阵节省存储空间。当和边相关的信息较多时更是如此。

在无向图的邻接表中,顶点 vi 的度恰为第 i 个链表中的结点数;而在有向图中,第 i 个链表中的结点个数只是顶点 vi 的出度,为求入度,必须遍历整个邻接表。在所有链表中,其邻接点域的值为 i 的结点的个数是顶点 vi 的入度。有时,为了便于确定顶点的入度或以顶点 vi 为头的弧,可以建立一个有向图的逆邻接表,即对每个顶点 vi 建立一个链接以 vi 为头的弧的链表。例如,下图所示为有向图 G2(见有向图)的邻接表和逆邻接表。

邻接表与逆邻接表

在建立邻接表或逆邻接表时,若输入的顶点信息为顶点的编号,则建立邻接表的时间复杂度为 O(n+e);否则,需要通过查找才能得到顶点在图中的位置,则时间复杂度为 O(n*e)。 在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点,但要判定任意两个顶点(vi和 vj)之间是否有边或弧相连,则需搜索第 i 个或第 j 个链表,因此不及邻接矩阵方便。

用户头像
登录后发表评论