算法设计_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" };//边情况[ AB\AD\BC\BD]
	 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;
}

本文地址：https://blog.csdn.net/zu_zhu_xia/article/details/107338454