图论基础： 邻接矩阵与邻接表（c++实现）

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

文章目录

邻接矩阵

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

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

  1. 无向图的邻接矩阵一定是成对角线对称的是一个对称矩阵有向图不一定是对称的。
  2. 有向图当把它的行i固定时遍历每一列j得到的是顶点i的出度当把列j固定时遍历每一行得到的是顶点i的入度。
    在这里插入图片描述

在这里插入图片描述

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

临界矩阵的结构分为两部分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;
}

在这里插入图片描述

邻接表

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

在这里插入图片描述

在邻接表中

  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];	//单链表数组
};

完整代码

#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;
}
阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
标签: c++
返回列表

上一篇：CORS预请求

下一篇：Vue2框架 基础知识1

“图论基础： 邻接矩阵与邻接表（c++实现）” 的相关文章

【C++】通过栈/队列/优先级队列/反向迭代器了解适配器及仿函数1年前 (2023-02-02)
希尔排序的思路与C++实现1年前 (2023-02-02)
蓝桥杯C/C++百校真题赛（3期）Day3(考勤刷卡、最大和)1年前 (2023-02-02)
LeetCode 329. 矩阵中的最长递增路径（C++）*1年前 (2023-02-02)
C++11 std::function 基础用法1年前 (2023-02-02)
C/C++编程题之购物清单1年前 (2023-02-02)
C/C++编程题之字符串反转1年前 (2023-02-02)
2023/1 寒假期间自学c++计划安排1年前 (2023-02-02)
Visual C++6.0安装教程（win10版）及“应用程序无法正常启动（0x0150002）”解决办法1年前 (2023-02-02)
如何学习C++图像处理？1年前 (2023-02-02)

阿里云国际版