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

清疚 2024-04-01 16:37 83阅读 0赞

**目录**

图的表示方式

邻接矩阵

邻接表

图的遍历

深度优先遍历

深度优先遍历算法步骤：

图的广度优先遍历

广度优先遍历算法步骤:

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

代码

运行结果：

图的邻接表存储来创建图

如下图：

运行结果：

--------------------

> ## **图的表示方式** ##

*  图的表示方式有两种：
 *  [二维数组][Link 1]表示（邻接矩阵）；链表表示（邻接表）

> ### **邻接矩阵** ###

[邻接矩阵][Link 2] **邻接矩阵:**[邻接矩阵][Link 2] 是表示图形中顶点之间相邻关系的矩阵

> ### **邻接表** ###

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

> 建立如下的无向图：

![511a36e1992941d08575f8695c240355.png][]

> #### 运行结果： ####

![014f5af24989497ead61e35d65f6952f.png][]

> ### 图的邻接表存储来创建图 ###

/*
    * 图的邻接表存储----
    *					图的建立与遍历：
    *								   广度优先遍历---深度优先遍历
    */
    #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;
    }

> #### 如下图： ####

![660467d315f84d17aa5a6095d45b565b.png][]

> #### 运行结果： ####

![796a2517ac5044b29c7d18d21c731aa5.png][]

[Link 1]: https://so.csdn.net/so/search?q=%E4%BA%8C%E7%BB%B4%E6%95%B0%E7%BB%84&spm=1001.2101.3001.7020
[Link 2]: https://so.csdn.net/so/search?q=%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5&spm=1001.2101.3001.7020
[511a36e1992941d08575f8695c240355.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/0c6b4a0b3cb841ff99432f7f731bdb04.png
[014f5af24989497ead61e35d65f6952f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/bfd522fc87be446198e2345c00ea078d.png
[660467d315f84d17aa5a6095d45b565b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/bc6ea6d399264359adb231ffb2ae0883.png
[796a2517ac5044b29c7d18d21c731aa5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/bd574f8043e7493cb03a4657287c21d9.png