图的创建(详解邻接矩阵和邻接表)

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

首先,我们来看一下涉及的知识点:

:图 G=(V,E) 由顶点集 V 和集 E 组成。每条边对应一个点对 (v,w),其中 v,w 属于 V 。如果图中的点对是有序的,那么该图就是有向图,反之为无向图

邻接点:若顶点 v 与 w 之间存在一条边,则认为顶点 v 与 w 邻接。

:图中的每条边都可以对应一个数值,这种与边相关的数值称为权。

路径:在图 G 中,顶点 v1 到 vk 的路径是一个顶点序列 v1,v2,···,vk。

连通图:在无向图 G 中,若两个顶点之间存在路径,则认为这两个顶点是连通的。如果在无向图 G 中,任意两个顶点都是连通的,则称 G 是连通图。

完全图:若图中任意两个顶点之间都存在一条边,则该图为完全图。

稀疏图和稠密图:当图中边的数量比较少时,称该图为稀疏图;而当图接近完全图时,称该图为稠密图。

1、邻接矩阵

邻接矩阵就是运用二维数组,对于图中的每条边 (v,w) ,设置 A[v][w] 等于该权值;若不存在边(v,w),则 A[v][w]=0 。

图的创建(详解邻接矩阵和邻接表)

 

基本数据结构:

typedef struct VexType {  //顶点类型
	int code;             //顶点编号
	char data;            //顶点信息
}VexType;
typedef struct Graph {     //邻接矩阵类型
	int arcs[maxn][maxn];  //邻接矩阵
	int vexnum, arcnum;    //顶点数和边的个数
	VexType vexs[maxn];    //顶点信息
	int type;              //邻接矩阵的类型(1.无向图 2.有向图)
}Graph;

创建邻接矩阵(以带权的图为例):

void Create_Graph(Graph& G)   //创建
{
	cout << "请输入图的类型(1.无向图 2.有向图):";
	cin >> G.type;
	cout << "顶点的个数:";
	cin >> G.vexnum;
	cout << "请输入各顶点的名称:";
	for (int i = 0; i < G.vexnum; i++) {
		cin >> G.vexs[i].data;
		G.vexs[i].code = i;  //按顺序为点编号
	}
	for (int i = 0; i < G.vexnum; i++) {
		for (int j = 0; j < G.vexnum; j++) {
			G.arcs[i][j] = 0;  //邻接矩阵初始化,将所有元素的初始值设为0
		}
	}
	cout << "请输入边的个数:";
	cin >> G.arcnum;
	cout << "请输入各边起点和终点的编号及权重:" << endl;
	int x, y, w;  //x:起始点,y:终点,w:权重
	for (int i = 0; i < G.arcnum; i++) {
		cin >> x >> y >> w;
		if (G.type == 1) {  //如果是无向图,对称边也要赋值为权重
			G.arcs[x][y] = w;
			G.arcs[y][x] = w;
		}
		else {
			G.arcs[x][y] = w;
		}
	}
}

 全部代码:

# include <iostream>
# include <iomanip>
# include <queue>
# define maxn 20
using namespace std;
typedef struct VexType {  //顶点类型
	int code;             //顶点编号
	char data;            //顶点信息
}VexType;
typedef struct Graph {     //邻接矩阵类型
	int arcs[maxn][maxn];  //邻接矩阵
	int vexnum, arcnum;    //顶点数和边的个数
	VexType vexs[maxn];    //顶点信息
	int type;              //邻接矩阵的类型(1.无向图 2.有向图)
}Graph;

void Create_Graph(Graph& G)   //创建
{
	cout << "请输入图的类型(1.无向图 2.有向图):";
	cin >> G.type;
	cout << "顶点的个数:";
	cin >> G.vexnum;
	cout << "请输入各顶点的名称:";
	for (int i = 0; i < G.vexnum; i++) {
		cin >> G.vexs[i].data;
		G.vexs[i].code = i;  //按顺序为点编号
	}
	for (int i = 0; i < G.vexnum; i++) {
		for (int j = 0; j < G.vexnum; j++) {
			G.arcs[i][j] = 0;  //邻接矩阵初始化,将所有元素的初始值设为0
		}
	}
	cout << "请输入边的个数:";
	cin >> G.arcnum;
	cout << "请输入各边起点和终点的编号及权重:" << endl;
	int x, y, w;  //x:起始点,y:终点,w:权重
	for (int i = 0; i < G.arcnum; i++) {
		cin >> x >> y >> w;
		if (G.type == 1) {  //如果是无向图,对称边也要赋值为权重
			G.arcs[x][y] = w;
			G.arcs[y][x] = w;
		}
		else {
			G.arcs[x][y] = w;
		}
	}
}

void Print_Graph(Graph G)     //打印邻接矩阵
{
	cout << "\n该图的邻接矩阵为:" << endl;
	cout.setf(ios::left); //输出左对齐
	cout << setw(4) << "";
	for (int i = 0; i < G.vexnum; i++) {
		cout << setw(4) << G.vexs[i].data;
	}
	cout << endl;
	for (int i = 0; i < G.vexnum; i++) {
		cout << setw(4) << G.vexs[i].data;
		for (int j = 0; j < G.vexnum; j++) {
			cout << setw(4) << G.arcs[i][j];
		}
		cout << endl;
	}
	cout << endl;
}

int main()
{
	Graph G;
	Create_Graph(G);     //创建
	Print_Graph(G);      //打印邻接矩阵
	cout << endl;
	return 0;
}

 运行结果:

请输入图的类型(1.无向图 2.有向图):1
顶点的个数:8
请输入各顶点的名称:A B C D E F G H
请输入边的个数:9
请输入各边起点和终点的编号及权重:
0 1 3
0 2 12
1 3 5
1 4 6
2 3 7
2 4 10
5 6 9
5 7 4
6 7 13
该图的邻接矩阵为:
    A   B   C   D   E   F   G   H
A   0   3   12  0   0   0   0   0
B   3   0   0   5   6   0   0   0
C   12  0   0   7   10  0   0   0
D   0   5   7   0   0   0   0   0
E   0   6   10  0   0   0   0   0
F   0   0   0   0   0   0   9   4
G   0   0   0   0   0   9   0   13
H   0   0   0   0   0   4   13  0

 采用邻接矩阵表示图的优点是非常简单,但他的空间复杂度为O(n^2),n表示图中顶点的数目。若图是稠密图,则邻接矩阵是合适的表示方法;但如果图是稀疏图,就不适合采用邻接矩阵了。此时,一种更好的解决办法是使用邻接表。

2、邻接表

邻接表是图的一种链式存储结构。他用 n 个带头结点的单链表代替邻接矩阵的 n 行,并对图中的每个顶点 v 建立一个带头结点的单链表,将顶点 v 的相关信息存放在表头,表中其余的结点用来存放与顶点 v 相关的边的信息。此时的空间需求是O(n+e)(e表示图中包含的边的数目)。

图的创建(详解邻接矩阵和邻接表)

基本数据结构:

typedef struct ArcNode {  //边的结点结构类型
	int adjvex;           //该边的终点编号
	int weight;           //该边的权值
	struct ArcNode* nextarc;  //指向下一条边的指针
}ArcNode;
typedef struct VexNode {  //顶点结构
	char data;
	ArcNode* firstarc;    //指向第一条与该顶点有关的边的指针
}VexNode;
typedef struct Graph {    //邻接表结构类型
	VexNode* VNode;       //定义邻接表
	int vexnum, arcnum;   //顶点数和边的个数
	int type;             //图的种类
	int size;             //邻接表的大小
}Graph;

创建邻接表:

void Create_Graph(Graph& G)   //创建
{
	cout << "请输入图的类型(1.无向图 2.有向图):";
	cin >> G.type;
	cout << "顶点的个数:";
	cin >> G.vexnum;
	G.VNode = (VexNode*)malloc(SIZE * sizeof(VexNode));
	G.size = SIZE;
	while (G.size < G.vexnum) {   //根据点的个数动态分配空间
		G.VNode = (VexNode*)realloc(G.VNode, (G.size + NEWSIZE) * sizeof(VexNode));
		G.size += NEWSIZE;
	}
	Visit = (int*)malloc((G.size + 10) * sizeof(int));
	cout << "请输入各顶点的名称:";
	for (int i = 0; i < G.vexnum; i++) {
		cin >> G.VNode[i].data;
		G.VNode[i].firstarc = NULL;  //邻接表初始化,所有单向链表均为空表
	}
	cout << "请输入边的个数:";
	cin >> G.arcnum;
	cout << "请输入各边起点和终点的编号及权重:" << endl;
	int x, y, w;    //x:起始点,y:终点,w:权重
	ArcNode* p, * q;
	for (int i = 0; i < G.arcnum; i++) {
		cin >> x >> y >> w;
		p = (ArcNode*)malloc(sizeof(ArcNode)); //创建一个用于存放当前边的结点p
		p->nextarc = NULL;
		p->adjvex = y;
		p->weight = w;
		q = G.VNode[x].firstarc;
		//将边按顺序插入到链表末尾
		if (q == NULL) {   
			G.VNode[x].firstarc = p;
		}
		else {
			while (q->nextarc != NULL) { 
				q = q->nextarc;
			}
			q->nextarc = p;
		}
		if (G.type == 1) {    //如果是无向图,要再创建一个表示对称边的结点p
			p = (ArcNode*)malloc(sizeof(ArcNode));
			p->nextarc = NULL;
			p->adjvex = x;
			p->weight = w;
			q = G.VNode[y].firstarc;
			if (q == NULL) {
				G.VNode[y].firstarc = p;
			}
			else {
				while (q->nextarc != NULL) {
					q = q->nextarc;
				}
				q->nextarc = p;
			}
		}
	}
}

全部程序:

# include <iostream>
# include <queue>
# define SIZE 20
# define NEWSIZE 20
using namespace std;
typedef struct ArcNode {  //边的结点结构类型
	int adjvex;           //该边的终点编号
	int weight;           //该边的权值
	struct ArcNode* nextarc;  //指向下一条边的指针
}ArcNode;
typedef struct VexNode {  //顶点结构
	char data;
	ArcNode* firstarc;    //指向第一条与该顶点有关的边的指针
}VexNode;
typedef struct Graph {    //邻接表结构类型
	VexNode* VNode;       //定义邻接表
	int vexnum, arcnum;   //顶点数和边的个数
	int type;             //图的种类
	int size;             //邻接表的大小
}Graph;

void Create_Graph(Graph& G)   //创建
{
	cout << "请输入图的类型(1.无向图 2.有向图):";
	cin >> G.type;
	cout << "顶点的个数:";
	cin >> G.vexnum;
	G.VNode = (VexNode*)malloc(SIZE * sizeof(VexNode));
	G.size = SIZE;
	while (G.size < G.vexnum) {   //根据点的个数动态分配空间
		G.VNode = (VexNode*)realloc(G.VNode, (G.size + NEWSIZE) * sizeof(VexNode));
		G.size += NEWSIZE;
	}
	Visit = (int*)malloc((G.size + 10) * sizeof(int));
	cout << "请输入各顶点的名称:";
	for (int i = 0; i < G.vexnum; i++) {
		cin >> G.VNode[i].data;
		G.VNode[i].firstarc = NULL;  //邻接表初始化,所有单向链表均为空表
	}
	cout << "请输入边的个数:";
	cin >> G.arcnum;
	cout << "请输入各边起点和终点的编号及权重:" << endl;
	int x, y, w;    //x:起始点,y:终点,w:权重
	ArcNode* p, * q;
	for (int i = 0; i < G.arcnum; i++) {
		cin >> x >> y >> w;
		p = (ArcNode*)malloc(sizeof(ArcNode)); //创建一个用于存放当前边的结点p
		p->nextarc = NULL;
		p->adjvex = y;
		p->weight = w;
		q = G.VNode[x].firstarc;
		//将边按顺序插入到链表末尾
		if (q == NULL) {   
			G.VNode[x].firstarc = p;
		}
		else {
			while (q->nextarc != NULL) { 
				q = q->nextarc;
			}
			q->nextarc = p;
		}
		if (G.type == 1) {    //如果是无向图,要再创建一个表示对称边的结点p
			p = (ArcNode*)malloc(sizeof(ArcNode));
			p->nextarc = NULL;
			p->adjvex = x;
			p->weight = w;
			q = G.VNode[y].firstarc;
			if (q == NULL) {
				G.VNode[y].firstarc = p;
			}
			else {
				while (q->nextarc != NULL) {
					q = q->nextarc;
				}
				q->nextarc = p;
			}
		}
	}
}

int main()
{
	Graph G;
	Create_Graph(G);     //创建
	cout << endl;
	return 0;
}

以上是我的个人学习成果,很高兴与大家分享。文章来源地址https://www.toymoban.com/news/detail-463394.html

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

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

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

相关文章

  • 数据结构——图的基本定义以及图的存储结构,邻接矩阵,邻接表

    目录 图的定义和术语 图的存储结构 顺序存储结构—邻接矩阵 链式存储结构 邻接表 邻接多重表 十字链表 图的遍历 图的连通性问题 有向无环图及其应用 最短路径 图的定义:图是一种非线性的复杂的数据结构,图中的数据元素的关系是多对多的关系 ,在图中我们常常把数

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

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

    2024年02月03日
    浏览(46)
  • 【数据结构】邻接矩阵和邻接图的遍历

    本篇文章开始学习数据结构的图的相关知识,涉及的基本概念还是很多的。 本文的行文思路: 学习图的基本概念 学习图的存储结构——本文主要介绍邻接矩阵和邻接表 对每种结构进行深度优先遍历和广度优先遍历 话不多说,狠活献上 等等,先别急,正式学习之前先认识几个

    2024年02月04日
    浏览(49)
  • 图的存储 —— 邻接矩阵

    图的结构比较复杂,任何两个节点之间都可能有关系。 图的存储分为顺序存储和链式存储。 顺序存储包括邻接矩阵和边集数组, 链式存储包括邻接表、链式前向星、十字链表和邻接多重表。 图的存储 —— 邻接矩阵 邻接矩阵通常采用一个一维数组存储图中节点的信息,采用

    2024年02月06日
    浏览(38)
  • 无向图的邻接矩阵

    无向图的邻接矩阵的定义、表示法、度 定义 逻辑结构分为两部分:V和E集合,其中,V是顶点,E是边。因此,用一个一维数组存放图中所有顶点数据;用一个二维数组存放顶点间关系(边或弧)的数据,这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻

    2024年02月04日
    浏览(35)
  • 图论01-【无权无向】-图的基本表示-邻接矩阵/邻接表

    https://github.com/Chufeng-Jiang/Graph-Theory/tree/main/src/Chapt01_Adjacency 代码有删减 代码有删减 只需要改动一行 adj = new TreeSet[V]; //构造邻接表, V行,V个LinkedList 代码有删减

    2024年02月07日
    浏览(40)
  • 图的基本操作(邻接矩阵)

    图是比较常用的一种数据结构,我针对期末考试对其进行了大概整理,形成了本文。 整体上是基于文件进行图的建立,有两种文件内容格式,READMODE ==1时,是读入顶点个数,顶点信息以及邻接矩阵,READMODE ==2时,是读入顶点个数,顶点信息,边的个数,边的信息,样例如下:

    2024年02月04日
    浏览(44)
  • 【图】(一)图的建立 - 邻接矩阵与邻接表 - 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日
    浏览(44)
  • 图的邻接矩阵存储及遍历操作

    任务描述 本关任务:要求从文件输入顶点和边数据,包括顶点信息、边、权值等,编写程序实现以下功能。 1)构造无向网G的邻接矩阵和顶点集,即图的存储结构为邻接矩阵。 2)输出无向网G的各顶点和邻接矩阵。 3)输出无向网G中顶点H的所有邻接顶点。 测试说明 平台会对

    2024年02月06日
    浏览(39)
  • 图的存储--邻接矩阵/边集数组/邻接表/链式邻接表/链式前向星

    使用二维数组w[u][v]存储点u到点v的边的权值。 一般应用在点数不多的稠密图 时间复杂度:O(n 2 ) 空间复杂度:O(n 2 ) 边集数组e[i]存储第i条边的「起点、终点、边权」。在kruskal算法中,将边按边权排序,直接存边。 时间复杂度:O(nm) 空间复杂度:O(m) 出边数组e[u][i]存储u的所

    2024年02月02日
    浏览(36)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包