邻接矩阵
图节点的结构
#include <stdio.h> #include <stdlib.h> #define MaxVertexNum 100 // 最大顶点数 typedef int WeightType; // 边的权重类型 typedef struct GNode* PtrToGNode; struct GNode { int Nv; // 顶点数 int Ne; // 边数 WeightType G[MaxVertexNum][MaxVertexNum]; // 邻接矩阵 /* DataType Data[MaxVertexNum]; 存储顶点的数据 */ }; typedef PtrToGNode MGraph; // 以邻接矩阵存储的图类型
定义结构体GNode，其中包含以下成员变量：
- Nv：表示图中的顶点数。
- Ne：表示图中的边数。
二维数组表示图的邻接矩阵。它的大小是MaxVertexNum × MaxVertexNum，用于存储顶点之间边的权重或者存在的情况。（无权重且存在边用1表示，无权重且不存在边则用0表示；有权重且存在边用其权重表示，有权重且不存在边则用一个极大值表示。）
其中，DataType Data[MaxVertexNum]，可以用来存储与每个顶点相关的其他数据。例如：如果图表示一个社交网络，则可以存储每个顶点的个人资料信息（姓名、性别、年龄等），故而它的类型可以是整型，也可以是结构体类型。
创建并初始化
typedef int Vertex; /* 用顶点下标表示顶点，为整型 */ MGraph CreateGraph(int VertexNum) { Vertex V, W; MGraph Graph; Graph = (MGraph)malloc(sizeof(struct GNode)); Graph->Nv = VertexNum; Graph->Ne = 0; /* 注意：这里默认顶点编号从0开始，到 Nv-1 */ for (V = 0; V < Graph->Nv; V++) { for (W = 0; W < Graph->Nv; W++) { Graph->G[V][W] = 0; /* 如果是有权图，则设为INFINITY */ } } return Graph; }
变量V和W用于遍历图的顶点，Graph用于指向创建的图对象。
随后进入循环将图对象的邻接矩阵中顶点V和顶点W之间的权重（或标记）设置为0，表示它们之间没有边。注意，如果是有权图，则可以将该值设置为无穷大。
最后返回创建的图对象的指针。
插入边
typedef struct ENode* PtrToENode; struct ENode { Vertex V1, V2; /* 有向边<V1,V2 >*/ WeightType Weight; /* 权重 */ }; typedef PtrToENode Edge; void InsertEdge(MGraph Graph, Edge E) { /* 插入边<V1,V2> */ Graph->G[E->V1][E->V2] = E->Weight; /* 如果是无向图，还要插入边<V2,V1> */ Graph->G[E->V2][E->V1] = E->Weight; }
这个函数用于将对应位置的邻接矩阵元素设置为权重值（无权重值则标记为1）。如果是无向图，则还需要将对称位置的元素设置为相同的权重值，以表示双向的边。
完整的图的建立
输入格式：NvV1...NeV2...Weight...
MGraph BuildGraph() { MGraph Graph; Edge E; Vertex V; int Nv, i; scanf("%d", &Nv); Graph = CreateGraph(Nv); scanf("%d", &(Graph->Ne)); if (Graph->Ne != 0) { E = (Edge)malloc(sizeof(struct ENode)); for (i = 0; i < Graph->Ne; i++) { scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); InsertEdge(Graph, E); } } /* 如果顶点有数据的话，读入数据 */ for (V = 0; V < Graph->Nv; V++) { scanf("%c", &(Graph->Data[V])); } return Graph; }
先输入顶点数，然后去创建并初始化一个无边的图；再输入边数，如果没有边数则图建立完毕（如果顶点有数据就需要另外读入数据），可以直接返回图；如果有边数，则先开辟一个临时的变量，读入边的信息及权重存储在这个临时变量中，然后调用插入边的函数。最后返回构建好的图。
如果是为了考试，或者说需要在很短的时间内完成的话，可以改成以下的简化版：
#define MAXN 100 int G[MAXN][MAXN], Nv, Ne; void BuildGraph_() { int i, j, v1, v2, w; scanf("%d", &Nv); /* CreateGraph */ for (i = 0; i < Nv; i++) { for (j = 0; j < Nv; j++) { G[i][j] = 0; /* 或INFINITY */ } } scanf("%d", &Ne); for (i = 0; i < Ne; i++) { scanf("%d %d %d", &v1, &v2, &w); /* InsertEdge */ G[v1][v2] = w; G[v2][v1] = w; } }
邻接表
图节点的结构
#include <stdio.h> #include <stdlib.h> #define MaxVertexNum 100 // 最大顶点数 typedef int Vertex; /* 用顶点下标表示顶点，为整型 */ typedef float DataType; typedef int WeightType; // 边的权重类型 // 定义指向图节点的指针类型 PtrToGNode typedef struct GNode* PtrToGNode; // 图节点结构体定义 struct GNode { int Nv; // 顶点数 int Ne; // 边数 AdjList G; // 邻接表 }; // 图类型别名定义 typedef PtrToGNode LGraph; // 邻接表节点结构体定义 typedef struct Vnode { PtrToAdjVNode FirstEdge; // 指向第一个邻接点的指针 DataType Data; // 存储顶点的数据 } AdjList[MaxVertexNum]; // 邻接表类型定义 // 邻接表节点指针类型别名定义 typedef struct AdjVNode* PtrToAdjVNode; // 邻接点结构体定义 struct AdjVNode { Vertex AdjV; // 邻接点下标 WeightType Weight; // 边权重 PtrToAdjVNode Next; // 指向下一个邻接点的指针 };
创建并初始化
LGraph CreateGraph(int VertexNum) { Vertex V, W; LGraph Graph; Graph = (LGraph)malloc(sizeof(struct GNode)); Graph->Nv = VertexNum; Graph->Ne = 0; for (V = 0; V < Graph->Nv; V++) { Graph->G[V].FirstEdge = NULL; } return Graph; }
这里的初始化要注意的一点是：“Graph->G[V].FirstEdge = NULL;”将当前顶点的邻接表的第一个邻接点指针FirstEdge设置为NULL，表示当前顶点暂时没有邻接点。
插入边
typedef PtrToENode Edge; void InsertEdge(LGraph Graph, Edge E) { PtrToAdjVNode NewNode; /* 插入边<V1,V2> */ /* 先为V2建立新的邻接点 */ NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode)); NewNode->AdjV = E->V2; NewNode->Weight = E->Weight; /* 将V2插入V1的表头 */ NewNode->Next = Graph->G[E->V1].FirstEdge; Graph->G[E->V1].FirstEdge = NewNode; /* 如果是无向图，还要插入边<V2,V1> */ NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode)); NewNode->AdjV = E->V1; NewNode->Weight = E->Weight; /* 将V1插入V2的表头 */ NewNode->Next = Graph->G[E->V2].FirstEdge; Graph->G[E->V2].FirstEdge = NewNode; }
- 为边的顶点V2创建一个新的邻接点(NewNode)。
- 将边的顶点V2和权重赋值给新建立的邻接点(NewNode)。
- 将新建立的邻接点(NewNode)插入到顶点V1的邻接表的头部。
如果是无向图，则再反过来执行一遍。
完整的图的建立
LGraph BuildGraph() { int Nv,i; Vertex V; LGraph Graph; Edge E; scanf("%d", Graph->Nv); Graph = CreateGraph(Graph->Nv); scanf("%d", Graph->Ne); if ((Graph->Ne) != 0) { E = (Edge)malloc(sizeof(struct ENode)); printf("Enter the edges (format: V1 V2 Weight):\n"); for (i = 0; i < Graph->Ne; i++) { scanf("%d %d %d", &(E->V1), &(E->V2), &(E->Weight)); InsertEdge(Graph, E); } free(E); } return Graph; }
与邻接矩阵的实现类似
end
