图的存储结构
图的逻辑结构是：多对多
图的存储方式
数组(邻接矩阵)表示法
定义
图没有顺序存储结构，但可以借助二维数组来表示元素间的关系
-
建立一个
顶点表(记录各个顶点信息)，和一个邻接矩阵(表示各个顶点之间的关系) -
设图 A = (V,E)，有
n个顶点，则
顶点表的为
| i | 0 | 1 | 2 | … | n-1 |
|---|---|---|---|---|---|
| Vexs[i] | V1 | V2 | V3 | … | Vn |
- 图的邻接矩阵是一个二维数组
A.arcs[n][n]定义为：A.arcs[i][j] = 1存在从 i 顶点到 j 顶点的弧或者边，否则A.arcs[i][j] = 0
无向图的邻接矩阵
如下无向图
无向图
则它的邻接矩阵为
无向图的邻接矩阵
在无向图的邻接矩阵中，它的特点：
- 无向图的邻接矩阵是
对称的 - 顶点 i 的度 = 第 i 行/列 中 1 的个数
- 完全图的邻接矩阵中，对角元素为 0 ，其余为 1
有向图的邻接矩阵
如下有向图
有向图
则它的邻接矩阵为
有向图的邻接矩阵
第 i 行含义：以节点 Vi 为尾的弧(即出度边)
第 i 列含义：以节点 Vi 为头的弧(即入度边)
在有向图的邻接矩阵中，它的特点：
- 有向图的邻接矩阵
可能是不对称的 - 顶点的
出度 = 第 i 行元素之和 - 顶点的
入度 = 第 i 列元素之和 顶点的度 = 第 i 行元素之和 + 第 i 列元素之和
网(即有权图)的邻接矩阵表示法
定义为：A.arcs[i][j] = Wij 存在从 i 顶点到 j 顶点的弧或者边的权，否则 A.arcs[i][j] = 无穷大
如下网
有向网
则它的邻接矩阵为
有向网的邻接矩阵
邻接矩阵的存储表示
#define MAX_VERTEX_NUM 26 // 最大顶点个数
#define MAX_NAME 3 // 顶点字符串的最大长度+1
enum GraphKind
{
DG,
DN,
UDG,
UDN
}; // {有向图,有向网,无向图,无向网}
typedef int VRType;
typedef char InfoType;
typedef char VertexType[MAX_NAME]; // 顶点类型
typedef struct
{
VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；对带权图，则为权值
InfoType *info; // 该弧相关信息的指针(可无)
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二维数组
struct MGraph
{
VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
AdjMatrix arcs; // 邻接矩阵
int vexnum, arcnum; // 图的当前顶点数和弧数
enum GraphKind kind; // 图的种类标志
};
邻接矩阵的代码实现
main.c
/*
* Change Logs:
* Date Author Notes
* 2021-08.03 tyustli first version
*/
#include "graph.h"
int main(int argc, char *argv[])
{
printf("this is graph\r\n");
return 1;
}
graph.h
/*
* Change Logs:
* Date Author Notes
* 2021-08.03 tyustli first version
*/
#include <string.h>
#include <ctype.h>
#include <malloc.h> // malloc()等
#include <limits.h> // INT_MAX等
#include <stdio.h> // EOF(=^Z或F6),NULL
#include <stdlib.h> // atoi()
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
#define INFINITY INT_MAX // 用整型最大值代替∞
#define MAX_VERTEX_NUM 26 // 最大顶点个数
#define MAX_NAME 3 // 顶点字符串的最大长度+1
enum GraphKind
{
DG,
DN,
UDG,
UDN
}; // {有向图,有向网,无向图,无向网}
typedef int VRType;
typedef char InfoType;
typedef char VertexType[MAX_NAME]; // 顶点类型
typedef struct
{
VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；对带权图，则为权值
InfoType *info; // 该弧相关信息的指针(可无)
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二维数组
struct MGraph
{
VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
AdjMatrix arcs; // 邻接矩阵
int vexnum, arcnum; // 图的当前顶点数和弧数
enum GraphKind kind; // 图的种类标志
};
/************************ end of file **************************/
graph.c
/*
* Change Logs:
* Date Author Notes
* 2021-08.03 tyustli first version
*/
#include "graph.h"
// 图的数组(邻接矩阵)存储(存储结构由graph.h定义)的基本操作
// 初始条件：图 G 存在，u 和 G 中顶点有相同特征
// 操作结果：若 G 中存在顶点u，则返回该顶点在图中位置；否则返回 -1
int LocateVex(struct MGraph G, VertexType u)
{
int i;
for (i = 0; i < G.vexnum; ++i)
if (strcmp(u, G.vexs[i]) == 0)
return i;
return -1;
}
// 采用数组(邻接矩阵)表示法，由文件构造没有相关信息的无向图 G
void CreateFUDG(struct MGraph *G)
{
int i, j, k;
char filename[13];
VertexType va, vb;
FILE *graphlist;
printf("请输入数据文件名(f7-1.txt或f7-2.txt)：");
scanf("%s", filename);
graphlist = fopen(filename, "r"); // 打开数据文件，并以graphlist表示
fscanf(graphlist, "%d", &G->vexnum);
fscanf(graphlist, "%d", &G->arcnum);
for (i = 0; i < G->vexnum; ++i) // 构造顶点向量
fscanf(graphlist, "%s", G->vexs[i]);
for (i = 0; i < G->vexnum; ++i) // 初始化邻接矩阵
{
for (j = 0; j < G->vexnum; ++j)
{
G->arcs[i][j].adj = 0; // 图
G->arcs[i][j].info = NULL; // 没有相关信息
}
}
for (k = 0; k < G->arcnum; ++k)
{
fscanf(graphlist, "%s%s", va, vb);
i = LocateVex((*G), va);
j = LocateVex((*G), vb);
G->arcs[i][j].adj = G->arcs[j][i].adj = 1; // 无向图
}
fclose(graphlist); // 关闭数据文件
G->kind = UDG;
}
// 采用数组(邻接矩阵)表示法，由文件构造没有相关信息的无向网G
void CreateFUDN(struct MGraph *G)
{
int i, j, k, w;
char filename[13];
VertexType va, vb;
FILE *graphlist;
printf("请输入数据文件名：");
scanf("%s", filename);
graphlist = fopen(filename, "r"); // 打开数据文件，并以graphlist表示
fscanf(graphlist, "%d", &G->vexnum);
fscanf(graphlist, "%d", &G->arcnum);
for (i = 0; i < G->vexnum; ++i) // 构造顶点向量
fscanf(graphlist, "%s", G->vexs[i]);
for (i = 0; i < G->vexnum; ++i) // 初始化邻接矩阵
{
for (j = 0; j < G->vexnum; ++j)
{
G->arcs[i][j].adj = INFINITY; // 网
G->arcs[i][j].info = NULL; // 没有相关信息
}
}
for (k = 0; k < G->arcnum; ++k)
{
fscanf(graphlist, "%s%s%d", va, vb, &w);
i = LocateVex(*G, va);
j = LocateVex(*G, vb);
G->arcs[i][j].adj = G->arcs[j][i].adj = w; // 无向网
}
fclose(graphlist); // 关闭数据文件
G->kind = UDN;
}
makefile
objects = main.o graph.o
obj: $(objects)
cc -o obj $(objects) -lm
main.o : graph.h
graph.o : graph.h
.PHONY : clean
clean :
-rm obj $(objects)