1. Toy模板网首页
  2. > Toy博客

图的基本操作（邻接矩阵）

9月前 作者：青耕_ 分类：Toy博客 阅读(43) 违法举报

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

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

声明

#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语言---数据结构实验---哈夫曼树及哈夫曼编码的算法实现---图的基本操作

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

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

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

    图详解第一篇：图的基本概念及其存储结构（邻接矩阵和邻接表）

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

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

    图的邻接矩阵存储及遍历操作

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

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

    图的数据结构，系统学习图的基本概念、定义和建立，学会邻接矩阵、邻接表以及实现六度空间案例，遍历图的方式——广度、深度访问

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

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

    【数据结构】图的基本操作

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

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

    数据结构--图的基本操作

    使用的存储模式： 图的基本操作： • 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日
    浏览(50)
  • TensorFlow入门(十一、图的基本操作)

    TensorFlow入门(十一、图的基本操作)

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

    2024年02月07日
    浏览(36)

  • 6. 【图的基本操作】Adjacent、Neighbors、InsertVertex、DeleteVertex、AddEdge、RemoveEdge、FirstNeighbor、Next....

    2023年04月23日
    浏览(25)
  • 图的创建（详解邻接矩阵和邻接表）

    图的创建（详解邻接矩阵和邻接表）

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

    2024年02月06日
    浏览(39)
  • 【矩阵的基本操作】——MatLab基础

    【矩阵的基本操作】——MatLab基础

    对矩阵A加一个’就表示A的转置矩阵 横拼： 对于A、B两个矩阵，我们该怎么做到使矩阵A在左，B在右形成一个新矩阵呢？ 竖拼： 因为分号表示换号，所以用分号来进行竖直凭借 位置是一列一列从左往右数的，相当于门牌号只有一个数 取出矩阵A中第m行n列的元素 end(): 取矩阵

    2024年02月16日
    浏览(35)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包