图的邻接表实现在处理稀疏图时比矩阵实现具有更高的效率，以下为图邻接表实现的c语言版本

声明和引用头文件部分：我们定义两个结构体类型，一个是节点 AdjListNode ,另一个就是图 GraphAdjList ，节点由下标 node 和邻接节点的指针 next 组成，图由图中储存的节点数目 size 和 储存节点信息的 List 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include <stdlib.h>
//用邻接表实现图
/*节点结构体*/
#define Maxsize 20
typedef struct AdjListNode
{
    
    int node;
    struct AdjListNode* next;
}AdjListNode;
typedef struct GraphAdjList{
    int size;
    AdjListNode* List[Maxsize];
}GraphAdjList;

初始化函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*初始化图*/
GraphAdjList* GraphInit(){
    GraphAdjList* graph = (GraphAdjList*)malloc(sizeof(GraphAdjList));
    graph->size=0;
    for(int i=0;i<Maxsize;++i){
        graph->List[i] = NULL;
    }
    return graph;
}
/*创建顶点*/
AdjListNode* CreateNode(int node){
    AdjListNode* ListNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    ListNode->next = NULL;
    ListNode->node = node;
    return ListNode;
}

添加顶点

1
2
3
4
/*添加顶点*/
void addNode(GraphAdjList* graph,AdjListNode* newNode){
    graph->List[graph->size++] = newNode;
}

连接图（最重要的步骤）：代码中重点强调的这一行很重要，每次连接两个节点（以V1连接V2为例），实际上是创建一个新的和V2一样的节点，然后将这个节点连接到V1之后，而不是直接引用V2,如果对V2直接引用就会造成在 V1->V2, V1->V3 这个操作时，V2也会和V3建立连接

1
2
3
4
5
6
7
8
9
10
11
/*连接有向图，V1 -> V2*/
void Connect(AdjListNode* V1,AdjListNode* V2){
    AdjListNode* pointer = V1;
    while(pointer->next != NULL){
        pointer = pointer->next;
    }
    AdjListNode* new ;
    new = CreateNode(V2->node);//！！！
    new->next = NULL;
    pointer->next = new;
}

打印函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*按顺序打印图中的所有顶点*/
void printgraph(GraphAdjList* graph){
    for(int i=0;i<graph->size;++i){
        printf("%d - ",graph->List[i]->node);
    }
}
/*打印图中所有顶点的连接关系*/
void printAVertex(AdjListNode* node){
    AdjListNode* pointer = node->next;
    printf("%d",node->node);
    while (pointer != NULL)
    {
        printf("->%d",pointer->node);
        pointer = pointer->next;
    }
    printf("\n");
}
void printVertex(GraphAdjList* graph){
    for(int i=0;i<graph->size;++i){
          printAVertex(graph->List[i]);
    }
}

主函数

1
2
3
4
5
6
7
8
9
10
11
int main(){
    GraphAdjList* graph = GraphInit();
    AdjListNode** List = graph->List;
    for(int i=0;i<Maxsize;++i){
        addNode(graph,CreateNode(i));
    }
    Connect(List[1],List[2]);
    Connect(List[1],List[3]);
    Connect(List[3],List[2]);
    printVertex(graph);
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。