首页 > 编程学习 > C++图的建立---邻接矩阵-----邻接表

C++图的建立---邻接矩阵-----邻接表

发布时间:2022/11/10 4:53:31

目录

图的表示方式

 邻接矩阵

邻接表

图的遍历

深度优先遍历

深度优先遍历算法步骤: 

图的广度优先遍历 

广度优先遍历算法步骤: 

图的邻接矩阵存储来创建图

代码 

运行结果: 

 图的邻接表存储来创建图

如下图:

运行结果:


图的表示方式

  • 图的表示方式有两种:
  • 二维数组表示(邻接矩阵);链表表示(邻接表) 

 邻接矩阵

​ 邻接矩阵 邻接矩阵:邻接矩阵 是表示图形中顶点之间相邻关系的矩阵 

邻接表

  1.  邻接矩阵需要为每个顶点都分配 n 个边的空间,其实有很多边都是不存在的,会造成空间的一定损失.
  2. 邻接表的实现只关心存在的边,不关心不存在的边。因此没有空间浪费,邻接表由数组+链表组成.

图的遍历

  • 所谓图的遍历,即是对结点的访问。一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种访问策略:
  1. 深度优先遍历
  2. 广度优先遍历

深度优先遍历

  • 深度优先遍历算法步骤: 

  1. 访问初始结点 v,并标记结点 v 为已访问
  2. 查找结点 v 的第一个邻接结点 w
  3. 若 w 存在,则继续访问 4,如果 w 不存在,则回到第 1 步,将从 v 的下一个结点继续
  4. 若 w 未被访问,对 w 进行深度优先遍历递归(即把 w 当作另一个 v ,然后进行步骤 123)
  5. 查找结点 v 的 w 邻接结点的下一个邻接结点,转到步骤 3
     
  • 核心代码: 

//深度优先遍历
void MyGraph::DFSearch(int v) {
	cout << vertex[v]<<" ";
	visited[v] = 1;
	for (int i = 0; i < vertexNum; i++) {
		if (edge[v][i] == 1 && visited[i] == 0) {
			DFSearch(i);
		}
	}
}

图的广度优先遍历 

  • 图的广度优先遍历(Broad First Search)
  • 类似于一个分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来访问这些结点的邻接结点

广度优先遍历算法步骤: 

  1. 访问初始结点 v 并标记结点 v 为已访问
  2. 结点 v 入队列
  3. 当队列非空时,继续执行,否则算法结束
  4. 出队列,取得头结点 u
  5. 查找结点 u 的第一个邻接结点 w
  6. 若结点 u 的邻接结点 w 不存在,则转到步骤 3;否则循环执行以下三个步骤
  1. >>若结点 w 尚未被访问,则访问结点 w 并标记为已访问
  2. >>结点 w 入队列
  3. >>查找结点 u 的继 w 邻接结点后的下一个邻接结点 w,转到步骤6
  •  核心代码

//广度优先遍历
void MyGraph::BFSearch(int v){
	int w, j;
	int Q[MaxSize];			//采用顺序队列
	int front=-1, rear=-1;	//初始化队列
	cout << vertex[v] << " ";
	visited[v] = 1;

	Q[++rear] = v;		//被访问的顶点入队
	while (front != rear) {
		w = Q[++front];//将对头元素出队并送到v中
		for (j = 0; j < vertexNum; j++) {
			if (edge[w][j] == 1 && visited[j] == 0) {
				cout << vertex[j] << " ";
				visited[j] = 1;
				Q[++rear] = j;
			}
		}
	}
}

图的邻接矩阵存储来创建图

  • 代码 

/*
* 图的邻接矩阵存储----
*					图的建立与遍历:
*								   广度优先遍历---深度优先遍历
*/
#include<iostream>
using namespace std;

const int MaxSize = 10;

int visited[MaxSize] = { 0 };//全局变量visited初始化——遍历的标志

class MyGraph {
private:
	char vertex[MaxSize];//存放顶点的数组
	char edge[MaxSize][MaxSize];//存放边的数组
	int vertexNum;//图的顶点数
	int edgeNum;//图的边数
public:
	MyGraph(char a[], int n, int e);//传数组,顶点数,边数
	~MyGraph();
	void DFSearch(int v);//深度优先遍历
	void BFSearch(int v);//广度优先遍历
};

//图的建立
MyGraph::MyGraph(char a[], int n, int e){
	int i, j, k;
	this->vertexNum = n;	 //图的顶点数
	this->edgeNum = e;		//图的边数

	//储存顶点
	for (i = 0; i < vertexNum; i++) {
		vertex[i] = a[i];
	}

	//初始化邻接矩阵
	for (i = 0; i < vertexNum; i++) {
		for (j = 0; j < vertexNum; j++) {
			edge[i][j] = 0;
		}
	}

	cout << "请输入边依附的两个顶点的编号:" << endl;

	// 依次输入每一条边----无向图---对称,有向图--可能不对称
	for (k = 0; k < edgeNum; k++) {
		cin >> i >> j;			//输入边依附的两个顶点的编号
		//无向图-- - 对称---有i j必有j i
		edge[i][j] = 1; edge[j][i] = 1;		//置有边标志为1,没有默认为0
	}
}

//图的析构——图的邻接矩阵存储为静态存储分配,
//在图变量退出作用域时自动释放所占内存单元,因此,
//图的邻接矩阵存储无须销毁,析构函数为空
MyGraph::~MyGraph(){}

//深度优先遍历
void MyGraph::DFSearch(int v) {
	cout << vertex[v]<<" ";
	visited[v] = 1;
	for (int i = 0; i < vertexNum; i++) {
		if (edge[v][i] == 1 && visited[i] == 0) {
			DFSearch(i);
		}
	}
}

//广度优先遍历
void MyGraph::BFSearch(int v){
	int w, j;
	int Q[MaxSize];			//采用顺序队列
	int front=-1, rear=-1;	//初始化队列
	cout << vertex[v] << " ";
	visited[v] = 1;

	Q[++rear] = v;		//被访问的顶点入队
	while (front != rear) {
		w = Q[++front];//将对头元素出队并送到v中
		for (j = 0; j < vertexNum; j++) {
			if (edge[w][j] == 1 && visited[j] == 0) {
				cout << vertex[j] << " ";
				visited[j] = 1;
				Q[++rear] = j;
			}
		}
	}
}
 
int main() {
	int i;
	char array[] = { 'A','B','C','D','E' };
	MyGraph mygraph{ array,5,6 };//建立5个顶点,6条边的无向图
	//深度优先遍历
	for (i = 0; i < MaxSize; i++) {
		visited[i] = 0;
	}
	cout << "深度优先遍历序列为:";
	mygraph.DFSearch(0);		//从顶点0出发进行深度优先遍历
	cout << endl;

	//广度优先遍历
	for (i = 0; i < MaxSize;i++) {
		visited[i] = 0;
	}
	cout << "广度优先遍历序列为:";
	mygraph.BFSearch(0);		//从顶点0出发进行广度优先遍历

	return 0;
}

建立如下的无向图:

 

运行结果: 

 图的邻接表存储来创建图

/*
* 图的邻接表存储----
*					图的建立与遍历:
*								   广度优先遍历---深度优先遍历
*/
#include<iostream>
using namespace std;

const int MaxSize = 10;

int visited[MaxSize] = { 0 };//全局变量visited初始化——遍历的标志

//定义边表结点
struct EdgeNode
{
	int adjvex;  //邻接点数据域
	EdgeNode* next;//邻接点指针域
};

//定义顶点表结点
struct VertexNode
{
	char vertex;
	EdgeNode* firstEdge;
};

class ALGraph
{
private:
	VertexNode adjlist[MaxSize]; //存放顶点表的数组
	int vertexNum;				//图的顶点数
	int edgeNum;			   //图的边数
public:
	ALGraph(char a[], int n, int e);
	~ALGraph();
	void DFSearch(int v);//深度优先遍历
	void BFSearch(int v);//广度优先遍历
};

//有向图邻接表存储的构造函数
ALGraph::ALGraph(char a[], int n, int e){
	int i, j, k;
	EdgeNode* s = nullptr;
	this->vertexNum = n;
	this->edgeNum = e;

	//输入顶点信息,初始化顶点表
	for (i = 0; i < vertexNum; i++) {
		adjlist[i].vertex = a[i];
		adjlist[i].firstEdge = nullptr;
	}

	cout << "请输入边依附的两个顶点的编号:"<<endl;
	//依次输入每条边
	for (k = 0; k < edgeNum; k++) {
		cin >> i >> j;				//输入边依附的两个顶点的编号
		s = new EdgeNode;//生成一个边表结点s
		s->adjvex = j;
		s->next = adjlist[i].firstEdge;//将结点s插入表头
		adjlist[i].firstEdge = s;
	}
}

//图的销毁
ALGraph::~ALGraph(){
	EdgeNode* p = nullptr, * q = nullptr;
	for (int i = 0; i < vertexNum; i++) {
		p = q = adjlist[i].firstEdge;
		while (p != nullptr) {
			p = q->next;
			delete q;
			q = p;
		}
	}
}

//深度优先遍历
void ALGraph::DFSearch(int v) {
	int j;
	EdgeNode* p = nullptr;
	cout << adjlist[v].vertex; visited[v] = 1;
	p = adjlist[v].firstEdge;//工作指针p指向顶点v的边表

	while (p != nullptr) {
		j=p->adjvex;
		if (visited[j] == 0) {
			DFSearch(j);
		}
		p = p->next;
	}
}


//广度优先遍历
void ALGraph::BFSearch(int v) {
	int w, j;
	int Q[MaxSize];			//采用顺序队列
	int front = -1, rear = -1;	//初始化队列
	EdgeNode* p = nullptr;
	cout << adjlist[v].vertex<<" ";
	visited[v] = 1;
	Q[++rear] = v;				 //被访问的顶点入队

	while (front != rear) {		//当队非空时
		w = Q[++front];
		p = adjlist[w].firstEdge;//工作指针p指向顶点v的边表
		while (p!=nullptr){
			j = p->adjvex;
			if (visited[j] == 0) {
				cout << adjlist[j].vertex << " ";
				visited[j] = 1;
				Q[++rear] = j;
			}
			p = p->next;
		}
	}
}

int main() {
	char array[] = { 'A','B','C','D','E' };;
	int i;
	ALGraph algraph{ array,5,6 };//建立5个顶点,6条边的无向图

	//深度优先遍历
	for (i = 0; i < MaxSize; i++) {
		visited[i] = 0;
	}
	cout << "深度优先遍历序列为:";
	algraph.DFSearch(0);		//从顶点0出发进行深度优先遍历
	cout << endl;

	//广度优先遍历
	for (i = 0; i < MaxSize; i++) {
		visited[i] = 0;
	}
	cout << "广度优先遍历序列为:";
	algraph.BFSearch(0);		//从顶点0出发进行广度优先遍历

	return 0;
}

如下图:

运行结果:

 

 

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式