Tim的资源站

一、基本概念

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

一种是顶点结点结构，它由顶点域（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时）的情况下，用邻接表表示图比邻接矩阵节省存储空间。当和边相关的信息较多时更是如此。

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

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