(创作不易，感谢有你，你的支持，就是我前行的最大动力，如果看完对你有帮助，请留下您的足迹）
目录
图的概念（http://t.csdn.cn/CH4Bv）
图的顺序存储结构
数组（邻接矩阵）表示法
定义
无向图
有向图
网的邻接矩阵表示法
图的链式存储结构
邻接表表示法
定义：
无向图;
有向图：
小结：
图的概念（http://t.csdn.cn/CH4Bv）
图的顺序存储结构
数组（邻接矩阵）表示法
定义
建立一个顶点表和一个邻接矩阵（表示各个顶点之间关系）。
设图A=(V,E)有n个顶点，则图的邻接矩阵是一个二维数组A.Edge[n][n],
/** 图的类型枚举 */
typedef enum {
DG, //有向图 0
UDG, //无向图 1
DN, //有向网 2
UDN //无向网 3
}GraphKind;
/** 图的邻接矩阵存储表示 */
typedef struct {
char* verTexs[100]; //顶点数组
int arcs[100][100]; //邻接矩阵（权数组）
int verTexCount; //图的顶点数
int arcCount; //图的边/弧数
GraphKind kind; //图的类型
}MatrixGraph;无向图
特点：
1 、无向图的邻接矩阵是 对称 的
2 、顶点i的度=第i行（列）中1的个数完全图的领接矩阵中，对角元素为0，其余1
/** 使用邻接矩阵表示法创建无向图 */
int CreateUDG(MatrixGraph* G)
{
G->kind = UDG; //设置当前创建图的类型为无向图
printf("请输入无向图的顶点数：");
scanf("%d", &G->verTexCount);
printf("请输入边的数量：");
scanf("%d", &G->arcCount);
printf("依次输入顶点信息\n");
for (int i = 0; i < G->verTexCount; i++)
{
G->verTexs[i] = (char *)malloc(sizeof(char) * 10);
printf("顶点%d：", i + 1);
scanf("%s", G->verTexs[i]);
}
//初始化邻接矩阵，所有边的权值设置为0
for (int i = 0; i < G->verTexCount; i++)
{
for (int j = 0; j < G->verTexCount; j++)
{
G->arcs[i][j] = 0;
}
}
printf("请输入顶点和邻接顶点信息，构建邻接矩阵\n");
for (int i = 0; i < G->arcCount; i++)
{
char * vex1 = (char *)malloc(sizeof(char) * 10);
char * vex2 = (char *)malloc(sizeof(char) * 10);
printf("顶点：");
scanf("%s", vex1);
printf("邻接点：");
scanf("%s", vex2);
//分别获得两个顶点在顶点数组中的坐标
int x = LocateVex(G, vex1);
int y = LocateVex(G, vex2);
if (x == -1 || y == -1)
{
return 0;
}
G->arcs[x][y] = 1;
G->arcs[y][x] = G->arcs[x][y]; //无向图的邻接矩阵是对称的
free(vex1);
free(vex2);
}
return 1;
}有向图
特点：
1 、 有向图的邻接矩阵 可能是不对称 的
2 、 顶点的 出度=第i行元素之和
顶点的 入度=第i 列元素之和
顶点的度= 第i 行元素之和+ 第i列元素之和
/** 使用邻接矩阵表示法创建有向图 */
int CreateDG(MatrixGraph* G) {
G->kind = DG; //设置当前创建图的类型为有向图
printf("请输入有向图的顶点数：");
scanf("%d", &G->verTexCount);
printf("请输入边的数量：");
scanf("%d", &G->arcCount);
printf("依次输入顶点信息\n");
for (int i = 0; i < G->verTexCount; i++) {
G->verTexs[i] = (char *)malloc(sizeof(char) * 10);
printf("顶点%d：", i + 1);
scanf("%s", G->verTexs[i]);
}
//初始化邻接矩阵，所有边的权值设置为0
for (int i = 0; i < G->verTexCount; i++) {
for (int j = 0; j < G->verTexCount; j++) {
G->arcs[i][j] = 0;
}
}
printf("请输入顶点和邻接顶点信息，构建邻接矩阵\n");
for (int i = 0; i < G->arcCount; i++) {
char * vex1 = (char *)malloc(sizeof(char) * 10);
char * vex2 = (char *)malloc(sizeof(char) * 10);
printf("顶点：");
scanf("%s", vex1);
printf("邻接点：");
scanf("%s", vex2);
//分别获得两个顶点在顶点数组中的坐标
int x = LocateVex(G, vex1);
int y = LocateVex(G, vex2);
if (x == -1 || y == -1) {
return 0;
}
G->arcs[x][y] = 1;
//G->arcs[y][x] = G->arcs[x][y]; //有向图的邻接矩阵有可能不对称
free(vex1);
free(vex2);
}
return 1;
}网的邻接矩阵表示法
图的链式存储结构
邻接表表示法
定义：
指数组与链表相结合的储存方法
对每个顶点V𝑗 建立一个单链表，把与V 𝑗 有关联的边的信息链接起来，每个结点设为3个域
1 、每个单链表有一个 头结点 （设为 2个域）），存V𝒋 信息
2 、每个单链表的头结点另外用顺序存储结构存储
/** 图的类型枚举 */
typedef enum
{
DG, //有向图 0
UDG, //无向图 1
DN, //有向网 2
UDN //无向网 3
}GraphKind;
/** 边/弧的结点 */
typedef struct node {
int adjVex; //该边指向这条边邻接点的下标
struct node* nextEdge; //指向下一条边结点的指针
struct node* nextArc; //指向下一个弧结点的指针
int weight; //权重
}EdgeNode, ArcNode;
/** 顶点结点 */
typedef struct vexNode {
char* vex; //顶点值
EdgeNode* firstEdge; //指向第一条边的指针
ArcNode* firstArc; //指向第一条弧的指针
}VNode, AdjList[100];
/** 邻接表实现的图结构 */
typedef struct adjGraph {
AdjList vexes; //顶点数组
int vexCount; //顶点数量
int edgeCount; //图的边数
int arcCount; //图的弧数
GraphKind kind; //图的类型
}AdjListGraph;无向图;
注意：邻接表不唯一，因为各个边结点的链入顺序是任意的
TD(V𝒋 ) = 单链表中链接的结点个数
/** 返回顶点vex在顶点数组中的下标，没有找到返回-1 */
int LocateVex_AdjList(AdjListGraph* G, char* vex) {
int index = -1;
for (int i = 0; i < G->vexCount; i++) {
if (strcmp(vex, G->vexes[i].vex) == 0) {
index = i;
break;
}
}
return index;
}
/** 采用邻接表表示法创建无向图 */
int CreateUDG_AdjList(AdjListGraph* G) {
G->kind = UDG;
printf("请输入顶点数量：");
scanf("%d", &G->vexCount);
printf("请输入边的数量：");
scanf("%d", &G->edgeCount);
printf("请依次输入顶点信息\n");
for (int i = 0; i < G->vexCount; i++) {
G->vexes[i].vex = (char*)malloc(sizeof(char) * 10);
printf("顶点%d：", i + 1);
scanf("%s", G->vexes[i].vex);
//初始化邻接表，把边置空
G->vexes[i].firstEdge = NULL;
}
printf("请输入顶点和邻接点信息，构建邻接表\n");
for (int i = 0; i < G->edgeCount; i++) {
char* vex1 = (char*)malloc(sizeof(char) * 10);
char* vex2 = (char*)malloc(sizeof(char) * 10);
printf("顶点：");
scanf("%s", vex1);
printf("邻接点：");
scanf("%s", vex2);
int x = LocateVex_AdjList(G, vex1);
int y = LocateVex_AdjList(G, vex2);
if (x == -1 || y == -1) {
free(vex1);
free(vex2);
return 0;
}
EdgeNode* edgeNode = (EdgeNode*)malloc(sizeof(EdgeNode));
edgeNode->adjVex = x;
edgeNode->nextEdge = G->vexes[y].firstEdge;
edgeNode->weight = 0;
G->vexes[y].firstEdge = edgeNode;
edgeNode = (EdgeNode*)malloc(sizeof(EdgeNode));
edgeNode->adjVex = y;
edgeNode->nextEdge = G->vexes[x].firstEdge;
edgeNode->weight = 0;
G->vexes[x].firstEdge = edgeNode;
free(vex1);
free(vex2);
}
return 1;
}有向图：
TD(V𝒋 ) = OD(V𝒋 ) + ID（V𝒋 ）文章来源：https://www.toymoban.com/news/detail-774829.html
小结：
文章来源地址https://www.toymoban.com/news/detail-774829.html
到了这里，关于c语言数据结构-图的操作的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
