邻接表和邻接矩阵的互相转换代码,C代码库,德仔网

代码语言
代码分类
【C】邻接表和邻接矩阵的互相转换
作者:ZhaoMatlab / 发布于2013/6/4/ 728

	/*
	邻接表和邻接矩阵的互相转换
	*/

	#include <iostream.h>

	const int MaxSize=10; //顶点的最大个数为10

	//下面定义一个循环顺序队列
	class Queue{
	private:
	 int front,rear;
	 int queueDate[MaxSize];
	public:
	 Queue(){rear=front=MaxSize;}
	 void enqueue(int x);
	 int dequeue();
	 int empty();
	};

	void Queue::enqueue (int x){
	if((rear+1)%MaxSize==front)
	 cout<<"队满";
	else{
	 rear=(rear+1)%MaxSize;
	 queueDate[rear]=x;
	}
	}

	int Queue::dequeue (){
	int tmp;
	if(rear==front)
	 cout<<"队空";
	else{
	 front=(front+1)%MaxSize;
	 tmp=queueDate[front];
	 return tmp;
	}
	}

	int Queue::empty (){
	if(front==rear)
	 return 1;
	else
	 return 0;
	}

	//邻接表的边表结点
	struct ArcNode{
	int arc_node; //边表的数据域
	ArcNode * next; //边表的指针域
	};

	//邻接表的顶点表结点
	struct VertexNode{
	int vertex_node; //顶点表的数据
	ArcNode * first_edge; //顶点表的指针域
	};

	//邻接表图的结构
	class TableGraph{
	private:
	 VertexNode table_vertex[MaxSize]; //邻接表_顶点表数组
	 int table_arc_num,table_vertex_num; //邻接表_边的数目和顶点数目
	
	 int table_visited[MaxSize]; //邻接表_标记是否已访问
	public:
	 void table_DFST(int v); //邻接表_深度优先搜索遍历
	 void table_BFST(int v); //邻接表_广度优先搜索遍历

	 init_table_visited(); //邻接表_初始化标记数组
	 void friend convert(MatrixGraph & mg,TableGraph & tg);
	};

	//邻接矩阵图的结构
	class MatrixGraph{
	private:
	 int matrix_vertex[MaxSize]; //邻接矩阵_存放顶点的数组
	 int matrix_arc[MaxSize][MaxSize]; //邻接矩阵_存放边的数组
	 int matrix_vertex_num,matrix_arc_num; //令接矩阵_顶点的数目和边的数目

	 int matrix_visited[MaxSize]; //邻接矩阵_标记是否已访问
	public:
	 void friend convert(MatrixGraph &mg,TableGraph & tg);
	 MatrixGraph(int a[],int n,int e); //邻接矩阵_构造函数
	 void matrix_DFST(int v); //邻接矩阵_深度优先搜索遍历
	 void matrix_BFST(int v); //邻接矩阵_广度优先搜索遍历

	 void init_matrix_visited(); //邻接矩阵_初始化标记数组
	};

	//邻接表的函数定义
	void TableGraph::table_DFST(int v){
	int j;
	ArcNode * p;
	cout<<table_vertex[v].vertex_node <<" "; //访问传过来的第几个结点
	table_visited[v]=1; //设置已访问
	p=table_vertex[v].first_edge ; //p指向边表中的第一个结点
	while(p!=NULL){
	 j=p->arc_node ; //用j保存与p所指结点相邻接的结点在顶点表的下标
	 if(table_visited[j]==0) //如果j没有被访问则深度优先搜索遍历j
	 table_DFST(j);
	 p=p->next; //看下一个结点
	}
	}

	void TableGraph::table_BFST(int v){
	int j;
	Queue table_q;
	ArcNode * p;
	cout<<table_vertex[v].vertex_node <<" "; //访问传过来的第几个结点
	table_visited[v]=1; //设置已访问
	table_q.enqueue (v);
	while(!table_q.empty()){
	 v=table_q.dequeue ();
	 p=table_vertex[v].first_edge ; //p指向顶点表中V的边表
	 while(p!=NULL){
	 j=p->arc_node ; //用j保存与p所指结点相邻接的结点在顶点表的下标
	 if(table_visited[j]==0){ //如棵j没有被访问则输出j的数据并设置已访问并入队列
	 cout<<table_vertex[j].vertex_node<<" " ;
	 table_visited[j]=1;
	 table_q.enqueue (j);
	 }
	 p=p->next ;
	 }
	}
	}

	TableGraph::init_table_visited (){
	for(int i=0;i<table_arc_num;i++){
	 table_visited[i]=0;
	}
	}

	//邻接矩阵中的函数定义
	MatrixGraph::MatrixGraph(int a[],int n,int e){
	int i,j,k;
	matrix_vertex_num=n; //邻接矩阵_顶点的个数
	matrix_arc_num=e; //邻接矩阵_边的个数
	int matrix_count=1;
	char s;

	for(k=0;k<matrix_vertex_num;k++){ //邻接矩阵_给顶点赋值
	 matrix_vertex[k]=a[k];
	}

	for(i=0;i<matrix_vertex_num;i++){ //邻接矩阵_边数组的初始化
	 for(j=0;j<matrix_vertex_num;j++){
	 matrix_arc[i][j]=0;
	 }
	}

	cout<<"下面用邻接矩阵来建立图,请输入边所依附的两个结点用逗号隔开"<<endl;
	for(k=0;k<matrix_arc_num;k++){ //依次把边输入
	 cout<<"请输入第 "<<matrix_count<<" 边所依附的两个结点: ";
	 cin>>i>>s>>j;
	 matrix_count++;
	 matrix_arc[i][j]=1;matrix_arc[j][i]=1;
	}
	}

	void MatrixGraph::matrix_DFST(int v){
	cout<<matrix_vertex[v]<<" "; //访问传过来的第几个结点
	matrix_visited[v]=1; //设置已经访问
	for(int i=0;i<matrix_vertex_num;i++)
	 if(matrix_arc[v][i]==1 && matrix_visited[i]==0)//如果i与v邻接并且i未被访问
	 matrix_DFST(i); //那么就去深度优先搜索遍历i
	}

	void MatrixGraph::matrix_BFST (int v){
	Queue matrix_q;
	cout<<matrix_vertex[v]<<" "; //访问传过来的第几个结点
	matrix_visited[v]=1; //设置已经访问
	matrix_q.enqueue (v); //将访问过的结点入队列
	while(!matrix_q.empty()){
	 v=matrix_q.dequeue (); //将队头元素出队列并送到V中
	 for(int i=0;i<matrix_vertex_num;i++){
	 if(matrix_arc[v][i]==1 && matrix_visited[i]==0){//如果i与V邻接并且未被访问过，那就输出第i个结点的数据并设置已访问，并且将其入队列
	 cout<<matrix_vertex[i]<<" ";
	 matrix_visited[i]=1;
	 matrix_q.enqueue (i);
	 }
	 }
	}
	}

	void MatrixGraph::init_matrix_visited(){
	for(int i=0;i<matrix_vertex_num;i++){
	 matrix_visited[i]=0;
	}
	}

	void convert(MatrixGraph & mg,TableGraph & tg){
	int i,j;
	ArcNode * s, *l;
	tg.table_arc_num = mg.matrix_arc_num ;
	tg.table_vertex_num = mg.matrix_vertex_num ;
	for(i=0;i<mg.matrix_vertex_num ;i++){
	 tg.table_vertex[i].vertex_node = mg.matrix_vertex [i];
	 tg.table_vertex [i].first_edge = NULL;
	}
	
	for(i=0;i<mg.matrix_vertex_num ;i++){
	 for(j=0;j<mg.matrix_vertex_num ;j++){
	 if(mg.matrix_arc[i][j]!=0){
	 s=new ArcNode; s->arc_node =j;
	 s->next = tg.table_vertex [i].first_edge ;
	 tg.table_vertex [i].first_edge =s;

	 l= new ArcNode; l->arc_node =i;
	 l->next =tg.table_vertex [j].first_edge ;
	 tg.table_vertex [j].first_edge =l;
	 }
	 }
	}

	}

	//主函数
	void main(){

	}
试试其它关键字
　转换　
同语言下
可能有用的
ZhaoMatlab贡献的其它代码(2)