如何将邻接矩阵转换成长尾邻接表？

本文共计578个文字，预计阅读时间需要3分钟。

解决方法+邻接表是一种图的表示方式，可以通过链表来表示每个节点的邻接点集合。将邻接矩阵转化为邻接表，可以首先创建一个顶点数组，然后对于每个顶点，将与其相邻的顶点编号存储在链表中。这样，可以通过链表快速访问每个顶点的邻接点集合。

解决方法

邻接表是一种图的表示方式，可以通过链表来表示每个顶点的邻接点集合。将邻接矩阵转化为邻接表，可以先创建一个顶点数组，然后对于每个顶点，将其对应的行或列中非零元素的列或行号（表示相邻的其他顶点）存储到该顶点的链表中。

代码实现

#include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 50 // 邻接表中的边结构体 typedef struct EdgeNode { int adjvex; // 邻接顶点的下标 struct EdgeNode *next; // 指向下一个邻接点的指针 }EdgeNode; // 邻接表中的顶点结构体 typedef struct VertexNode { int data; // 顶点的数据 EdgeNode *firstedge; // 指向第一个邻接点的指针 }VertexNode, AdjList[MAX_VERTEX_NUM]; // 图结构体 typedef struct { AdjList adjList; // 邻接表 int vertexNum; // 顶点数 int edgeNum; // 边数 }Graph; // 将邻接矩阵转化为邻接表 void createGraph(Graph *G, int matrix[][MAX_VERTEX_NUM]) { int i, j; for (i = 0; i < G->vertexNum; i++) { G->adjList[i].data = i; // 顶点的数据为下标 G->adjList[i].firstedge = NULL; // 初始化指向第一个邻接点的指针为空 for (j = 0; j < G->vertexNum; j++) { if (matrix[i][j] != 0) { // 邻接矩阵中元素不为0，表示有边 // 创建一个邻接点结构体 EdgeNode *edge = (EdgeNode*)malloc(sizeof(EdgeNode)); edge->adjvex = j; edge->next = G->adjList[i].firstedge; // 将新创建的邻接点插入到该顶点的链表头 G->adjList[i].firstedge = edge; // 更新该顶点的链表头指针 } } } } int main() { int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM] = { // 邻接矩阵 {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 0, 0, 1}, {0, 1, 1, 0} }; Graph G; G.vertexNum = 4; createGraph(&G, matrix); // 输出邻接表 for (int i = 0; i < G.vertexNum; i++) { printf("%d: ", G.adjList[i].data); EdgeNode *p = G.adjList[i].firstedge; while (p) { printf("%d ", p->adjvex); p = p->next; } printf("\n"); } return 0; }