一、邻接矩阵表示图

1.1、图的表示

节点数为 n 的图 \(G = (V,E)\) 的邻接矩阵 A 是 n*n 的。将 G 的顶点编号为 \(v_{1},v_{2},...,v_{n}\)，则

\[A[i][j] = \begin{cases} 1 &,若(v_{i},v_{j}) 或 <v_{i},v_{j}> 是 E(G) 中的边\\ 0 & ,若 (v_{i},v_{j}) 或 <v_{i},v_{j}> 不是 E(G) 中的边 \end{cases} \]

#define WeightType      int                             // 带权图中边上权值的数据类型
#define VertexType      char                            // 顶点的数据类型
#define MaxVertexNum    10                              // 顶点数目的最大值

typedef struct GNode *PtrToGNode;
typedef PtrToGNode MGraph;                              // 以邻接矩阵存储的图类型
typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;                                // 边

// 用邻接矩阵存储图
struct GNode
{
    VertexType vertex[MaxVertexNum];                    // 顶点表
    WeightType edge[MaxVertexNum][MaxVertexNum];        // 邻接矩阵，边表
    int vertexNum;                                      // 顶点数
    int edgeNum;                                        // 边数
};

// 边
struct ENode
{
    int v1,v2;                                          // 有向边<v1,v2>
    WeightType weight;                                  // 权重
};

1.2、初始化只有顶点的图

/**
 * @brief 初始化一个有vertexNum个顶点但没有边的图
 * 
 * @param vertexNum 顶点数
 * @return MGraph 返回指向图的指针
 */
MGraph CreateGraph(int vertexNum)
{
    MGraph graph;
    int V,E;

    graph = (MGraph)malloc(sizeof(struct GNode));
    graph->vertexNum = vertexNum;
    graph->edgeNum = 0;

    for(V = 0; V < graph->vertexNum; V++)
    {
        for(E = 0; E < graph->vertexNum; E++)
        {
            graph->edge[V][E] = 0;
        }
    }

    return graph;
}

1.3、向图中插入边

/**
 * @brief 向图中插入边
 * 
 * @param graph 待操作的图
 * @param edge 待插入的边
 */
void InsertEdge(MGraph graph, Edge edge)
{
    graph->edge[edge->v1][edge->v2] = edge->weight;         // 插入边<V1,V2>
    // 若是无向图，还要插入边<V2,V1>
    graph->edge[edge->v2][edge->v1] = edge->weight;
    graph->edgeNum++;
}

1.4、创建图

/**
 * @brief 创建图
 * 
 * @return MGraph 返回指向图的指针
 */
MGraph BuildGraph()
{
    MGraph graph;
    Edge edge;
    VertexType vertex;
    int vertexNum,edgeNum,i;

    printf("请输入顶点数：\n");
    scanf("%d", &vertexNum);
    getchar();

    graph = CreateGraph(vertexNum);

    // 如果顶点有数据的话，读入数据
    printf("请输入顶点的数据：\n");
    for(i = 0; i < graph->vertexNum; i++)
    {
        scanf("%c", &(graph->vertex[i]));
        getchar();
    }

    printf("请输入边数：\n");
    scanf("%d", &edgeNum);
    getchar();

    printf("请输入对应的边：\n");
    printf("（格式为：第一个顶点下标 第二个顶点下标 权值）\n");
    if(edgeNum != 0)
    {
        edge = (Edge)malloc(sizeof(struct ENode));
        for(i = 0; i < edgeNum; i++)
        {
            scanf("%d %d %d", &edge->v1, &edge->v2, &edge->weight);
            getchar();
            InsertEdge(graph, edge);
        }
    }

    return graph;
}

二、邻接表表示法

2.1、图的表示

邻接表：G[N] 为指针数组，对应矩阵每行一个链表，只存非 0 元素。

#define WeightType      int                     // 带权图中边上权值的数据类型
#define VertexType      char                    // 顶点类型
#define MaxVertexNum    10                      // 顶点数目的最大值

typedef struct GNode *PtrToGNode;
typedef PtrToGNode LGraph;                      // 以邻接表存储的图类型
typedef struct AdjVNode *PtrToAdjVNode;
typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;                        // 边

// 顶点信息
typedef struct VNode
{
    VertexType data;                            // 存顶点数据
    PtrToAdjVNode firstEdge;                    // 第一条边
}AdjList[MaxVertexNum];

// 边信息
struct AdjVNode
{
    int adjVex;                                 // 边指向哪个节点（邻接点下标）
    WeightType weight;                          // 边权重
    PtrToAdjVNode next;                         // 指向下一条边的指针
};

// 边
struct ENode
{
    VertexType v1,v2;                           // 有向边<V1,V2>
    WeightType weight;                          // 权重
};

// 用邻接表存储图
struct GNode
{
    AdjList vertices;                           // 邻接表
    int vertexNum;                              // 顶点数
    int edgeNum;                                // 边数
};

2.2、初始化只有顶点的图

/**
 * @brief 初始化一个有VertexNum个顶点但没有边的图
 * 
 * @param vertexNum 顶点数
 * @return MGraph 返回指向图的指针
 */
LGraph CreateGraph(int vertexNum)
{
    LGraph graph;
    int V,E;

    graph = (LGraph)malloc(sizeof(struct GNode));
    graph->vertexNum = vertexNum;
    graph->edgeNum = 0;

    for(V = 0; V < graph->vertexNum; V++)
    {
        graph->vertices[V].firstEdge = NULL;
    }

    return graph;
}

2.3、向图中插入边

/**
 * @brief 向图中插入边
 * 
 * @param graph 待操作的图
 * @param edge 待插入的边
 */
void InsertEdge(LGraph graph, Edge edge)
{
    PtrToAdjVNode newNode;

    // 为v2建立新的邻接点
    newNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    newNode->adjVex = edge->v2;
    newNode->weight = edge->weight;

    // 将v2插入v1的表头
    newNode->next = graph->vertices[edge->v1].firstEdge;
    graph->vertices[edge->v1].firstEdge = newNode;

    // 若是无向图，还需要插入边<v2,v1>
    // 为v1建立新的邻接点
    newNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    newNode->adjVex = edge->v1;
    newNode->weight = edge->weight;

    // 将v1插入v2的表头
    newNode->next = graph->vertices[edge->v2].firstEdge;
    graph->vertices[edge->v2].firstEdge = newNode;
}

2.4、创建图

/**
 * @brief 创建图
 * 
 * @return LGraph 返回指向图的指针
 */
LGraph BuildGraph(void)
{
    LGraph graph;
    Edge edge;
    int V;
    int vertexNum,i;

    printf("请输入顶点数：\n");
    scanf("%d", &vertexNum);
    getchar();

    // 如果顶点有数据的话，读入数据
    printf("请输入顶点的数据：\n");
    for(i = 0; i < graph->vertexNum; i++)
    {
        scanf("%c", &(graph->vertices[i].data));
        getchar();
    }

    graph = CreateGraph(vertexNum);

    printf("请输入边数：\n");
    scanf("%d", &(graph->edgeNum));
    getchar();

    if(graph->edgeNum != 0)
    {
        printf("请输入对应的边：\n");
        printf("（格式为：第一个顶点下标 第二个顶点下标 权值）\n");

        edge = (Edge)malloc(sizeof(struct ENode));
        for(i = 0; i < graph->edgeNum; i++)
        {
            scanf("%d %d %d", &edge->v1, &edge->v2, &edge->weight);
            getchar();
            InsertEdge(graph, edge);
        }
    }

    return graph;
}