代码语言
.
CSharp
.
JS
Java
Asp.Net
C
MSSQL
PHP
Css
PLSQL
Python
Shell
EBS
ASP
Perl
ObjC
VB.Net
VBS
MYSQL
GO
Delphi
AS
DB2
Domino
Rails
ActionScript
Scala
代码分类
文件
系统
字符串
数据库
网络相关
图形/GUI
多媒体
算法
游戏
Jquery
Extjs
Android
HTML5
菜单
网页交互
WinForm
控件
企业应用
安全与加密
脚本/批处理
开放平台
其它
【
C
】
邻接表和邻接矩阵的互相转换
作者:
ZhaoMatlab
/ 发布于
2013/6/4
/
721
/* 邻接表和邻接矩阵的互相转换 */ #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(){ }
试试其它关键字
转换
同语言下
.
获取手机通讯录 iOS去除数字以外的所有字符
.
异步加载音乐等资源
.
交通罚单管理系统
.
freemark实现,简单的替换
.
计算斐波那契数列
.
base64解码 包括解码长度
.
图像显示
.
冒泡排序
.
输入十进制数,输出指定进制
.
链式栈
可能有用的
.
C#实现的html内容截取
.
List 切割成几份 工具类
.
SQL查询 多列合并成一行用逗号隔开
.
一行一行读取txt的内容
.
C#动态修改文件夹名称(FSO实现,不移动文件)
.
c# 移动文件或文件夹
.
c#图片添加水印
.
Java PDF转换成图片并输出给前台展示
.
网站后台修改图片尺寸代码
.
处理大图片在缩略图时的展示
ZhaoMatlab
贡献的其它代码
(
2
)
.
比较任意类型大小
.
邻接表和邻接矩阵的互相转换
Copyright © 2004 - 2024 dezai.cn. All Rights Reserved
站长博客
粤ICP备13059550号-3