图论基础: 邻接矩阵与邻接表(c++实现)

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

邻接矩阵

邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。

设G=(顶点,边):G=(V,E)是一个图。其中V={v1,v2,…,vn} [1] 。G的邻接矩阵是一个具有下列性质的n阶方阵:

  1. 无向图的邻接矩阵一定是成对角线对称的,是一个对称矩阵,有向图不一定是对称的。
  2. 有向图当把它的行i固定时,遍历每一列j,得到的是顶点i的出度;当把列j固定时,遍历每一行,得到的是顶点i的入度。
    c++邻接矩阵,数据结构与算法,图论,c++,算法

c++邻接矩阵,数据结构与算法,图论,c++,算法

  1. 对于n个顶点和e条边的邻接矩阵存储时占用的空间是O(n^2),与边数e无关,邻接矩阵适合用于存储稠密图,任何图的邻接矩阵的表示都是唯一,图采用邻接矩阵来描述i,j之间的边很容易。

临界矩阵的结构分为两部分:V和E集合,其中,V是顶点,E是边。

因此,用一个一维数组存放图中所有顶点数据;用一个二维数组存放顶点间关系(边或弧)的数据,这个二维数组称为邻接矩阵

邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵

#define INF 0x3F3F3F3F
constexpr auto MAXN = 100;
//存储图中所有顶点的数据:一维数组
struct Vertex
{
	int Vid;		//顶点编号
	string VInfo;	//顶点信息
};
//存储图中的顶点与边关系:二维数组
struct Graph
{
	int e, n;	//e: 实际边数 n:实际定点数
	Vertex vers[MAXN];		//顶点集合
	int edge[MAXN][MAXN];	//边的集合
}A;

图的邻接矩阵的表示格式:

邻接矩阵
1. 不带权的图的邻接矩阵的表示形式:
			{ 1 :对于无向图(i,j)(j,i),对于有向图<i,j>
	A[i][j]=  0 :i == j
			  0 :其他情况 
			}
2. 带权的图的邻接矩阵的表示形式:
			{ w :对于无向图(i,j)(j,i),对于有向图<i,j>
	A[i][j]=  0	:i == j
			  INF :其他情况
			}
#include <iostream>
#include <vector>
using namespace std;

#define INF 0x3F3F3F3F
//1.创建邻接矩阵
constexpr auto MAXN = 100;
struct Vertex
{
	int Vid;		//顶点编号
	string VInfo;	//顶点信息
};
struct Graph
{
	int e, n;	//e: 实际边数 n:实际定点数
	Vertex vers[MAXN];		//顶点集合
	int edge[MAXN][MAXN];	//边的集合
};
class adjacent_matrix
{
public:
	adjacent_matrix() {}
	~adjacent_matrix() {}
	//1. 创建图的邻接矩阵
	void CreateGraph(vector<vector<int>>& A, int n, int e)
	{
		g.e = e;
		g.n = n;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				g.edge[i][j] = A[i][j];
			}
		}
	}
	//2.输出图
	friend ostream& operator<<(ostream& os, adjacent_matrix lhs)
	{
		for (int i = 0; i < lhs.g.n; i++)
		{
			for (int j = 0; j < lhs.g.n; j++)
			{
				if (lhs.g.edge[i][j] < INF)
				{
					os << lhs.g.edge[i][j] << " ";
				}
				else
				{
					os << "* ";
				}
			}
			os << endl;
		}
		return os;
	}
	//3. 求顶点度的运算
	//	3.1无向图的顶点度
	int Degree1(int v)
	{
		int d = 0;
		if (v < 0 || v >= g.n)
		{
			return -1;
		}
		for (int i = 0; i < g.n; i++)
		{
			if (g.edge[v][i] > 0 && g.edge[v][i] < INF)
			{
				d++;
			}
		}
		return d;
	}
	//	3.2有向图的定点度
	int Degree2(int v)
	{
		int d = 0;
		if (v < 0 || v >= g.n)
		{
			return -1;
		}
		for (int i = 0; i < g.n; i++)
		{
			if (g.edge[v][i] > 0 && g.edge[v][i] < INF)
			{
				//行:求出度
				d++;
			}
		}
		for (int i = 0; i < g.n; i++)
		{
			if (g.edge[i][v] > 0 && g.edge[i][v] < INF)
			{
				//列:求入度
				d++;
			}
		}
		return d;
	}
public:
	Graph g;
};

int main()
{
	adjacent_matrix a;
	int n = 5, e = 7;
	vector<vector<int>> A = {
		{0,1,2,6,INF},
		{INF,0,INF,4,5},
		{INF,INF,0,INF,3},
		{INF,INF,INF,0,INF},
		{INF,INF,INF,7,0}
	};
	a.CreateGraph(A, n, e);
	cout << a;
	cout << "顶点及其度:" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << i << ":--" << a.Degree2(i) << endl;
	}
	return 0;
}

c++邻接矩阵,数据结构与算法,图论,c++,算法

邻接表

邻接表,是一种链式存储结构,存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中。

c++邻接矩阵,数据结构与算法,图论,c++,算法

在邻接表中:

  1. 图中每个顶点建立一个带头节点的单链表,单链表的所有节点由与这个顶点所相邻的所有顶点构成的节点组成。
  2. 每个顶点构成一条边,称为边节点
  3. 所有的顶点的单链表构成一个数组,称为头节点数组
//边节点
struct Node
{
	int Neid;		//相邻点节点的序号
	int weight;		//节点权值
	Node* next;		//指向下一个节点的指针
};

//每个顶点的单链表
struct VexNode
{
	string VexInfo;	//第一个顶点的信息
	Node* head;		//单链表的头节点类型
};

//图
struct Graph
{
	int n, e;				//n:实际顶点数 e:实际边数
	VexNode graph[MAXN];	//单链表数组
};

完整代码:文章来源地址https://www.toymoban.com/news/detail-754570.html

#include "change.h"
/*
邻接表:以链式结构存储图的结构
*/
#define MAXN 100
#define INF 0x3F3F3F3F
//边节点
struct Node
{
	int Neid;		//相邻点节点的序号
	int weight;		//节点权值
	Node* next;		//指向下一个节点的指针
};

//每个顶点的单链表
struct VexNode
{
	string VexInfo;	//第一个顶点的信息
	Node* head;		//单链表的头节点类型
};

//图
struct Graph
{
	int n, e;				//n:实际顶点数 e:实际边数
	VexNode graph[MAXN];	//单链表数组
};

//邻接表
class AdjGraph
{
public:
	AdjGraph()
	{
		G = nullptr;
	}
	~AdjGraph() {}
	//创建邻接表
	void CreateGraph(vector<vector<int>> A, int n, int e)
	{
		G = new Graph;
		G->n = n; G->e = e;
		//首先初始化图中全部顶点的单链表为nullptr
		for (int i = 0; i < G->n; i++)
		{
			G->graph[i].head = nullptr;
		}
		for (int i = 0; i < G->n; i++)
		{
			//单链表连接的时候从小到大
			for (int j = G->n - 1; j >= 0; j--)
			{
				if (A[i][j] > 0 && A[i][j] < INF)
				{
					Node* p = new Node;
					p->Neid = j;
					p->weight = A[i][j];
					//单链表头插
					p->next = G->graph[i].head;
					G->graph[i].head = p;
				}
			}
		}
	}
	//销毁邻接表
	void destroyGraph()
	{
		for (int i = 0; i < G->n; i++)
		{
			//遍历图中每一个顶点单链表
			Node* temp = nullptr;
			Node* cur = G->graph[i].head;
			while (cur)
			{
				temp = cur->next;
				memset(cur, NULL, sizeof(cur));
				delete cur;
				cur = nullptr;
				cur = temp;
			}
		}
	}
	//输出图
	void display()
	{
		for (int i = 0; i < G->n; i++)
		{
			//遍历每个顶点单链表
			cout << i << ": ";
			Node* head = G->graph[i].head;
			while (head)
			{
				cout << "->";
				cout << head->Neid << "(" << head->weight << ")";
				head = head->next;
			}
			cout << endl;
		}
	}
	//求顶点的度:无向图的单链表的节点个数就是该节点的度
	int Degree1(int v)
	{
		int d = 0;
		auto head =  G->graph[v].head;
		while (head)
		{
			d++;
			head = head->next;
		}
		return d;
	}
	//有向图的顶点的度:出度+入度
	int Degree2(int v)
	{
		int d = 0;
		Node* outhead = G->graph[v].head;
		//求出度:顶点单链表的节点个数
		while (outhead)
		{
			d++;
			outhead = outhead->next;
		}
		//求入度:每个单链表中是否存在此顶点节点
		for (int i=0;i<G->n;i++)
		{
			Node* cur = G->graph[i].head;
			while (cur)
			{
				if (cur->Neid == v)
				{
					d++;
					break;
				}
				cur = cur->next;
			}
		}
		return d;
	}
public:
	Graph* G;
};

//练习1:邻接矩阵转换为邻接表
Graph* change1(matrix lhs)
{
	Graph* nG = new Graph;
	nG->n = lhs.g.n;
	nG->e = lhs.g.e;
	for (int i = 0; i < nG->n; i++)
	{
		nG->graph[i].head = nullptr;
	}
	for (int i = 0; i < lhs.g.n; i++)
	{
		//邻接矩阵:行出度,列入度
		for (int j = lhs.g.n - 1; j >= 0; j--)
		{
			//行:出度
			if (lhs.g.edge[i][j] > 0 && lhs.g.edge[i][j] < INF)
			{
				//<i,j>是一个路径
				Node* node = new Node;
				node->Neid = j;
				node->weight = lhs.g.edge[i][j];

				//头插
				node->next = nG->graph[i].head;
				nG->graph[i].head = node;
			}
		}
	}

	return nG;
}
//练习1:邻接表转换为邻接矩阵
void change2(matrixGraph &g,Graph* lhs)
{
	g.e = lhs->e;
	g.n = lhs->n;
	for (int i = 0; i < g.n; i++)
	{
		for (int j = 0; j < g.n; j++)
		{
			//对角线元素置零,其他元素置INF
			if (i == j) g.edge[i][j] = 0;
			else g.edge[i][j] = INF;
		}
	}
	for (int i = 0; i < lhs->n; i++)
	{
		//顶点出度:遍历每一个顶点单链表的节点
		Node* cur = lhs->graph[i].head;
		while (cur)
		{
			// i->j
			g.edge[i][cur->Neid] = cur->weight;
			cur = cur->next;
		}
	}
}
int main()
{
	AdjGraph Ga;
	int n = 5, e = 7;
	vector<vector<int>> A = {
		{0,1,2,6,INF},
		{INF,0,INF,4,5},
		{INF,INF,0,INF,3},
		{INF,INF,INF,0,INF},
		{INF,INF,INF,7,0}
	};
	Ga.CreateGraph(A, n, e);
	Ga.display();
	cout << "顶点及其度:" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << i << ":--" << Ga.Degree2(i) << endl;
	}

	matrix ga;
	ga.CreateGraph(A, n, e);
	cout << ga;
	cout << "顶点及其度:" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << i << ":--" << ga.Degree2(i) << endl;
	}
	//邻接矩阵转化为邻接表
	auto Gp =  change1(ga);
	//邻接表转换为邻接矩阵
	matrixGraph g;
	change2(g,Gp);

	return 0;
}

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

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

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

相关文章

  • 【C语言\数据结构】图dijkstra最短路径 邻接矩阵(无项、有权)代码简单实现深度解析

    这个代码是在图的邻接矩阵(无项、有权)的代码的基础上,添加了dijkstra最短路径函数,并且修改测试用例和主函数代码,图的邻接矩阵(无项、有权)的代码具体请查看 【C语言数据结构】图之邻接矩阵(无向、有权)代码简单实现,这里就不过多赘述。 我们用一个案例

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

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

    2024年02月04日
    浏览(52)
  • 【数据结构】邻接矩阵法

    顶点用一维数组Vex表示,其中可存放较为复杂的信息(如下标),边表用二维数组Edge表示,存放边的信息(两顶点之间有直接相连的边为1,否则为0)。  如何求顶点的入度 、出度? 对于无向图  第 i 个节点的度: 该结点所在行列的非0元素个数 对于有向图  第i个节点的

    2024年02月12日
    浏览(60)
  • 图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问

    图 :G = (V,E) Graph = (Vertex, Edge) V:顶点(数据元素)的有穷非空集合; E:边的有穷集合。 有向图 :每条边都是有方向的     无向图 :每条边都是无方向的   完全图 :任意两点之间都有一条边相连    无向完全图:n个顶点,n(n-1)/2条边 无向完全图:n个顶点,n(n-1)条边 稀疏

    2023年04月22日
    浏览(49)
  • 【数据结构与算法】图——邻接表与邻接矩阵

    图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中, G表示一个图,V是顶点的集合,E是边的集合 。 在图中数据元素,我们则称之为顶点(Vertex)。 图中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是

    2024年02月02日
    浏览(43)
  • 数据结构——图的基本定义以及图的存储结构,邻接矩阵,邻接表

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

    2024年02月04日
    浏览(58)
  • 24考研数据结构-图的存储结构邻接矩阵

    【1】顶点的结点结构 ——————— | data | firstarc | ——————— data数据域:储存顶点vi firstarc链域:指向链表中第一个结点 【2】弧的结点结构 —————————— | adjvex | info | nextarc | —————————— adjvex邻接点域:与顶点vi邻接的点在图中的位置 info数据域

    2024年02月14日
    浏览(57)
  • 数据结构——图篇(邻接矩阵、邻接表、深度优先搜索、广度优先搜索)

    描述 图比树更为复杂,展现的是一种多对多的关系,图的结构是任意两个数据对象之间都可能存在某种特定的关系的数据结构 概念 顶点 : 基本介绍 顶点集合表示为V集合,要求图中顶点至少要有一个,即V集合不能为空集。通常使用|V|来表示顶点的个数,通常使用E(V)来表示

    2024年02月04日
    浏览(41)
  • 数据结构-邻接矩阵的创建与遍历

    上篇文章已经介绍了邻接矩阵的具体作用与如果利用邻接矩阵寻找相邻顶点,这次介绍重点为邻接矩阵的创建与两种遍历方式 邻接矩阵的创建 其结构体需要能记录顶点、顶点数、边数及邻接矩阵,即 创建方式则为读入边数、顶点数即各边的两个顶点和权值 图的遍历 DFS(深

    2024年02月20日
    浏览(47)
  • 【数据结构】图的创建(邻接矩阵,邻接表)以及深度广度遍历(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)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包