C++数据结构之实现邻接表

在图论中，为了表示节点及其之间的联系，我们需要使用数据结构。邻接表是图的一种常见表示方法，实现方便且高效。

什么是邻接表

邻接表是一种图形式的数据结构，由节点和边组成。它使用链式结构来存储相邻节点的信息。邻接表常用于表示有向图、无向图以及加权图。在邻接表中，每一个节点都存储了一个链表，其中包含了该节点与其他节点之间的连接情况。

实现邻接表

1. 定义节点类

在实现邻接表前，我们需要定义一个节点类来表示每一个图节点的信息。节点类可以有多个属性，例如节点 ID、节点名称等。

//节点类
class Node{
public:
    int id; //节点 ID
    string name; //节点名称
    Node(){}
    Node(int id,string name){
        this->id=id;
        this->name=name;
    }
};

2. 定义邻接表类

定义邻接表类时需要考虑其成员变量和成员函数，一般包括节点数、边数、节点数组等。

//邻接表类
class Adjacency_List{
public:
    int node_num; //节点数
    int edge_num; //边数
    Node* node_array; //节点数组
    Adjacency_List(){}
    Adjacency_List(int node_num,int edge_num,Node* node_array){
        this->node_num=node_num;
        this->edge_num=edge_num;
        this->node_array=node_array;
    }
};

3. 定义链表节点类

为了实现邻接表，我们需要定义一个链表节点类表示每一个节点与其它节点的连接情况。链表节点需要保存连接的节点 ID 和指向下一个链表节点的指针等。

//链表节点类
class List_Node{
public:
    int id; //连接的节点 ID
    List_Node* next; //指向下一个链表节点的指针
    List_Node(){}
    List_Node(int id,List_Node* next){
        this->id=id;
        this->next=next;
    }
};

4. 实现邻接表的插入操作

在邻接表中插入新的连接时，需要遍历链表并找到最后一个节点，然后将新节点插入到最后一个节点的后面。

//邻接表插入操作
void insert_edge(Adjacency_List& g,int from,int to){
    for(int i=0;i<g.node_num;i++){
        //找到出发点
        if(g.node_array[i].id==from){
            //在出发点的链表中插入连接点
            List_Node* p=g.node_array[i].next;
            while(p->next!=NULL){
                p=p->next;
            }
            List_Node* new_node=new List_Node(to,NULL);
            p->next=new_node;
            break;
        }
    }
}

5. 实现邻接表的打印操作

打印邻接表时，需要遍历每一个节点的链表，并输出链表中的每一个节点 ID。

//打印邻接表
void print_graph(Adjacency_List g){
    cout<<"Node number: "<<g.node_num<<"  Edge number: "<<g.edge_num<<endl;
    for(int i=0;i<g.node_num;i++){
        cout<<"Node "<<g.node_array[i].id<<": ";
        List_Node* p=g.node_array[i].next;
        while(p->next!=NULL){
            cout<<p->id<<" ";
            p=p->next;
        }
        cout<<p->id<<endl;
    }
}

示例演示

下面是两个简单的示例演示如何使用邻接表来表示图。

示例 1

假设有一个有向图，其中有 3 个节点分别为 1、2、3，图的连接信息如下：

1 --> 2
1 --> 3

我们可以先定义每个节点，然后定义邻接表并插入连接信息，最后输出邻接表。

int main(){
    Node node1(1,"node1");
    Node node2(2,"node2");
    Node node3(3,"node3");
    Node nodes[]={node1,node2,node3};
    Adjacency_List g(3,2,nodes);
    List_Node node1_2(2,NULL);
    List_Node node1_3(3,NULL);
    node1.next=&node1_2;
    node2.next=NULL;
    node3.next=NULL;
    g.node_array[0]=node1;
    g.node_array[1]=node2;
    g.node_array[2]=node3;
    insert_edge(g,1,2);
    insert_edge(g,1,3);
    print_graph(g);
    return 0;
}

输出如下：

Node number: 3  Edge number: 2
Node 1: 2 3
Node 2: 
Node 3: 

示例 2

假设有一个无向图，其中有 4 个节点分别为 1、2、3、4，图的连接信息如下：

1 --- 2
|     |
|     |
3 --- 4

我们可以先定义每个节点，然后定义邻接表并插入连接信息，最后输出邻接表。

int main(){
    Node node1(1,"node1");
    Node node2(2,"node2");
    Node node3(3,"node3");
    Node node4(4,"node4");
    Node nodes[]={node1,node2,node3,node4};
    Adjacency_List g(4,4,nodes);
    List_Node node1_2(2,NULL);
    List_Node node1_3(3,NULL);
    node1.next=&node1_2;
    node2.next=NULL;
    node3.next=NULL;
    List_Node node2_1(1,NULL);
    List_Node node2_4(4,NULL);
    node2.next=&node2_1;
    node1_2.next=&node2_1;
    node4.next=NULL;
    List_Node node3_1(1,NULL);
    List_Node node3_4(4,NULL);
    node3.next=&node3_4;
    node1_3.next=&node3_1;
    List_Node node4_2(2,NULL);
    List_Node node4_3(3,NULL);
    node4.next=&node4_2;
    node2_4.next=&node4_2;
    node3_4.next=&node4_3;
    g.node_array[0]=node1;
    g.node_array[1]=node2;
    g.node_array[2]=node3;
    g.node_array[3]=node4;
    print_graph(g);
    return 0;
}

输出如下：

Node number: 4  Edge number: 4
Node 1: 2 3 
Node 2: 1 4 
Node 3: 1 4 
Node 4: 2 3