• 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
       
    • 核心代码： 
    1.  
    2. //深度优先遍历
    3. void MyGraph::DFSearch(int v) {
    4. 	cout << vertex[v]<<" ";
    5. 	visited[v] = 1;
    6. 	for (int i = 0; i < vertexNum; i++) {
    7. 		if (edge[v][i] == 1 && visited[i] == 0) {
    8. 			DFSearch(i);
    9. 		}
    10. 	}
    11. }

    图的广度优先遍历 

    • 图的广度优先遍历（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
    •  核心代码
    1.  
    2. //广度优先遍历
    3. void MyGraph::BFSearch(int v){
    4. 	int w, j;
    5. 	int Q[MaxSize];			//采用顺序队列
    6. 	int front=-1, rear=-1;	//初始化队列
    7. 	cout << vertex[v] << " ";
    8. 	visited[v] = 1;
    9.  
    10. 	Q[++rear] = v;		//被访问的顶点入队
    11. 	while (front != rear) {
    12. 		w = Q[++front];//将对头元素出队并送到v中
    13. 		for (j = 0; j < vertexNum; j++) {
    14. 			if (edge[w][j] == 1 && visited[j] == 0) {
    15. 				cout << vertex[j] << " ";
    16. 				visited[j] = 1;
    17. 				Q[++rear] = j;
    18. 			}
    19. 		}
    20. 	}
    21. }

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

    • 代码 

    1. /*
    2. * 图的邻接矩阵存储----
    3. *					图的建立与遍历：
    4. *								   广度优先遍历---深度优先遍历
    5. */
    6. #include
    7. using namespace std;
    8.  
    9. const int MaxSize = 10;
    10.  
    11. int visited[MaxSize] = { 0 };//全局变量visited初始化——遍历的标志
    12.  
    13. class MyGraph {
    14. private:
    15. 	char vertex[MaxSize];//存放顶点的数组
    16. 	char edge[MaxSize][MaxSize];//存放边的数组
    17. 	int vertexNum;//图的顶点数
    18. 	int edgeNum;//图的边数
    19. public:
    20. 	MyGraph(char a[], int n, int e);//传数组，顶点数，边数
    21. 	~MyGraph();
    22. 	void DFSearch(int v);//深度优先遍历
    23. 	void BFSearch(int v);//广度优先遍历
    24. };
    25.  
    26. //图的建立
    27. MyGraph::MyGraph(char a[], int n, int e){
    28. 	int i, j, k;
    29. 	this->vertexNum = n;	 //图的顶点数
    30. 	this->edgeNum = e;		//图的边数
    31.  
    32. 	//储存顶点
    33. 	for (i = 0; i < vertexNum; i++) {
    34. 		vertex[i] = a[i];
    35. 	}
    36.  
    37. 	//初始化邻接矩阵
    38. 	for (i = 0; i < vertexNum; i++) {
    39. 		for (j = 0; j < vertexNum; j++) {
    40. 			edge[i][j] = 0;
    41. 		}
    42. 	}
    43.  
    44. 	cout << "请输入边依附的两个顶点的编号：" << endl;
    45.  
    46. 	// 依次输入每一条边----无向图---对称，有向图--可能不对称
    47. 	for (k = 0; k < edgeNum; k++) {
    48. 		cin >> i >> j;			//输入边依附的两个顶点的编号
    49. 		//无向图-- - 对称---有i j必有j i
    50. 		edge[i][j] = 1; edge[j][i] = 1;		//置有边标志为1，没有默认为0
    51. 	}
    52. }
    53.  
    54. //图的析构——图的邻接矩阵存储为静态存储分配，
    55. //在图变量退出作用域时自动释放所占内存单元,因此，
    56. //图的邻接矩阵存储无须销毁，析构函数为空
    57. MyGraph::~MyGraph(){}
    58.  
    59. //深度优先遍历
    60. void MyGraph::DFSearch(int v) {
    61. 	cout << vertex[v]<<" ";
    62. 	visited[v] = 1;
    63. 	for (int i = 0; i < vertexNum; i++) {
    64. 		if (edge[v][i] == 1 && visited[i] == 0) {
    65. 			DFSearch(i);
    66. 		}
    67. 	}
    68. }
    69.  
    70. //广度优先遍历
    71. void MyGraph::BFSearch(int v){
    72. 	int w, j;
    73. 	int Q[MaxSize];			//采用顺序队列
    74. 	int front=-1, rear=-1;	//初始化队列
    75. 	cout << vertex[v] << " ";
    76. 	visited[v] = 1;
    77.  
    78. 	Q[++rear] = v;		//被访问的顶点入队
    79. 	while (front != rear) {
    80. 		w = Q[++front];//将对头元素出队并送到v中
    81. 		for (j = 0; j < vertexNum; j++) {
    82. 			if (edge[w][j] == 1 && visited[j] == 0) {
    83. 				cout << vertex[j] << " ";
    84. 				visited[j] = 1;
    85. 				Q[++rear] = j;
    86. 			}
    87. 		}
    88. 	}
    89. }
    90.  
    91. int main() {
    92. 	int i;
    93. 	char array[] = { 'A','B','C','D','E' };
    94. 	MyGraph mygraph{ array,5,6 };//建立5个顶点，6条边的无向图
    95. 	//深度优先遍历
    96. 	for (i = 0; i < MaxSize; i++) {
    97. 		visited[i] = 0;
    98. 	}
    99. 	cout << "深度优先遍历序列为：";
    100. 	mygraph.DFSearch(0);		//从顶点0出发进行深度优先遍历
    101. 	cout << endl;
    102.  
    103. 	//广度优先遍历
    104. 	for (i = 0; i < MaxSize;i++) {
    105. 		visited[i] = 0;
    106. 	}
    107. 	cout << "广度优先遍历序列为：";
    108. 	mygraph.BFSearch(0);		//从顶点0出发进行广度优先遍历
    109.  
    110. 	return 0;
    111. }

    建立如下的无向图：

     

    运行结果： 

     图的邻接表存储来创建图

    1. /*
    2. * 图的邻接表存储----
    3. *					图的建立与遍历：
    4. *								   广度优先遍历---深度优先遍历
    5. */
    6. #include
    7. using namespace std;
    8.  
    9. const int MaxSize = 10;
    10.  
    11. int visited[MaxSize] = { 0 };//全局变量visited初始化——遍历的标志
    12.  
    13. //定义边表结点
    14. struct EdgeNode
    15. {
    16. 	int adjvex;  //邻接点数据域
    17. 	EdgeNode* next;//邻接点指针域
    18. };
    19.  
    20. //定义顶点表结点
    21. struct VertexNode
    22. {
    23. 	char vertex;
    24. 	EdgeNode* firstEdge;
    25. };
    26.  
    27. class ALGraph
    28. {
    29. private:
    30. 	VertexNode adjlist[MaxSize]; //存放顶点表的数组
    31. 	int vertexNum;				//图的顶点数
    32. 	int edgeNum;			   //图的边数
    33. public:
    34. 	ALGraph(char a[], int n, int e);
    35. 	~ALGraph();
    36. 	void DFSearch(int v);//深度优先遍历
    37. 	void BFSearch(int v);//广度优先遍历
    38. };
    39.  
    40. //有向图邻接表存储的构造函数
    41. ALGraph::ALGraph(char a[], int n, int e){
    42. 	int i, j, k;
    43. 	EdgeNode* s = nullptr;
    44. 	this->vertexNum = n;
    45. 	this->edgeNum = e;
    46.  
    47. 	//输入顶点信息，初始化顶点表
    48. 	for (i = 0; i < vertexNum; i++) {
    49. 		adjlist[i].vertex = a[i];
    50. 		adjlist[i].firstEdge = nullptr;
    51. 	}
    52.  
    53. 	cout << "请输入边依附的两个顶点的编号："<
    54. 	//依次输入每条边
    55. 	for (k = 0; k < edgeNum; k++) {
    56. 		cin >> i >> j;				//输入边依附的两个顶点的编号
    57. 		s = new EdgeNode;//生成一个边表结点s
    58. 		s->adjvex = j;
    59. 		s->next = adjlist[i].firstEdge;//将结点s插入表头
    60. 		adjlist[i].firstEdge = s;
    61. 	}
    62. }
    63.  
    64. //图的销毁
    65. ALGraph::~ALGraph(){
    66. 	EdgeNode* p = nullptr, * q = nullptr;
    67. 	for (int i = 0; i < vertexNum; i++) {
    68. 		p = q = adjlist[i].firstEdge;
    69. 		while (p != nullptr) {
    70. 			p = q->next;
    71. 			delete q;
    72. 			q = p;
    73. 		}
    74. 	}
    75. }
    76.  
    77. //深度优先遍历
    78. void ALGraph::DFSearch(int v) {
    79. 	int j;
    80. 	EdgeNode* p = nullptr;
    81. 	cout << adjlist[v].vertex; visited[v] = 1;
    82. 	p = adjlist[v].firstEdge;//工作指针p指向顶点v的边表
    83.  
    84. 	while (p != nullptr) {
    85. 		j=p->adjvex;
    86. 		if (visited[j] == 0) {
    87. 			DFSearch(j);
    88. 		}
    89. 		p = p->next;
    90. 	}
    91. }
    92.  
    93.  
    94. //广度优先遍历
    95. void ALGraph::BFSearch(int v) {
    96. 	int w, j;
    97. 	int Q[MaxSize];			//采用顺序队列
    98. 	int front = -1, rear = -1;	//初始化队列
    99. 	EdgeNode* p = nullptr;
    100. 	cout << adjlist[v].vertex<<" ";
    101. 	visited[v] = 1;
    102. 	Q[++rear] = v;				 //被访问的顶点入队
    103.  
    104. 	while (front != rear) {		//当队非空时
    105. 		w = Q[++front];
    106. 		p = adjlist[w].firstEdge;//工作指针p指向顶点v的边表
    107. 		while (p!=nullptr){
    108. 			j = p->adjvex;
    109. 			if (visited[j] == 0) {
    110. 				cout << adjlist[j].vertex << " ";
    111. 				visited[j] = 1;
    112. 				Q[++rear] = j;
    113. 			}
    114. 			p = p->next;
    115. 		}
    116. 	}
    117. }
    118.  
    119. int main() {
    120. 	char array[] = { 'A','B','C','D','E' };;
    121. 	int i;
    122. 	ALGraph algraph{ array,5,6 };//建立5个顶点，6条边的无向图
    123.  
    124. 	//深度优先遍历
    125. 	for (i = 0; i < MaxSize; i++) {
    126. 		visited[i] = 0;
    127. 	}
    128. 	cout << "深度优先遍历序列为：";
    129. 	algraph.DFSearch(0);		//从顶点0出发进行深度优先遍历
    130. 	cout << endl;
    131.  
    132. 	//广度优先遍历
    133. 	for (i = 0; i < MaxSize; i++) {
    134. 		visited[i] = 0;
    135. 	}
    136. 	cout << "广度优先遍历序列为：";
    137. 	algraph.BFSearch(0);		//从顶点0出发进行广度优先遍历
    138.  
    139. 	return 0;
    140. }

    如下图：

    运行结果：

     

     

  • 相关阅读:
    14. Redisson 分布式锁
    vue-别名路径联想提示的配置
    Linux操作系统之线程
    Python——基础语法(模块、包、文件读写等操作)
    利用PerconaTookit工具在线修改表结构
    Spring boot多数据源实现动态切换
    9.2作业
    【SpringMVC】JSON注解&全局异常处理机制
    JVM基础08_强软弱虚引用
    GB/T 10707 橡胶燃烧性能
  • 原文地址：https://blog.csdn.net/m0_63064861/article/details/127767017