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

目录

图的表示方式

 邻接矩阵

邻接表

图的遍历

深度优先遍历

深度优先遍历算法步骤： 

图的广度优先遍历 

广度优先遍历算法步骤: 

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

代码 

运行结果： 

 图的邻接表存储来创建图

如下图：

运行结果：

---

图的表示方式

• 图的表示方式有两种：
• 二维数组表示（邻接矩阵）；链表表示（邻接表） 

 邻接矩阵

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

邻接表

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;
}

如下图：

运行结果：