c/c++语言开发共享算法设计_63

题目

设计算法，将一个无向图的邻接矩阵转换为邻接表。
tip:初始化一个无向图的邻接矩阵——初始化一个邻接表——转换
PS:作业记录

#include<iostream> using namespace std; const int MAX_SIZE = 10; int M_visited[MAX_SIZE] = { 0 }; int A_visited[MAX_SIZE] = { 0 }; //邻接矩阵 template<typename DataType> class MGraph{ public: 	 //邻接矩阵初始化  	MGraph(DataType a[], int n, int e) 	 {  	 	int i, j, k;  	 	M_vertexNum = n; M_edgeNum = e;   		for (i = 0; i < M_vertexNum; i++)   //存储顶点   			 vertex[i] = a[i];   		for (i = 0; i < M_vertexNum; i++)   //初始化邻接矩阵    		for (j = 0; j < M_vertexNum; j++)       			edge[i][j] = 0;   		for (k = 0; k < M_edgeNum; k++)    //输入边   		{    			cout << "请输入边的邻接点（i,j)：";    			cin >> i >> j;    			edge[i][j] = 1;    			edge[j][i] = 1;   		} 	 }   	//用于测试的深度遍历  	void DFTraverse(int v)      //邻接矩阵的深度遍历  	{   		cout << vertex[v] << "——";   		M_visited[v] = 1;   		for (int j = 0; j < M_vertexNum; j++)   			 if (edge[v][j] == 1 && M_visited[j] == 0)    				 DFTraverse(j); 	 }  	DataType vertex[MAX_SIZE];   //存放顶点  	int edge[MAX_SIZE][MAX_SIZE];  //存放边  	int M_vertexNum, M_edgeNum;   //图的顶点数和边数 };  //关于邻接表的转换 struct EdgeNode  	 //定义边表结点 {  	int adjvex; 	 EdgeNode* next; }; template<typename DataType> struct VertexNode  //定义顶点结点 {  DataType vertex;  EdgeNode* firstEdge; }; template<typename DataType> class ALGraph {  		//定义邻接表 public : 	 //邻接表的深度遍历  	void DFTraverse(int  v)    	{   		int j;   		EdgeNode* p = nullptr;   		cout << adjList[v].vertex << "——";   		A_visited[v] = 1;   		p = adjList[v].firstEdge;   		while (p != nullptr)   		{    			j = p->adjvex;    			if (A_visited[j] == 0)     			DFTraverse(j);    			p = p->next;   		}  	}  	VertexNode<DataType> adjList[MAX_SIZE];  //存放顶点表  	int A_vertexNum, A_edgeNum;     //存放顶点数和边数 }; //转换核心代码 template<typename DataType> void Change_(MGraph<DataType>& MG, ALGraph<DataType>& AL) {  	int i, j, k;  	EdgeNode* s = nullptr;  	AL.A_vertexNum = MG.M_vertexNum;  	AL.A_edgeNum = MG.M_edgeNum;  	for (i = 0; i < MG.M_vertexNum; i++)//初始化顶点表结点  	{   		AL.adjList[i].vertex = MG.vertex[i];  		 AL.adjList[i].firstEdge = nullptr;  	}  	for (i = 0; i < MG.M_vertexNum; i++)//初始化边表结点  	{   		for (j = 0; j < MG.M_vertexNum; j++)   		{    			if (MG.edge[i][j] == 1)//如果i到j有边    			{     				s = new EdgeNode;     				s->adjvex = j;     				s->next = AL.adjList[i].firstEdge;     				AL.adjList[i].firstEdge = s;   		 	}   		}  	} } //测试 int main() {  	string ch[] = { "A","B","C","D" };//边情况[ ABADBCBD] 	 MGraph<string> MG(ch,4,4);  	ALGraph<string> AL;  	cout << "邻接矩阵的深度遍历：";  	MG.DFTraverse(0);  	cout << "n执行转换操作！" << endl;  	Change_(MG, AL);  	cout << "邻接表的深度遍历：";  	AL.DFTraverse(0);  	return 0; }

c/c++开发分享算法设计_63地址：https://blog.csdn.net/zu_zhu_xia/article/details/107338454