#include "graph.h" #include <stdio.h> #include <stdlib.h> void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e) //创建图的邻接表 { int i,j; ArcNode *p; G=(AdjGraph *)malloc(sizeof(AdjGraph)); for(i=0;i<n;i++)

这是一个创建图的邻接表的函数实现，其中AdjGraph是图的邻接表结构体，定义如下：

#define MAXV 100   // 最大顶点数
typedef struct ArcNode{   // 边结点
    int adjvex;           // 邻接点
    struct ArcNode *next; // 指向下一个邻接点的指针
}ArcNode;
typedef struct VNode{     // 顶点结点
    int data;             // 顶点的数据
    ArcNode *first;       // 指向第一个邻接点的指针
}VNode, AdjList[MAXV];
typedef struct{           // 邻接表
    AdjList vertices;     // 存放顶点的数组
    int vexnum, arcnum;   // 顶点数和边数
}AdjGraph;

下面是CreateAdj函数的实现：

void CreateAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e)
{
    int i, j;
    ArcNode *p;
    G = (AdjGraph *)malloc(sizeof(AdjGraph));  // 分配内存空间
    for(i = 0; i < n; i++)
    {
        G->vertices[i].data = i;  // 初始化顶点的数据
        G->vertices[i].first = NULL;  // 初始化指向第一个邻接点的指针
        for(j = 0; j < n; j++)
        {
            if(A[i][j] != 0)  // 如果顶点i和顶点j之间有边
            {
                p = (ArcNode *)malloc(sizeof(ArcNode));  // 创建边结点
                p->adjvex = j;  // 邻接点为j
                p->next = G->vertices[i].first;  // 将该边结点插入到顶点i的邻接表头部
                G->vertices[i].first = p;
            }
        }
    }
    G->vexnum = n;  // 顶点数为n
    G->arcnum = e;  // 边数为e
}

其中，A[MAXV][MAXV]是一个邻接矩阵，n是顶点数，e是边数。函数的作用是将邻接矩阵转换为邻接表存储法。