博客

图的五种存储结构及其C语言实现

  • Post author:
  • Post category:其他


文章目录



🌅 一、图的基本概念

:root { --mermaid-font-family: "trebuchet ms", verdana, arial;}

图

方向

无向图

有向图

顶点

边

生成树

度

顶点

弧

有向树

入度

出度

生成森林

边分类

稀疏图

稠密图

完全图

有向完全图

简单图

顶点

邻接点

依附

网

权

路径

连通

环

连通图

强连通图

连通分量

强连通分量

简单路径

简单环



🛕二、图的基本存储结构



🎡1.邻接矩阵法

对于无权图来说，邻接矩阵法就是用一个二维数组arr来表示顶点之间的状态，如果存在边（vi，vj）（对有向图来说是弧<vi,vj>），那么arr[i][j]=arr[j][i]=1(如果是有向图则只有arr[i][j]=1)。

对于权图来说，如果不存在边的话，那么对应的矩阵元素值就置成无穷大。



🌇1.1 存储结构

typedef struct {
	VertexType vexs[MAXSIZE][MAXSIZE];//顶点数组
	EdgeType arr[MAXSIZE][MAXSIZE];//邻接矩阵 也可以用来存放权值
	int numNodes;//顶点的个数
	int numEdges;//边的个数
}MGraph;

void createMGraph(MGraph* G);//无向网的建立

void printMGraph(MGraph G);



🕍1.2 创建邻接矩阵

#include "Graph.h"
void createMGraph(MGraph* G)
{
	printf("请输入顶点数和边数:");
	int n, m;
	scanf("%d %d", &n, &m);
	G->numNodes = n;
	G->numEdges = m;
	printf("请输入%d个顶点\n", n);
	for (int i = 0; i < n; i++)
	{
		scanf("%s", G->vexs[i]);
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			G->arr[i][j] = INF;
		}
	}
	int i, j, w;
	for (int k = 0; k < m; k++)
	{
		printf("请输入边(Vi,Vj)的下标(i,j)和权w，以i,j,w的形式输入:");
		scanf("%d,%d,%d", &i, &j, &w);
		G->arr[i][j] = w;
		G->arr[j][i] = G->arr[i][j];
	}
}



🏰1.3 打印邻接矩阵存储的图

void printMGraph(MGraph G)
{
	for (int i = 0; i < G.numNodes; i++)
	{
		printf("第%d个顶点是%s\n", i + 1, G.vexs[i]);
	}
	for (int i = 0; i < G.numNodes; i++)
	{
		for (int j = 0; j < G.numNodes; j++)
		{
			if (G.arr[i][j] != INF)
			{
				printf("边(%s,%s)的权值是%d\n", G.vexs[i], G.vexs[j], G.arr[i][j]);
			}
		}
	}
}



🎢1.4 测试函数

void test1()
{
	MGraph G;
	createMGraph(&G);
	printMGraph(G);
}



🪂2.邻接表法

就是和在树中孩子表示法是一样的，用一个

数组表示顶点的集合

，数组中每个元素是一个结构体，结构体中

有顶点的元素和指向该顶点第一个邻接点（如果是有向图则指向以它为起点的弧的终点的）指针

，然后每个顶点的邻接点形成一个单链表，头结点是该顶点，这样对于无向图确定节点的度只要看他的邻接链表有多少个元素就行了，并且节约了很多的空间。

提出这种方法的动机是如果是稀疏图，我们用邻接矩阵法来储存有点太浪费空间了。

如果你是有向图，用上述邻接表可以方便的确定出度，如果还想确定入度可以再创建一个逆邻接表，把顶点作为弧尾的邻接弧都表示用链表表示出来，稍微有点麻烦了。



🎇2.1 存储结构

typedef struct EdgeNode{
	int adjvex;//确定这个点的下标
	EdgeType w;//储存头结点到这个结点的邻接边的权值
	struct EdgeNode* next;
}EdgeNode;//每个头结点的邻接链表的节点

typedef struct {
	VertexType str[MAXSIZE];//结点名
	EdgeNode* firstedgenode;//指向第一个邻接点
}VertexNode,AdjList[MAXSIZE];
//定义结点数组的元素，并直接把大小为MAXSIZE的结点数组这种类型定义为AdjList
typedef struct {
	AdjList adjlist;//头结点数组
	int numNode;//结点个数
	int numEdge;//边的个数
}GraphAdjList;

void createAdjlistGraph(GraphAdjList* G);//以邻接表法创无向权图

void printAdjlistGraph(GraphAdjList G);//展示我们的无向权图的边



🚇2.2 创建邻接表

void createAdjlistGraph(GraphAdjList* G)
{
	printf("请输入图G的结点数和边数:");
	scanf("%d %d", &(G->numNode), &(G->numEdge));
    //输入结点
	for (int i = 0; i < G->numNode; i++)
	{
		printf("请输入序号为%d的结点:", i);
		scanf("%s", G->adjlist[i].str);
		G->adjlist[i].firstedgenode = NULL;
	}
    //输入边
	for (int k = 0; k < G->numEdge; k++)
	{
		int i, j;
		EdgeNode* e = (EdgeNode*)malloc(sizeof(EdgeNode));
		printf("请输入边(vi,vj)上的序号i和j和权值w,以i,j,w的形式输入:");
		scanf("%d,%d,%d", &i, &j,&(e->w));
		e->adjvex = j;
        //头插法把e插入链表中
		e->next = G->adjlist[i].firstedgenode;
		G->adjlist[i].firstedgenode = e;
		//因为是无向图，所以要把e插入到头结点为j的链表汇总
        int tmp = e->w;
		e= (EdgeNode*)malloc(sizeof(EdgeNode));
		e->adjvex = i;
		e->next = G->adjlist[j].firstedgenode;
		G->adjlist[j].firstedgenode = e;
		e->w = tmp;
	}
}



🌁2.3 打印邻接表法存储的图

void printAdjlistGraph(GraphAdjList G)
{
	for (int i = 0; i < G.numNode; i++)
	{
		EdgeNode* p = G.adjlist[i].firstedgenode;
        //遍历每个以数组元素为头结点的链表 以此来输出自己的边。
		while (p != NULL)
		{
			printf("边(%s,%s)的权值为%d\n", G.adjlist[i].str, G.adjlist[p->adjvex].str, p->w);
			p = p->next;
		}
	}
}



🕋2.4 测试函数

void test2()
{
	GraphAdjList G;
	createAdjlistGraph(&G);
	printAdjlistGraph(G);
}
int main()
{
    test2();
    return 0;
}



🏖️3.十字链表法

解决有向图使用邻接表的时候只能确定出度或入度的问题。

在邻接表法的基础上，对每个结点，

形成两个链表

，一个是全部都以这个结点开头的弧的弧形成的链表，用指针nextsameSarc连起来。另一个是全部都以这个结点为结尾的弧形成的链表，用指针nextsameEarc连起来。



🏟️3.1 存储结构

//十字链表

typedef struct OLarc {
	int startvex;//弧的起点
	int endvex;//弧的终点
	struct OLarc* nextsameSarc;//指向起点相同的下一条弧
	struct OLarc* nextsameEarc;//指向终点相同的下一条弧
	EdgeType w;
}OLarc;//每个弧结点
//对每个结点，形成两个链表，一个是全部都以这个结点开头的弧的弧形成的链表，用指针nextsameSarc连起来
//另一个是全部都以这个结点为结尾的弧形成的链表，用指针nextsameEarc连起来。

typedef struct {
	VertexType str[MAXSIZE];//结点名
	OLarc* firstin;//指向第一个入结点弧
	OLarc* firstout;//指向第一个出结点弧
}OLNode,OList[MAXSIZE];

typedef struct {
	OList olist;
	int numNodes;//结点数
	int numarcs;//弧数
}OLGraph;

void createOLGraph(OLGraph* G);//利用十字链表创建一个有向带权图

void printOLGraph(OLGraph G);//展示该图的弧



🗻3.2 创建十字链表

void createOLGraph(OLGraph* G)
{
	printf("请输入图的顶点个数和弧的个数，以a空格b的形式输入：");
	scanf("%d %d", &(G->numNodes), &(G->numarcs));
    //输入结点
	for (int i = 0; i < G->numNodes; i++)
	{
		printf("请输入序号为%d的结点：",i);
		scanf("%s", G->olist[i].str);
		G->olist[i].firstin = G->olist[i].firstout = NULL;
	}
    //对每个弧(vi,vj)，利用头插法把这个弧插入到以数组中下标i对应的元素开头的相同起点链表中
    //利用头插法把这个弧插入到以数组中下标j对应的元素开头的相同终点链表中。
	for (int k = 0; k < G->numarcs; k++)
	{
		OLarc* e = (OLarc*)malloc(sizeof(OLarc));
		int i, j, w;
		printf("请输入弧(vi,vj)的顶点序号i和j以及它的权重w，以i,j,w形式输入");
		scanf("%d,%d,%d", &i, &j, &w);
		e->startvex = i;
		e->endvex = j;
		e->w = w;
		e->nextsameSarc = G->olist[i].firstout;
		G->olist[i].firstout = e;
		e->nextsameEarc = G->olist[j].firstin;
		G->olist[j].firstin = e;
	}
}



🧆3.3 打印十字链表存储的图

void printOLGraph(OLGraph G)
{
	for (int i = 0; i < G.numNodes; i++)
	{
		int ID = 0;//入度
		int OD = 0;//出度
		OLarc* p1 = G.olist[i].firstin;
		while (p1 != NULL)
		{
			//printf("弧<%s,%s>的权是%d\n", G.olist[p1->startvex].str, G.olist[i].str);
			p1 = p1->nextsameEarc;
			ID++;
		}
		OLarc* p2 = G.olist[i].firstout;
		while (p2 != NULL)
		{
			printf("弧<%s,%s>的权是%d\n", G.olist[i].str, G.olist[p2->endvex].str,p2->w);
			p2 = p2->nextsameSarc;
			OD++;
		}
		printf("结点%s的入度是%d,出度是%d\n", G.olist[i].str, ID, OD);
	}

}



🍔3.4 测试函数

void test3()
{
	OLGraph G;
	createOLGraph(&G);
	printOLGraph(G);
}



🥙4.邻接多重表法



🍝4.1 存储结构

对于我们的无向图的操作中，如果我们要删除两个结点的边，那么如果使用邻接表法存储我们的图，需要先找到其中一个结点，在以它为头结点的链表中删除这个边对应的链表元素；然后再找到另一个结点，然后再删除元素，这样的操作显然过于繁琐了。

因此，我们仿照十字链表的方式，对边表结点的结构进行一些改造。(不过我后面看来 这个删除操作还是很复杂= =)

把邻接表中用来放边的另一端的结构体修改成如下结构： 

typedef struct AMEdge {
	int start;
	int end;//用start和end表示一个边
	struct AMEdge* startlink;//指向下一个依附于这个start顶点的边的指针
	struct AMEdge* endlink;//指向下一个依附于这个end顶点的边的指针
}AMEdge;

这样，我们就用一个结点就表示了一个无向图中的边，而不是像邻接表法中那样对一个边用两个结点来表示它。

然后仿照邻接表法构建其他的结构： 

typedef struct {
	VertexType str[MAXSIZE];//结点的名字
	AMEdge* pEdge;//指向第一个依附于此结点的边
}AMvertex,AMList[MAXSIZE];

typedef struct {
	AMList Amlist;
	int numvertex;
	int numedge;
}AMGraph;



🎂4.2 创建邻接多重表

这里创建的方法仿照十字链表，每输入一个边（Vi，Vj）后，利用头插法把这个边插入到以数组下标i对应的元素为头结点的链表中，并且插入i时把这个边的指向下一个依附于这个i顶点的边的指针指向链表头结点的下一个元素，然后把指向链表头结点的下一个元素的指针指向这个边；然后对以数组下标i对应的元素为头结点的链表进行同样的操作，不过要把startlink指针换成endlink指针。 

void createAMGraph(AMGraph* G)
{
	printf("请输入该无向图的顶点数和边数，以i空格j格式输入:");
	scanf("%d %d", &G->numvertex, &G->numedge);
	for (int i = 0; i < G->numvertex; i++)
	{
		printf("请输入序号为%d的结点的名字\n", i);
		scanf("%s", G->Amlist[i].str);
		G->Amlist[i].pEdge = NULL;
	}
	for (int k = 0; k < G->numedge; k++)
	{
		int i, j;
		printf("请输入边(Vi,Vj)的顶点序号i和j,以格式i,j输入:");
		scanf("%d,%d", &i, &j);
		AMEdge* e = (AMEdge*)malloc(sizeof(AMEdge));
		e->start = i;
		e->end = j;
		e->startlink = G->Amlist[i].pEdge;
		G->Amlist[i].pEdge = e;
		e->endlink = G->Amlist[j].pEdge;
		G->Amlist[j].pEdge = e;
	}
}



🥧4.3 打印邻接多重表存储的图

void printAMGraph(AMGraph G)
{
	for (int i = 0; i < G.numvertex; i++)
	{
		AMEdge* p = G.Amlist[i].pEdge;
		printf("结点%s的邻接边为：",G.Amlist[i].str);
		while (p != NULL)
		{
			printf("(%s,%s) ", G.Amlist[p->start].str, G.Amlist[p->end].str);
            //根据p这个边的start端点是i还是end端点是i来判断走startlink还是endlink
			if (p->start == i)
			{
				p = p->startlink;
			}
			else if (p->end == i)
			{
				p = p->endlink;
			}
		}
		printf("\n");
	}
}



🥛4.4 删除图中的边

这里需要传G的指针进去，因为当我们把一个点的相邻边都删除完了以后，需要把这个链表中头结点中指向下一个元素的指针的值改成空，我们要修改指针的值，所以要传G的指针进去，相当于传了头结点中指向下一个元素的指针的二级指针。 

void deleteEdge(AMGraph* G, int i, int j)
{
	if (G->numedge != 0)
	{
		AMEdge* p = G->Amlist[i].pEdge;
		AMEdge* tmp = NULL;
		AMEdge* tmp1 = NULL;
		while ((!(p->start == i && p->end == j)) && (!(p->start == j && p->end == i)))
		{
			tmp = p;
			if (p->start == i)
			{
				p = p->startlink;
			}
			else if (p->end == i)
			{
				p = p->endlink;
			}
		}
		tmp1 = p;
		if (tmp == NULL)
		{
			if (p->start == i)
			{
				G->Amlist[i].pEdge = p->startlink;
			}
			else if (p->end == i)
			{
				G->Amlist[i].pEdge = p->endlink;
			}
		}
		else
		{
			if (p->start == i)
			{
				if (tmp->start == i)
				{
					tmp->startlink = p->startlink;
				}
				else if (tmp->end == i)
				{
					tmp->endlink = p->startlink;
				}
			}
			else if (p->end == i)
			{
				if (tmp->start == i)
				{
					tmp->startlink = p->endlink;
				}
				else if (tmp->end == i)
				{
					tmp->endlink = p->endlink;
				}
			}
		}
		p = G->Amlist[j].pEdge;
		tmp = NULL;
		while ((!(p->start == i && p->end == j)) && (!(p->start == j && p->end == i)))
		{
			tmp = p;
			if (p->start == j)
			{
				p = p->startlink;
			}
			else if (p->end == j)
			{
				p = p->endlink;
			}
		}
		if (tmp == NULL)
		{
			if (p->start == j)
			{
				G->Amlist[j].pEdge = p->startlink;
			}
			else if (p->end == j)
			{
				G->Amlist[j].pEdge = p->endlink;
			}
		}
		else
		{
			if (p->start == j)
			{
				if (tmp->start == j)
				{
					tmp->startlink = p->startlink;
				}
				else if (tmp->end == j)
				{
					tmp->endlink = p->startlink;
				}
			}
			else if (p->end == j)
			{
				if (tmp->start == j)
				{
					tmp->startlink = p->endlink;
				}
				else if (tmp->end == j)
				{
					tmp->endlink = p->endlink;
				}
			}
		}
		free(tmp1);
		G->numedge--;
	}
	else
	{
	printf("图中的边已经都删除了\n");
    }
}



🧊4.5 测试函数

void test4()
{
	AMGraph G;
	createAMGraph(&G);
	printAMGraph(G);
	for (int k = 0; k < 6; k++)
	{
		printf("请输入要删除的边,以i,j格式输入");
		int i, j;
		scanf("%d,%d", &i, &j);
		deleteEdge(&G, i, j);
		printAMGraph(G);
	}
}



🍛5.边集数组法

边集数组是由两个一维数组构成的，一个是存储顶点的信息；另一个存储边的信息，这个数组的元素存储边的起点，终点，权重。



🍿5.1 存储结构

//边集数组法

typedef struct {
	VertexType str[MAXSIZE];
}Node;

typedef struct {
	int start;
	int end;
	int weight;
}Edge;

typedef struct {
	Node vertex[MAXSIZE];
	Edge edge[MAXSIZE];
}ESAGraph;

在边集数组中要确定一个顶点的度要扫描整个边集数组，效率很低，不过边集数组可以很容易的帮助我们找到修改边的信息，显然边集数组法更适合需要对边进行处理的情况。



🧊6.图的五种存储结构代码汇总



🍙6.1 Graph.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#define INF 65535

#define MAXSIZE 100

typedef char VertexType;//顶点的类型

typedef int EdgeType;//边上权值的类型

//邻接矩阵法
typedef struct {
	VertexType vexs[MAXSIZE][MAXSIZE];//顶点数组
	EdgeType arr[MAXSIZE][MAXSIZE];//邻接矩阵 也可以用来存放权值
	int numNodes;//顶点的个数
	int numEdges;//边的个数
}MGraph;

void createMGraph(MGraph* G);//无向网的建立

void printMGraph(MGraph G);

//邻接表法
typedef struct EdgeNode{
	int adjvex;//确定这个点的下标
	EdgeType w;//储存头结点到这个结点的邻接边的权值
	struct EdgeNode* next;
}EdgeNode;//每个头结点的邻接链表的节点

typedef struct {
	VertexType str[MAXSIZE];//结点名
	EdgeNode* firstedgenode;//指向第一个邻接点
}VertexNode,AdjList[MAXSIZE];
//定义结点数组的元素，并直接把大小为MAXSIZE的结点数组这种类型定义为AdjList
typedef struct {
	AdjList adjlist;
	int numNode;//结点个数
	int numEdge;//边的个数
}GraphAdjList;

void createAdjlistGraph(GraphAdjList* G);//以邻接表法创无向权图

void printAdjlistGraph(GraphAdjList G);

//十字链表

typedef struct OLarc {
	int startvex;//弧的起点
	int endvex;//弧的终点
	struct OLarc* nextsameSarc;//指向起点相同的下一条弧
	struct OLarc* nextsameEarc;//指向终点相同的下一条弧
	EdgeType w;
}OLarc;//每个弧节点

typedef struct {
	VertexType str[MAXSIZE];//结点名
	OLarc* firstin;//指向第一个入结点弧
	OLarc* firstout;//指向第一个出结点弧
}OLNode,OList[MAXSIZE];

typedef struct {
	OList olist;
	int numNodes;
	int numarcs;
}OLGraph;

void createOLGraph(OLGraph* G);//利用十字链表创建一个有向带权图

void printOLGraph(OLGraph G);

//邻接多重表

typedef struct AMEdge {
	int start;
	int end;//用start和end表示一个边
	struct AMEdge* startlink;//指向下一个依附于这个start顶点的边的指针
	struct AMEdge* endlink;//指向下一个依附于这个end顶点的边的指针
}AMEdge;

typedef struct {
	VertexType str[MAXSIZE];//结点的名字
	AMEdge* pEdge;//指向第一个依附于此结点的边
}AMvertex,AMList[MAXSIZE];

typedef struct {
	AMList Amlist;
	int numvertex;
	int numedge;
}AMGraph;

void createAMGraph(AMGraph* G);//创建一个无权有向图

void printAMGraph(AMGraph G);

void deleteEdge(AMGraph* G, int i, int j);

//边集数组法

typedef struct {
	VertexType str[MAXSIZE];
}Node;

typedef struct {
	int start;
	int end;
	int weight;
}Edge;

typedef struct {
	Node vertex[MAXSIZE];
	Edge edge[MAXSIZE];
}ESAGraph;



🍲6.2 Graph.c

#include "Graph.h"
void createMGraph(MGraph* G)
{
	printf("请输入顶点数和边数,以a空格b的形式输入:");
	int n, m;
	scanf("%d %d", &n, &m);
	G->numNodes = n;
	G->numEdges = m;
	printf("请输入%d个顶点\n", n);
	for (int i = 0; i < n; i++)
	{
		scanf("%s", G->vexs[i]);
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			G->arr[i][j] = INF;
		}
	}
	int i, j, w;
	for (int k = 0; k < m; k++)
	{
		printf("请输入边(Vi,Vj)的下标(i,j)和权w，以i,j,w的形式输入:");
		scanf("%d,%d,%d", &i, &j, &w);
		G->arr[i][j] = w;
		G->arr[j][i] = G->arr[i][j];
	}
}

void printMGraph(MGraph G)
{
	for (int i = 0; i < G.numNodes; i++)
	{
		printf("第%d个顶点是%s\n", i + 1, G.vexs[i]);
	}
	for (int i = 0; i < G.numNodes; i++)
	{
		for (int j = 0; j < G.numNodes; j++)
		{
			if (G.arr[i][j] != INF)
			{
				printf("边(%s,%s)的权值是%d\n", G.vexs[i], G.vexs[j], G.arr[i][j]);
			}
		}
	}
}

void createAdjlistGraph(GraphAdjList* G)
{
	printf("请输入图G的结点数和边数,以a空格b的形式输入:");
	scanf("%d %d", &(G->numNode), &(G->numEdge));
	for (int i = 0; i < G->numNode; i++)
	{
		printf("请输入序号为%d的结点:", i);
		scanf("%s", G->adjlist[i].str);
		G->adjlist[i].firstedgenode = NULL;
	}
	for (int k = 0; k < G->numEdge; k++)
	{
		int i, j;
		EdgeNode* e = (EdgeNode*)malloc(sizeof(EdgeNode));
		printf("请输入边(vi,vj)上的序号i和j和权值w,以i,j,w的形式输入:");
		scanf("%d,%d,%d", &i, &j,&(e->w));
		e->adjvex = j;
		e->next = G->adjlist[i].firstedgenode;
		G->adjlist[i].firstedgenode = e;
		int tmp = e->w;
		e= (EdgeNode*)malloc(sizeof(EdgeNode));
		e->adjvex = i;
		e->next = G->adjlist[j].firstedgenode;
		G->adjlist[j].firstedgenode = e;
		e->w = tmp;
	}
}

void printAdjlistGraph(GraphAdjList G)
{
	for (int i = 0; i < G.numNode; i++)
	{
		EdgeNode* p = G.adjlist[i].firstedgenode;
		while (p != NULL)
		{
			printf("边(%s,%s)的权值为%d\n", G.adjlist[i].str, G.adjlist[p->adjvex].str, p->w);
			p = p->next;
		}
	}
}

void createOLGraph(OLGraph* G)
{
	printf("请输入图的顶点个数和弧的个数，以a空格b的形式输入：");
	scanf("%d %d", &(G->numNodes), &(G->numarcs));
	for (int i = 0; i < G->numNodes; i++)
	{
		printf("请输入序号为%d的节点：",i);
		scanf("%s", G->olist[i].str);
		G->olist[i].firstin = G->olist[i].firstout = NULL;
	}
	for (int k = 0; k < G->numarcs; k++)
	{
		OLarc* e = (OLarc*)malloc(sizeof(OLarc));
		int i, j, w;
		printf("请输入弧(vi,vj)的顶点序号i和j以及它的权重w，以i,j,w形式输入");
		scanf("%d,%d,%d", &i, &j, &w);
		e->startvex = i;
		e->endvex = j;
		e->w = w;
		e->nextsameSarc = G->olist[i].firstout;
		G->olist[i].firstout = e;
		e->nextsameEarc = G->olist[j].firstin;
		G->olist[j].firstin = e;
	}
}

void printOLGraph(OLGraph G)
{
	for (int i = 0; i < G.numNodes; i++)
	{
		int ID = 0;//入度
		int OD = 0;//出度
		OLarc* p1 = G.olist[i].firstin;
		while (p1 != NULL)
		{
			//printf("弧<%s,%s>的权是%d\n", G.olist[p1->startvex].str, G.olist[i].str);
			p1 = p1->nextsameEarc;
			ID++;
		}
		OLarc* p2 = G.olist[i].firstout;
		while (p2 != NULL)
		{
			printf("弧<%s,%s>的权是%d\n", G.olist[i].str, G.olist[p2->endvex].str,p2->w);
			p2 = p2->nextsameSarc;
			OD++;
		}
		printf("结点%s的入度是%d,出度是%d\n", G.olist[i].str, ID, OD);
	}
}

void createAMGraph(AMGraph* G)
{
	printf("请输入该无向图的顶点数和边数，以i空格j格式输入:");
	scanf("%d %d", &G->numvertex, &G->numedge);
	for (int i = 0; i < G->numvertex; i++)
	{
		printf("请输入序号为%d的结点的名字\n", i);
		scanf("%s", G->Amlist[i].str);
		G->Amlist[i].pEdge = NULL;
	}
	for (int k = 0; k < G->numedge; k++)
	{
		int i, j;
		printf("请输入边(Vi,Vj)的顶点序号i和j,以格式i,j输入:");
		scanf("%d,%d", &i, &j);
		AMEdge* e = (AMEdge*)malloc(sizeof(AMEdge));
		e->start = i;
		e->end = j;
		e->startlink = G->Amlist[i].pEdge;
		G->Amlist[i].pEdge = e;
		e->endlink = G->Amlist[j].pEdge;
		G->Amlist[j].pEdge = e;
	}
}

void printAMGraph(AMGraph G)
{
	for (int i = 0; i < G.numvertex; i++)
	{
		AMEdge* p = G.Amlist[i].pEdge;
		printf("结点%s的邻接边为：",G.Amlist[i].str);
		while (p != NULL)
		{
			printf("(%s,%s) ", G.Amlist[p->start].str, G.Amlist[p->end].str);
			if (p->start == i)
			{
				p = p->startlink;
			}
			else if (p->end == i)
			{
				p = p->endlink;
			}
		}
		printf("\n");
	}
}

void deleteEdge(AMGraph* G, int i, int j)
{
	if (G->numedge != 0)
	{
		AMEdge* p = G->Amlist[i].pEdge;
		AMEdge* tmp = NULL;
		AMEdge* tmp1 = NULL;
		while ((!(p->start == i && p->end == j)) && (!(p->start == j && p->end == i)))
		{
			tmp = p;
			if (p->start == i)
			{
				p = p->startlink;
			}
			else if (p->end == i)
			{
				p = p->endlink;
			}
		}
		tmp1 = p;
		if (tmp == NULL)
		{
			if (p->start == i)
			{
				G->Amlist[i].pEdge = p->startlink;
			}
			else if (p->end == i)
			{
				G->Amlist[i].pEdge = p->endlink;
			}
		}
		else
		{
			if (p->start == i)
			{
				if (tmp->start == i)
				{
					tmp->startlink = p->startlink;
				}
				else if (tmp->end == i)
				{
					tmp->endlink = p->startlink;
				}
			}
			else if (p->end == i)
			{
				if (tmp->start == i)
				{
					tmp->startlink = p->endlink;
				}
				else if (tmp->end == i)
				{
					tmp->endlink = p->endlink;
				}
			}
		}
		p = G->Amlist[j].pEdge;
		tmp = NULL;
		while ((!(p->start == i && p->end == j)) && (!(p->start == j && p->end == i)))
		{
			tmp = p;
			if (p->start == j)
			{
				p = p->startlink;
			}
			else if (p->end == j)
			{
				p = p->endlink;
			}
		}
		if (tmp == NULL)
		{
			if (p->start == j)
			{
				G->Amlist[j].pEdge = p->startlink;
			}
			else if (p->end == j)
			{
				G->Amlist[j].pEdge = p->endlink;
			}
		}
		else
		{
			if (p->start == j)
			{
				if (tmp->start == j)
				{
					tmp->startlink = p->startlink;
				}
				else if (tmp->end == j)
				{
					tmp->endlink = p->startlink;
				}
			}
			else if (p->end == j)
			{
				if (tmp->start == j)
				{
					tmp->startlink = p->endlink;
				}
				else if (tmp->end == j)
				{
					tmp->endlink = p->endlink;
				}
			}
		}
		free(tmp1);
		G->numedge--;
	}
	else
	{
	printf("图中的边已经都删除了\n");
    }
}



🍦6.3 test.c

#include "Graph.h"

void test1()
{
	MGraph G;
	createMGraph(&G);
	printMGraph(G);
}

void test2()
{
	GraphAdjList G;
	createAdjlistGraph(&G);
	printAdjlistGraph(G);
}

void test3()
{
	OLGraph G;
	createOLGraph(&G);
	printOLGraph(G);
}

void test4()
{
	AMGraph G;
	createAMGraph(&G);
	printAMGraph(G);
	for (int k = 0; k < 6; k++)
	{
		printf("请输入要删除的边,以i,j格式输入");
		int i, j;
		scanf("%d,%d", &i, &j);
		deleteEdge(&G, i, j);
		printAMGraph(G);
	}
}

int main()
{
	test1();
	test2();
	test3();
	test4();
	return 0;
}


版权声明：本文为CS_COPy原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。