图的基本操作(邻接矩阵)

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

图是比较常用的一种数据结构,我针对期末考试对其进行了大概整理,形成了本文。

声明

#include<iostream>
#include<fstream>
#include<queue>
#include<stack>
using namespace std;
#define MAX_V 20 // 最大顶点数目
#define READMODE 2//文件内容格式,1是完整的矩阵,2是读入边
typedef char ElemType;//元素类型
typedef int GraphKind;//图形类型
typedef struct
{
	ElemType info; // 顶点其它信息
}VertexType; // 顶点类型定义
class MGraph
{
private:
	int arcs[MAX_V][MAX_V]; // 邻接矩阵
	int num1, num2; // 图包含的顶点数以及边数
	VertexType vexs[MAX_V]; // 存放顶点信息
	GraphKind type;//如果提供的数据区分不了,默认是无向图,十位数为一代表网,没有数代表图,个位数为一代表无向,为二代表有向
public:
	MGraph();
	void BFS();//广度遍历输出图
	void DFS();//深度遍历输出图
	void dfs(bool* f, int i);//深度遍历辅助函数
	void print();//输出图的邻接矩阵
	void DJ(int b);//迪杰斯特拉(Dijkstra)算法求最短路径
	void prim();//普里姆(Prim)算法求最小生成树,输出其邻接矩阵
	void DPauxiliary(int b, int* f, bool* v, int* pre);//迪杰斯特拉算法和普里姆算法的辅助函数
};

图的建立

整体上是基于文件进行图的建立,有两种文件内容格式,READMODE ==1时,是读入顶点个数,顶点信息以及邻接矩阵,READMODE ==2时,是读入顶点个数,顶点信息,边的个数,边的信息,样例如下:
图邻接矩阵基恩操作,算法,图论,c++
图邻接矩阵基恩操作,算法,图论,c++
两种读入形成的邻接矩阵都是从1开始存,0不存数据。

READMODE ==1

if (READMODE == 1)
	{
		for (i = 1; i <= num1; i++)
		{
			for (int j = 1; j <= num1; j++)
			{
				file >> arcs[i][j];
				if (arcs[i][j] != 0 && i != j)
					num2++;
				if (arcs[i][j] > 1)
					type += 10;//网
			}
		}
		i = 0;
		if (num2 % 2 == 0)
		{
			type += 1;//无向
			num2 /= 2;//提前去掉重复统计的边
			for (int i = 1; i <= num1; i++)
			{
				for (int j = 1; j <= i; j++)
				{
					if (arcs[i][j] != arcs[j][i])
					{
						num2 *= 2;//还原边
						type += 1;//有向
						break;
					}
				}
				if (type % 10 == 2)
					break;
			}
		}
	}

READMODE==2

if (READMODE == 2)//默认是无向
	{
		file >> num2;
		for (int i = 1; i <= num1; i++)
		{
			for (int j = 1; j <= num1; j++)
			{
				if (i != j)
					arcs[i][j] = 0;
				else
					arcs[i][j] = 1;
			}
		}
		type += 1;
		for (i = 1; i <= num2; i++)
		{
			int x, y, l;
			file >> x >> y >> l;
			arcs[x][y] = arcs[y][x] = l;
			if (l > 1)
				type += 10;
		}
		
	}

遍历

无论是广度遍历还是深度遍历,其目的都是将所有点的信息进行遍历输出,不能有遗落,只不过BFS是广度优先,DFS是深度优先。

广度遍历(BFS)

广度优先的字面意思很好理解,其思想也差不多,我理解的就是一层一层访问,以最开始访问的顶点作为基准,记其层数为0,其他点几条线与之相连就是第几层,每一层的访问顺序由其上层(指的是最开始的分支层)的标号大小决定,编号小的先访问,上层完全相同的,比较本身编号大小,编号小的先访问。对于非连通图来讲,将图分成几个连通的子图,按照标号顺序访问整个子图。
这个只是个人思路,仅供参考,但是代码思路还是很清晰的:
1.先将起点入队
2.出队输出,并将与出队点直接相连的所有点入队
3.反复执行第二步
4.遍历,将所有未入队过的点从第1步开始执行,直至所有点都入队过
5.反复出队输出,直至队空

void MGraph::BFS()
{
	queue<int> q;
	bool* f = new bool[num1 + 1];
	fill(f, f + num1 + 1, 0);
	cout << "广度遍历结果为:";
	for (int i = 1; i <= num1; i++)
	{
		if (f[i] == 1)
			continue;
		q.push(i);
		f[i] = 1;
		for (int j = 1; j <= num1; j++)
		{
			if (arcs[i][j] == 0 || f[j] == 1 || j == i)//两点之间没有边,该点已经访问过,该点与先行点是一个的情况排除
				continue;
			q.push(j);//压入队列
			f[j] = 1;
		}
		cout << vexs[q.front()].info << ' ';
		q.pop();
	}
	while (!q.empty())
	{
		cout << vexs[q.front()].info << ' ';
		f[q.front()] = 1;
		q.pop();
	}
	cout << endl;
}

深度遍历(DFS)

同样的,广度优先的字面意思也很好理解,我的解释是,一条线一条线的遍历,出现分支的话,先进入编号小的一边,访问到头后,回到分支点,访问其他分支,同样的,对于非连通图来讲,将图分成几个连通的子图,按照标号顺序访问整个子图。 代码思路就是递归,首先一个大循环防止是非连通图导致访问不全。然后就是一条线一条线的进行访问,到头就返回。

void MGraph::DFS()
{
	bool* f = new bool[num1 + 1];
	fill(f, f + num1 + 1, 0);
	cout << "深度遍历结果为:";
	for (int i = 1; i <= num1; i++)
	{
		if (f[i] == 1)
			continue;
		dfs(f, i);
	}
	cout << endl;
}
void MGraph::dfs(bool* f, int i)
{
	cout << vexs[i].info << ' ';
	f[i] = 1;
	for (int j = 1; j <= num1; j++)
	{
		if (i == j || arcs[i][j] == 0 || f[j] == 1)
			continue;
		dfs(f, j);
	}
}

最短路径和最小生成树(迪杰斯特拉算法和普里姆算法)

迪杰斯特拉算法和普里姆算法很像,**都是以一个点为基准,反复从未接入过的点中选出与之最近的点,接入图中,然后更新与新接入点直接相连的点到基准点的最短路径长度,只不过迪杰斯特拉算法说的最短针对的是起点,而普里姆算法的最短针对的是新的图。**但是思想还是差不多的。
另外我写的代码是针对无向的,有向没试,但应该不行。

迪杰斯特拉算法

找最短路径就是一个大循环内嵌两个循环,大循环是为了遍历到所有的点,第一个小循环是为了寻找未接入过的点中选出与基准点最近的点,第二个小循环就是最短路径长度和前驱点的更新。

void MGraph::DJ(int b)
{
	if (type % 10 == 2)
	{
		cout << "有向图不行" << endl;
		return;
	}
	int* f;
	bool* v;
	int* pre;
	v = new bool[num1 + 1];//标记是否经过
	f = new int[num1 + 1];//记录最短距离
	pre = new int[num1 + 1];//记录最短路径的上一节点
	fill(f, f + num1 + 1, INT_MAX);
	fill(v, v + num1 + 1, false);
	for (int i = 1; i <= num1; i++)
		pre[i] = i;
	f[b] = 0;
	for (int i = 1; i <= num1; i++)
	{
		int near = -1;
		int min = INT_MAX;
		for (int j = 1; j <= num1; j++)//每次寻找到的点,都是未选过的,距离起点最近的点
		{
			if (v[j] == false && f[j] < min)
			{
				near = j;
				min = f[j];
			}
		}
		if (near == -1)
			break;
		v[near] = 1;
		for (int j = 1; j <= num1; j++)
		{
			if (arcs[near][j] != 0 && j != near && v[j] == false)
			{
				if (min + arcs[near][j] < f[j]) {
					f[j] = min + arcs[near][j];
					pre[j] = near;//pre保存当前结点的上一个节点,以便输出最短路线
				}
			}
		}
	}
	for (int i = 1; i <= num1; i++)
	{
		if (f[i] == INT_MAX)
		{
			cout << b << "和" << i << "不连通" << endl;
			continue;
		}
		if (i == b)
			continue;
		stack<int>path;
		int j = i;
		while (j != b)
		{
			path.push(j);
			j = pre[j];
		}
		cout << b << "-";
		while (!path.empty())
		{
			if (path.top() != b)
				cout << path.top();
			path.pop();
			if (!path.empty())
				cout << '-';
		}
		cout <<"        " << "最短距离是" << f[i] << endl;
	}
}

最小生成树

我是直接输出构成最小生成树的边了,找边跟最短路径差不多文章来源地址https://www.toymoban.com/news/detail-765246.html

void MGraph::prim()
{
	bool* f = new bool[num1 + 1];//是否接入新图
	int* linknode = new int[num1 + 1];//与新的图的连接点
	int *k = new int[num1 + 1];//与新的图的最小长度
	fill(f, f + num1 + 1, false);
	for (int i = 2; i <= num1; i++)
	{
		k[i] = arcs[i][1];
		if (k[i] == 0)
		{
			k[i] = 999;
			linknode[i] = 0;
		}
		else
			linknode[i] = 1;
	}
	k[1] = 0;
	f[1] = 1;
	for (int i = 2; i <= num1; i++)
	{
		int min = 999;
		int minnode = 0;
		for (int j = 2; j<= num1; j++)
		{
			if (f[j])
				continue;
			if (k[j] < min)
			{
				min = k[j];
				minnode = j;
			}
		}
		if (min == 999)
			break;
		f[minnode] = 1;
		cout << linknode[minnode] << ' ' << minnode << ' ' << k[minnode] << endl;
		for (int j = 2; j <= num1; j++)//更新
		{
			if (f[j])
				continue;
			if (arcs[j][minnode] != 0 && k[j] > arcs[j][minnode])
			{
				k[j] = arcs[j][minnode];
				linknode[j] = minnode;
			}
		}
	}
}

源代码

#include<iostream>
#include<fstream>
#include<queue>
#include<stack>
using namespace std;
#define MAX_V 20 // 最大顶点数目
#define READMODE 2//文件内容格式,1是完整的矩阵,2是读入边
typedef char ElemType;//元素类型
typedef int GraphKind;//图形类型
typedef struct
{
	ElemType info; // 顶点其它信息
}VertexType; // 顶点类型定义
class MGraph
{
private:
	int arcs[MAX_V][MAX_V]; // 邻接矩阵
	int num1, num2; // 图包含的顶点数以及边数
	VertexType vexs[MAX_V]; // 存放顶点信息
	GraphKind type;//如果提供的数据区分不了,默认是无向图,十位数为一代表网,没有数代表图,个位数为一代表无向,为二代表有向
public:
	MGraph();
	void BFS();
	void DFS();
	void dfs(bool* f, int i);
	void print();
	void DJ(int b);
	void prim();
	void DPauxiliary(int b, int* f, bool* v, int* pre);
};
int main()
{
	MGraph G;
	G.print();
	G.DFS();
	G.BFS();
	G.DJ(1);
	G.prim();
}
MGraph::MGraph()
{
	type = 0;
	num2 = 0;
	fstream file("data1.txt", ios::in);
	file >> num1;
	int j = 1, i = 1;
	while (i <= num1)
		file >> vexs[i++].info;
	if (READMODE == 1)
	{
		for (i = 1; i <= num1; i++)
		{
			for (int j = 1; j <= num1; j++)
			{
				file >> arcs[i][j];
				if (arcs[i][j] != 0 && i != j)
					num2++;
				if (arcs[i][j] > 1)
					type += 10;//网
			}
		}
		i = 0;
		if (num2 % 2 == 0)
		{
			type += 1;//无向
			num2 /= 2;//提前去掉重复统计的边
			for (int i = 1; i <= num1; i++)
			{
				for (int j = 1; j <= i; j++)
				{
					if (arcs[i][j] != arcs[j][i])
					{
						num2 *= 2;//还原边
						type += 1;//有向
						break;
					}
				}
				if (type % 10 == 2)
					break;
			}
		}
	}
	if (READMODE == 2)//默认是无向
	{
		file >> num2;
		for (int i = 1; i <= num1; i++)
		{
			for (int j = 1; j <= num1; j++)
			{
				if (i != j)
					arcs[i][j] = 0;
				else
					arcs[i][j] = 1;
			}
		}
		type += 1;
		for (i = 1; i <= num2; i++)
		{
			int x, y, l;
			file >> x >> y >> l;
			arcs[x][y] = arcs[y][x] = l;
			if (l > 1)
				type += 10;
		}
		
	}
	else
		type += 2;//有向
	cout << "这是一个" << num1 << "个顶点" << num2 << "条边" << "的";
	if (type % 10 == 2)
		cout << "有向";
	else
		cout << "无向";
	if (type / 10 > 0)
		cout << "网" << endl;
	else
		cout << "图" << endl;
}
void MGraph::BFS()
{
	queue<int> q;
	bool* f = new bool[num1 + 1];
	fill(f, f + num1 + 1, 0);
	cout << "广度遍历结果为:";
	for (int i = 1; i <= num1; i++)
	{
		if (f[i] == 1)
			continue;
		q.push(i);
		f[i] = 1;
		for (int j = 1; j <= num1; j++)
		{
			if (arcs[i][j] == 0 || f[j] == 1 || j == i)//两点之间没有边,该点已经访问过,该点与先行点是一个的情况排除
				continue;
			q.push(j);//压入队列
			f[j] = 1;
		}
		cout << vexs[q.front()].info << ' ';
		q.pop();
	}
	while (!q.empty())
	{
		cout << vexs[q.front()].info << ' ';
		f[q.front()] = 1;
		q.pop();
	}
	cout << endl;
}
void MGraph::dfs(bool* f, int i)
{
	cout << vexs[i].info << ' ';
	f[i] = 1;
	for (int j = 1; j <= num1; j++)
	{
		if (i == j || arcs[i][j] == 0 || f[j] == 1)
			continue;
		dfs(f, j);
	}
}
void MGraph::DFS()
{
	bool* f = new bool[num1 + 1];
	fill(f, f + num1 + 1, 0);
	cout << "深度遍历结果为:";
	for (int i = 1; i <= num1; i++)
	{
		if (f[i] == 1)
			continue;
		dfs(f, i);
	}
	cout << endl;
}
void MGraph::print()
{
	for (int i = 1; i <= num1; i++)
	{
		for (int j = 1; j <= num1; j++)
			cout << arcs[i][j] << ' ';
		cout << endl;
	}
}
void MGraph::DJ(int b)
{
	if (type % 10 == 2)
	{
		cout << "有向图不行" << endl;
		return;
	}
	int* f;
	bool* v;
	int* pre;
	v = new bool[num1 + 1];//标记是否经过
	f = new int[num1 + 1];//记录最短距离
	pre = new int[num1 + 1];//记录最短路径的上一节点
	fill(f, f + num1 + 1, INT_MAX);
	fill(v, v + num1 + 1, false);
	for (int i = 1; i <= num1; i++)
		pre[i] = i;
	f[b] = 0;
	for (int i = 1; i <= num1; i++)
	{
		int near = -1;
		int min = INT_MAX;
		for (int j = 1; j <= num1; j++)//每次寻找到的点,都是未选过的,距离起点最近的点
		{
			if (v[j] == false && f[j] < min)
			{
				near = j;
				min = f[j];
			}
		}
		if (near == -1)
			break;
		v[near] = 1;
		for (int j = 1; j <= num1; j++)
		{
			if (arcs[near][j] != 0 && j != near && v[j] == false)
			{
				if (min + arcs[near][j] < f[j]) {
					f[j] = min + arcs[near][j];
					pre[j] = near;//pre保存当前结点的上一个节点,以便输出最短路线
				}
			}
		}
	}
	for (int i = 1; i <= num1; i++)
	{
		if (f[i] == INT_MAX)
		{
			cout << b << "和" << i << "不连通" << endl;
			continue;
		}
		if (i == b)
			continue;
		stack<int>path;
		int j = i;
		while (j != b)
		{
			path.push(j);
			j = pre[j];
		}
		cout << b << "-";
		while (!path.empty())
		{
			if (path.top() != b)
				cout << path.top();
			path.pop();
			if (!path.empty())
				cout << '-';
		}
		cout <<"        " << "最短距离是" << f[i] << endl;
	}
}
void MGraph::prim()
{
	bool* f = new bool[num1 + 1];
	int* linknode = new int[num1 + 1];
	int *k = new int[num1 + 1];
	fill(f, f + num1 + 1, false);
	for (int i = 2; i <= num1; i++)
	{
		k[i] = arcs[i][1];
		if (k[i] == 0)
		{
			k[i] = 999;
			linknode[i] = 0;
		}
		else
			linknode[i] = 1;
	}
	k[1] = 0;
	f[1] = 1;
	for (int i = 2; i <= num1; i++)
	{
		int min = 999;
		int minnode = 0;
		for (int j = 2; j<= num1; j++)
		{
			if (f[j])
				continue;
			if (k[j] < min)
			{
				min = k[j];
				minnode = j;
			}
		}
		if (min == 999)
			break;
		f[minnode] = 1;
		cout << linknode[minnode] << ' ' << minnode << ' ' << k[minnode] << endl;
		for (int j = 2; j <= num1; j++)
		{
			if (f[j])
				continue;
			if (arcs[j][minnode] != 0 && k[j] > arcs[j][minnode])
			{
				k[j] = arcs[j][minnode];
				linknode[j] = minnode;
			}
		}
	}
}

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

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

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

相关文章

  • C语言---数据结构实验---哈夫曼树及哈夫曼编码的算法实现---图的基本操作

    本篇实验代码非本人写,代码源自外部,经调试解决了部分warning和error后在本地vs上可以正常运行,如有运行失败可换至vs 未来会重构实现该两个实验 内容要求: 1、初始化(Init):能够对输入的任意长度的字符串s进行统计,统计每个字符的频度,并建立哈夫曼树 2、建立编码

    2024年02月13日
    浏览(58)
  • 图详解第一篇:图的基本概念及其存储结构(邻接矩阵和邻接表)

    这篇文章开始,我们来学习一种高阶数据结构——图 图是由顶点集合及顶点间的关系(边)组成的一种数据结构:G = (V, E)。 其中: 顶点集合V = {x|x属于某个数据对象集}是有穷非空集合; E = {(x,y)|x,y属于V}或者E = {x, y|x,y属于V Path(x, y)}是顶点间关系的有穷集合,也叫做边的集

    2024年02月08日
    浏览(42)
  • 图的邻接矩阵存储及遍历操作

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

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

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

    2023年04月22日
    浏览(48)
  • 【数据结构】图的基本操作

    一、问题描述 分别以邻接矩阵和邻接表作为存储结构,实现以下图的基本操作: 增加一个新结点v,Insert(G,v); 删除顶点v及其相关的边,Delete(G,v); 增加一条边v,w,Insert(G,v,w); 删除一条边v,w,Delete(G,v,w); 二、设计思路 1、邻接矩阵实现:         邻接矩阵实现图的基本

    2024年02月06日
    浏览(50)
  • 数据结构--图的基本操作

    使用的存储模式: 图的基本操作: • Adjacent(G,x,y):判断图G是否存在边x, y或(x, y)。 • Neighbors(G,x):列出图G中与结点x邻接的边。 • InsertVertex(G,x):在图G中插入顶点x。 • DeleteVertex(G,x):从图G中删除顶点x。 • AddEdge(G,x,y):若无向边(x, y)或有向边x, y不存在,则向图G中添加该

    2024年02月16日
    浏览(53)
  • TensorFlow入门(十一、图的基本操作)

    建立图         一个TensorFlow程序默认是建立一个图的,除了系统自动建图以外,还可以用tf.Graph()手动建立,并做一些其他的操作         如果想要获得程序一开始默认的图,可以使用tf.get_default_graph()函数         如果想要重新建立一张图代替原来的图,可以使用tf.reset_default_gr

    2024年02月07日
    浏览(37)
  • 图的创建(详解邻接矩阵和邻接表)

    首先,我们来看一下涉及的知识点: 图 :图 G=(V,E) 由 顶点 集 V 和 边 集 E 组成。每条边对应一个点对 (v,w),其中 v,w 属于 V 。如果图中的点对是有序的,那么该图就是 有向图 ,反之为 无向图 。 邻接点 :若顶点 v 与 w 之间存在一条边,则认为顶点 v 与 w 邻接。 权 :图中

    2024年02月06日
    浏览(41)
  • matlab:基本操作与矩阵输入

    学习素材:MATLAB教程_台大郭彦甫(14课)原视频补档 MATLAB教程_台大郭彦甫(14课)原视频补档_哔哩哔哩_bilibili (部分素材使用视频截图) 目录 一、基本运算 二、 三、\\\"format\\\"  四、符号 1.“;” 2.\\\":\\\"(colon operator) 五、关于矩阵 1.a=(3,:)用此方法来表示矩阵的某一行  

    2023年04月08日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包