C语言 图的建立(邻接矩阵与邻接表)

这篇具有很好参考价值的文章主要介绍了C语言 图的建立(邻接矩阵与邻接表)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、邻接矩阵 

1.邻接矩阵表示法

邻接矩阵是用于表示图的数据结构之一,可以用二维数组来表示。在邻接矩阵中,每个顶点都对应矩阵的一行和一列,矩阵中的值表示相应两个顶点之间的连通性。如果两个顶点之间存在一条边,则矩阵中对应位置为1;否则为0。如果是网 ,则矩阵中对应位置为权值;否则为(计算机允许、大于所以边上的数)。对于无向图而言,邻接矩阵是对称的;而对于有向图而言,则不一定对称。邻接矩阵可以方便地进行图的遍历、查找和修改等操作,但是对于稀疏图(边数较少)来说,邻接矩阵会浪费大量的空间。

c语言邻接矩阵,数据结构与算法,c语言,算法,矩阵

用邻接矩阵表示法表示图除了一个用于储存邻接矩阵的二维数组外,还需要一个一维数组储存顶点信息。

储存结构如下:

#define MVNum 100//最大顶点数
#define MaxInt 66666//表示极大值
typedef struct {
	char vexs[MVNum];//顶点表(顶点为字符型)
	int arcs[MVNum][MVNum];//邻接矩阵(权值为整型)
	int vexnum, arcnum;//图的当前点数和边数
}AMGraph;

 2.采用邻接矩阵表示法创建无向网

//定位
int LocateVex(AMGraph* G, char v) {
	int i;
	for (i = 0; i < G->vexnum; i++) {
		if (G->vexs[i] == v) {
			return i;
		}
	}
	return -1;
}
//创建无向网G
AMGraph* CreateUDN() {
	int i, j, k, w;
	char v1, v2;
	AMGraph* G = malloc(sizeof(AMGraph));
	printf("输入总顶点数,边数\n");
	scanf("%d%d", &G->vexnum, &G->arcnum);
	getchar();//吸收换行符
	printf("依次输入点的信息\n");
	for (i = 0; i < G->vexnum; i++) {
		scanf("%c", &G->vexs[i]);
	}
	getchar();//吸收换行符
	for (i = 0; i < G->vexnum; i++)
	    for (j = 0; j < G->vexnum; j++) {
		    if (i == j) {
			    G->arcs[i][j] = 0;
		    }
		    else {
			    G->arcs[i][j] = MaxInt;
		    }
	}
	for (k = 0; k < G->arcnum; k++) {
		printf("输入一条边依附的顶点及权值\n");
		scanf("%c%c", &v1, &v2);
		scanf("%d", &w);
		getchar();//吸收换行符
		i = LocateVex(G, v1), j = LocateVex(G, v2);//确定v1、v2在顶点数组的下标
		G->arcs[i][j] = w;//边<v1,v2>权值置为w
		G->arcs[j][i] = w;//无向网对称边<v2,v2>权值也置为w
	}
	return G;
}

再写个输出函数

void print(AMGraph* G) {
	int i, j;
	printf("  ");
	for (i = 0; i < G->vexnum; i++) {
		printf("%c ", G->vexs[i]);
	}
	printf("\n");
	for (i = 0; i < G->vexnum; i++) {
		printf("%c ", G->vexs[i]);
		for (j = 0; j < G->vexnum; j++) {
			if (G->arcs[i][j] == MaxInt)
				printf("∞ ");
			else
				printf("%d ", G->arcs[i][j]);
		}
		printf("\n");
	}
}

如果要创建无向图,只需改动两处:一是初始化时将边的权值都初始化为0;二是构造邻接矩阵时将权值w改为1。同样,稍做修改即可建立有向图或有线网(如果你前面知识学懂了,这里肯定没问题)。

二、邻接表

1.邻接表表示法

邻接表(Adjacency List)是一种表示无向图或有向图的数据结构。它使用一个数组来存储所有顶点,每个顶点对应一个链表。链表中存储了与该顶点直接相邻的所有顶点。对于有向图,邻接表中的链表只存储指向的顶点(个数为出度)。有时,为了便于确定顶点的入度,可以建立有向图的逆邻接表

c语言邻接矩阵,数据结构与算法,c语言,算法,矩阵

邻接表储存结构如下: 

#define MVNum 100  //最大顶点数
typedef struct ArcNode {  //边表结点
	int adjvex;//邻接点在顶点数组中的下标
	struct ArcNode* next;//指向下一条边的指针
}ArcNode;

typedef struct VNode {   //表头顶点信息结构体
	char data;
	ArcNode* first;//指向第一条依附于该顶点的边的指针
}VNode, AdjList[MVNum];

typedef struct {   //图结构体
	AdjList vertices;//邻接表
	int vexnum, arcnum;//顶点数和边数
}ALGraph;

c语言邻接矩阵,数据结构与算法,c语言,算法,矩阵

2.采用邻接表表示法创建无向图 

  • 首先输入顶点数和边数
  • 对于每条边,都会关联两个顶点,所以接下里输入被关联的两个顶点
  • 通过输入的顶点调用LocateVex函数来找到这两个顶点在顶点数组中的下标
  • 创建新结点,采用头插法插入到关联顶点的表头结点指向的单链表中
//查找
int LocateVex(ALGraph* G, char v) {
	int i;
	for (i = 0; i < G->vexnum; i++) {
		if (G->vertices[i].data == v) {
			return i;
		}
	}
	return -1;
}
//无向图的创建
ALGraph* CreateALGraph() {
	int i, j, k;
	char v1, v2;
	ALGraph* G = malloc(sizeof(ALGraph));
	printf("输入顶点数和边数:\n");
	scanf("%d%d", &G->vexnum, &G->arcnum);
	getchar();//吸收换行符
	printf("依次输入顶点信息:\n");
	for (i = 0; i < G->vexnum; i++) {
		scanf("%c", &G->vertices[i].data);
		G->vertices[i].first = NULL;
	}
	getchar();//吸收换行符
	//构造边表
	for (k = 0; k < G->arcnum; k++) {
		printf("输入一条边依附的两个顶点:\n");
		scanf("%c%c", &v1, &v2);
		getchar();//吸收换行符
		i = LocateVex(G, v1), j = LocateVex(G, v2);//确定v1、v2在邻接表数组中的下标
		ArcNode* p1 = malloc(sizeof(ArcNode));//生成新的边结点*p1
		p1->adjvex = i;//邻接点序号为i
		p1->next = G->vertices[j].first;//头插法插到顶点vj的边表头部
		G->vertices[j].first = p1;
		//因为是无向图,所以生成对称的边结点*p2
		ArcNode* p2 = malloc(sizeof(ArcNode));
		p2->adjvex = j;
		p2->next = G->vertices[i].first;
		G->vertices[i].first = p2;
	}
	return G;
}

还可以写个输出邻接表的函数

void print(ALGraph* G) {
	int i;
	for (i = 0; i < G->vexnum; i++) {
		printf("顶点%c的邻结点有:", G->vertices[i].data);
		ArcNode* p = G->vertices[i].first;
		while (p != NULL) {
			printf(" %c", G->vertices[p->adjvex].data);
			p = p->next;
		}
		printf("\n");
	}
}

运行 并构建如下图所示的邻接表:

c语言邻接矩阵,数据结构与算法,c语言,算法,矩阵

 运行结果如下:

c语言邻接矩阵,数据结构与算法,c语言,算法,矩阵

 总结

c语言邻接矩阵,数据结构与算法,c语言,算法,矩阵文章来源地址https://www.toymoban.com/news/detail-768490.html

到了这里,关于C语言 图的建立(邻接矩阵与邻接表)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++数据结构之图的存储结构——邻接矩阵和邻接表实现无向图

    关键点: 1.构建二维数组 2.对应边的位置赋值为1 由于比较简单就直接上代码: 个人对邻接表实现无向图的理解如下,仅供参考:         由于无向图的组成是由多个顶点和多条无向边组成的,因此我们可以把它拆分成两个结构,分别是顶点和无向边,又由于我们是使用

    2024年02月05日
    浏览(55)
  • C语言 图的建立(邻接矩阵与邻接表)

    邻接矩阵是用于表示图的数据结构之一,可以用二维数组来表示。在邻接矩阵中,每个顶点都对应矩阵的一行和一列,矩阵中的值表示相应两个顶点之间的连通性。如果两个顶点之间存在一条边,则矩阵中对应位置为1;否则为0。如果是网 ,则矩阵中对应位置为权值;否则为

    2024年02月03日
    浏览(49)
  • 【数据结构】图的创建(邻接矩阵,邻接表)以及深度广度遍历(BFS,DFS)

    图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E),其中: 顶点集合V = {x|x属于某个数据对象集}是有穷非空集合; E = {(x,y)|x,y属于V}或者E = {x, y|x,y属于V Path(x, y)}是顶点间关系的有穷集合,也叫 做边的集合。 完全图:在有n个顶点的无向图中,若有n * (n-1)/2条边,

    2024年02月04日
    浏览(45)
  • 【图】(一)图的建立 - 邻接矩阵与邻接表 - C语言

     图相关文章: 1. 图的建立 - 邻接矩阵与邻接表 https://blog.csdn.net/m15253053181/article/details/127552328?spm=1001.2014.3001.5501 2. 图的遍历 - DFS与BFS https://blog.csdn.net/m15253053181/article/details/127558368?spm=1001.2014.3001.5501 3. 顶点度的计算 https://blog.csdn.net/m15253053181/article/details/127558599?spm=1001.2014.3

    2024年02月06日
    浏览(45)
  • 【数据结构与算法】图的基本概念 | 邻接矩阵和邻接表 | 广度优先遍历和深度优先遍历

    🌠 作者:@ 阿亮joy. 🎆 专栏:《数据结构与算法要啸着学》 🎇 座右铭:每个优秀的人都有一段沉默的时光,那段时光是付出了很多努力却得不到结果的日子,我们把它叫做扎根 图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E) ,其中: 顶点集合V = {x|x属于某

    2024年02月04日
    浏览(73)
  • 数据结构实验6 :图的存储与遍历(邻接矩阵的深度优先遍历DFS和邻接表的广度优先遍历BFS)

    利用邻接矩阵存储无向图,并从0号顶点开始进行深度优先遍历。 输入第一行是两个整数n1 n2,其中n1表示顶点数(则顶点编号为0至n1-1),n2表示图中的边数。 之后有n2行输入,每行输入表示一条边,格式是“顶点1 顶点2”,把边插入图中。 例如: 4 4 0 1 1 3 0 3 0 2 先输出存储

    2024年02月09日
    浏览(67)
  • [数据结构]:25-图深度优先遍历(邻接矩阵)(C语言实现)

    目录 前言 已完成内容 图深度优先遍历实现 01-开发环境 02-文件布局 03-代码 01-主函数 02-头文件 03-AdjMatrixFunction.cpp 04-DFS.cpp 结语         此专栏包含408考研数据结构全部内容,除其中使用到C++引用外,全为C语言代码。使用C++引用主要是为了简化指针的使用,避免二重指针的

    2023年04月10日
    浏览(48)
  • 数据结构几种常见图的邻接矩阵的画法(有向图带权值,有向图不带权值,无向图带权值,无向图不带权值)

    这不马上要期末考试了,复习的时候突然发现了有好几种图的邻接矩阵需要画,在网上找了半天结果发现也没有特别详细的总结,所以经过总结写一下吧,希望对有需要的人,有点帮助吧!!!!(如有不对还请见谅!!!!!~~~~~~) 1,有向图带权值   2.有向图不带权值

    2024年02月13日
    浏览(54)
  • 数据结构--图的存储邻接表法

    邻接矩阵: 数组实现的顺序存储,空间复杂度高,不适合存储稀疏图 邻接表: 顺序+链式存储 无向图: 边结点的数量是 2|E|, 整体空间复杂度为 O(|V| + 2|E|) 有向图: 边结点的数量是 |E|, 整体空间复杂度为 O(|V| + |E|) 图的邻接表表示方式并不唯一 color{red}图的邻接表表示方

    2024年02月16日
    浏览(47)
  • 数据结构-图的邻接表的定义与实现

    目录 一、引言 二、图的基本概念 三、图的存储方式 1. 邻接矩阵 2. 邻接表 3. 十字链表 4. 邻接多重表 四、邻接表的实现 1. 邻接表的定义 2. 邻接表的构建 3. 邻接表的遍历 五、邻接表的优缺点 六、总结 在计算机科学中,图是一种非常重要的数据结构,它是由节点和边组成的

    2024年02月03日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包