定义邻接矩阵存储的图类。
[实验要求]
1. 创建一个邻接矩阵存储的图；
2. 返回图中指定边的权值；
3. 查找图中某顶点的第一个邻接顶点、某顶点关于另一个顶点的下一个邻接顶点序号；
4. 图的深度优先遍历；
[截图]
1. 实验例图
2.操作截图
[实现代码]
一共有三个文件Graph_Martix.h、Graph_Martix.cpp和main.cpp
- Graph_Martix.h
#ifndef _GRAPH_MARTIX_H
#define _GRAPH_MARTIX_H
#include <iostream>
using namespace std;
const int MaxGrzphSize=; //图的最大顶点个数
const int MaxWeight=; //图中允许的最大权值
class Graph_Martix
{
private:
int edge[][];
int graphsize;
public:
Graph_Martix();
int GetWeight(const int v1,const int v2);
int GetFirstNeighbor(const int v);
void GetAllNeighbor(const int v);
int GetNextNeighbor(const int v1,const int v2);
void DepthFirstSearch(int v);
void RDFS(const int v,int *visited); };
#endif
- Graph_Martix.cpp
#include "Graph_Martix.h"
Graph_Martix::Graph_Martix() {
cout<<"请输入邻接矩阵节点个数"<<endl;
cin>>graphsize;
cout<<"请输入各个节点之间的权值:"<<endl;
for(int i=;i<graphsize;i++){
for(int j=;j<graphsize;j++){
cin>>edge[i][j];
}
}
}
int Graph_Martix::GetWeight(const int v1,const int v2){
if(v1==-||v2==-)
return -;
else
return edge[v1][v2];
}
int Graph_Martix::GetFirstNeighbor(const int v){
if (v==-) return -;
for(int i=;i<graphsize;i++){
if(edge[v][i]>&&edge[v][i]<MaxWeight)
return i;
}
return -;//若v没有邻接顶点，则返回-1.
}
void Graph_Martix::GetAllNeighbor(const int v) {
if(v==-) return;
for(int i=;i<graphsize;i++){
if(edge[v][i]>&&edge[v][i]<MaxWeight){
cout<<i;
}
}
}
int Graph_Martix::GetNextNeighbor(const int v1,const int v2) {
if(v1==-||v2==-) return -;
for(int i=v2+;i<graphsize;i++)
if(edge[v1][i]>&&edge[v1][i]<MaxWeight)
return i;
return -; //若在v2之后没有与v1邻接的顶点，则返回-1.
}
void Graph_Martix::RDFS(const int v,int *visited)
{
cout<<v<<" "; //输出v的序号
visited[v]=; //说明v已被访问过
int w=GetFirstNeighbor(v); //取得v的第一个邻接顶点的序号
while(w!=-) //若存在顶点w
{
if(!visited[w]) //若w未被访问过，从w递归访问
RDFS(w,visited);
w=GetNextNeighbor(v,w); //w为v关于w的下一个邻接顶点
}
}
void Graph_Martix::DepthFirstSearch(int v)
{
int *visited=new int[graphsize]; //为辅助数组申请空间
for(int k=;k<graphsize;k++)
visited[k]=;
RDFS(v,visited); //从序号为0的节点出发，深度优先遍历
delete[]visited; //释放辅助数组空间
}
- main.cpp
#include <iostream>
#include "Graph_Martix.h"
#include "Graph_Martix.cpp"
using namespace std;
int main(){
Graph_Martix a;
int b,c,d,e,f,g;
while(){
cout<<"请输入要执行的操作"<<endl;
cout<<"0.退出"<<endl;
cout<<"1.获取指定权值"<<endl;
cout<<"2.获取该点全部邻接顶点"<<endl;
cout<<"3.深度遍历"<<endl;
cin>>c;
switch(c){
case :
exit();
break;
case :
cout<<"请输入该边的起点，终点"<<endl;
cin>>d>>e;
b=a.GetWeight(d,e);
if(b==-){
cout<<"边不存在"<<endl;
}
cout<<b<<endl;
break;
case :
cout<<"请输入顶点序号"<<endl;
cin>>f;
a.GetAllNeighbor(f);
break;
case :
cout<<"请输入选择哪个顶点开始深度遍历"<<endl;
cin>>g;
a.DepthFirstSearch(g);
cout<<endl;
break;}}
return ;
}