1.邻接矩阵

问题：

使用邻接矩阵存储方式建立有向图G。

1.1 数据准备

顶点数据：vSet.txt

弧数据：arcSet.txt

1.2 读取顶点信息

// 顶点信息从0开始存储，注意和矩阵映射
  VertexType vexSet[MAX_VERTEX];
  int vexLength = 0;
  FILE* fpVex = fopen("../data/vSet.txt", "r");
  if (fpVex != NULL)
  {
      while (!feof(fpVex))
      {
          fscanf(fpVex, "%d", &vexSet[vexLength]);
          vexLength++;
      }
      fclose(fpVex);
  }

1.3 读取弧信息

  VertexType arcSet[MAX_VERTEX][2];
  int arcSetLength = 0;
  FILE* fpArc = fopen("../data/arcSet.txt", "r");
  if (fpArc != NULL)
  {
      VertexType srcVertex, dstVertex;
      while (!feof(fpArc))
      {
         
          fscanf(fpArc, "%d %d", &srcVertex, &dstVertex);
          arcSet[arcSetLength][0] = srcVertex;
          arcSet[arcSetLength][1] = dstVertex;
          arcSetLength++;
      }
      fclose(fpArc);
  }

1.4 创建邻接矩阵存储有向图

// 创建一个基于邻接矩阵存储有向图
// vexSet: 一维数组，用于存储顶点信息
// arcSet: 二维数组，用于存储顶点之间的关系
//        如：一行（1，2）：顶点1指向顶点2
// 注意：可将arcSet[][3]：分别存“顶点1指向顶点2，权值”
bool createMGraph(MGraph* mG, GraphKind kind,
    VertexType vexSet[], int vexSetLength,
    VertexType arcSet[][2], int arcSetLength)
{
    if (mG == NULL || vexSet == NULL || arcSet == NULL)
        return false;
    mG->kind = kind;
    // 存入顶点信息
    mG->vexnum = vexSetLength;
    for (int i = 0; i < vexSetLength; i++)
    {
        mG->vexs[i] = vexSet[i];
    }
    // 存入弧信息
    mG->arcnum = arcSetLength;
    VertexType srcVertex = 0;    // 弧尾
    VertexType dstVertex = 0;    // 弧头
    // 初始化弧信息
    //for (int row = 0; row < MAX_VERTEX; row++)
    //    for (int col = 0; col < MAX_VERTEX; col++)
    //        mG->arcs[row][col].weight = 0;
    // 将顶点数据存入弧中
    for (int i = 0; i < arcSetLength; i++)
    {
        srcVertex = arcSet[i][0];
        dstVertex = arcSet[i][1];
        // ArcCell arcCell{ 1 };
        mG->arcs[srcVertex - 1][dstVertex - 1].weight = 1;
    }
    return true;
}

1.5 打印邻接矩阵图

void printMGraph(MGraph mG)
{
    printf("Graph Type: %d\n", mG.kind);
    printf("Graph Vex Num: %d\n", mG.vexnum);
    printf("Graph Arc Num: %d\n", mG.arcnum);
    printf("Graph Vex Matrix: ");
    for (int i = 0; i < mG.vexnum; i++)
    {
        printf("%d ", mG.vexs[i]);
    }
    printf("\nGraph Arc Matrix: \n");
    // 存储的顶点编号为0开始
    for (int row = 0; row < mG.vexnum; row++)
    {
        for (int col = 0; col < mG.vexnum; col++)
        {
            printf("%d ", mG.arcs[row][col].weight);
        }
        printf("\n");
    }
}

运行结果：

2.邻接表

问题：

使用邻接表存储方式建立无向图G。

分析：

首先读入顶点信息，构建邻接数组之后，再读入弧信息。
然后再读入弧数据<两个顶点，两个顶点都能做源点，又能做终点，在两个头结点之后使用头插法插入弧结点>。
重复读取弧数据,生成弧结点插入，直到所有弧数据读完。

2.1 数据准备

2.2 读取顶点信息

2.3 读取弧信息

2.4 创建邻接表存储无向图

首先读入顶点信息，构建邻接数组之后，再读入弧信息。
然后再读入弧数据<两个顶点,两个顶点都能做源点，又能做终点，在两个头结点之后使用头插法插入弧结点>。
重复读取弧数据，生成弧结点插入，直到所有弧数据读完。

// 创建一个基于邻接表存储无向图
// vexSet: 一维数组，用于存储顶点信息
// arcSet: 二维数组，用于存储顶点之间的关系
//        如：一行（1，2）：顶点1指向顶点2
// 注意：可将arcSet[][3]：分别存“顶点1指向顶点2，权值”
bool createALGraph(ALGraph* G, GraphKind kind,
    VertexType vexSet[], int vexSetLength,
    VertexType arcSet[][2], int arcSetLength)
{
    if (G == NULL || vexSet == NULL || arcSet == NULL)
        return false;
    G->kind = kind;
    // 构造邻接数组vertice，每个元素包括顶点信息和头结点指针
    // 每次从vexSet中读入一个元素（顶点的信息）
    for (int i = 0; i < vexSetLength; i++)
    {
        VertexType vertex = vexSet[i];
        // 注意：顶点编号和索引一一对应
        // 将顶点信息存入头结点
        G->vertices[vertex].data = vertex;
        // 注意头结点指针赋空，方便后序头插
        G->vertices[vertex].first = NULL;
    }

    // 开始在边表中插入顶点，使用头插法
    VertexType srcVertex = 0;    // 源点
    VertexType dstVertex = 0;    // 终点
    for (int j = 0; j < arcSetLength; j++)
    {
        srcVertex = arcSet[j][0];   // 源点
        dstVertex = arcSet[j][1];   // 终点

        // 生成一个包含dstVertex弧结点，插入到srcVertex头节点中
        ArcNode* arcNodePtr = (ArcNode*)malloc(sizeof(ArcNode));
        arcNodePtr->adjvex = dstVertex;
        arcNodePtr->weight = 0;
        // 头插法插入到头结点
        arcNodePtr->next = G->vertices[srcVertex].first;
        G->vertices[srcVertex].first = arcNodePtr;

        // 生成一个包含srcVertex弧结点，插入到dstVertex头节点中
        arcNodePtr = (ArcNode*)malloc(sizeof(ArcNode));
        arcNodePtr->adjvex = srcVertex;
        arcNodePtr->weight = 0;
        // 头插法插入到头结点
        arcNodePtr->next = G->vertices[dstVertex].first;
        G->vertices[dstVertex].first = arcNodePtr;
    }

    // 设置顶点，弧数量
    G->vexnum = vexSetLength;
    G->arcnum = 2 * arcSetLength;

    return true;
}

2.5 打印邻接矩阵图

void printALGraph(ALGraph G)
{
    for (int i = 1; i <= G.vexnum; i++)
    {
        ArcNode* pNextNode = G.vertices[i].first;
        printf("Head: %d ", G.vertices[i].data);
        VertexType src = G.vertices[i].data; //头节点
        while (pNextNode != NULL)
        {
            // printf("%d ---> %d\n", src, pNextNode->adjvex);
            printf("-> %d ", pNextNode->adjvex);
            pNextNode = pNextNode->next;
        }
        printf("\n");
    }
}

运行结果