邻接矩阵实现无向图有向图基本操作

邻接矩阵实现无向图有向图基本操作 /*/ /*以无向图为基类，有向图为派生类，以邻接矩阵为存储方式，实现无向 图，有向 图的建立，插入，删除等操作*/ /*/ #include iostream #include string using namespace std; struct _ArcInfo//边信息 { char*v1; char*v2; }; struct _VexInfo { int adj;//顶点类型,是否相邻接 }; class UnDirectGraph { public: int ArcNum;//边数 _ArcInfo ArcInfo; //邻接矩阵 _VexInfo AdjMax[20][20]; int VexNum;//顶点数 char*Vexs[20];//存放顶点 public: UnDirectGraph(); ~UnDirectGraph(); int LocateVex(char*Vex);//获得节点在图中序号，在邻接矩阵中使用 virtual void CreateGraph();//构造无向图 void ShowGraph();//输出邻接矩阵 void InsertVex(char*&newVex);//向无向图中插入一个新节点 virtual void InsertArc(char*&v1,char*&v2);//向无向图中插入一条边 virtual void DeleteVex(char*oldVex);//删除一个节点 virtual void DeleteArc(char*&v1,char*&v2);//删除一条边 }; class DirectGraph:public UnDirectGraph//有向图继承无向图 { public: DirectGraph(); ~DirectGraph(); 重写基类的四个 函 关于工期滞后的函关于工程严重滞后的函关于工程进度滞后的回复函关于征求同志党风廉政意见的函关于征求廉洁自律情况的复函 数，基类中相应函数设为虚函数 // void CreateGraph();//构造有向图 void InsertArc(char*&v1,char*&v2);//向有向图中插入一条弧 void DeleteArc(char*&v1,char*&v2);//删除有向图中一条弧 void DeleteVex(char*oldVex);//删除有向图中的一个顶点 }; UnDirectGraph:UnDirectGraph() { VexNum=0; ArcNum=0; int i; for(i=0;i 20;i++) Vexs[i]=new char; ArcInfo.v1=new char; ArcInfo.v2=new char; } UnDirectGraph:~UnDirectGraph() { } int UnDirectGraph:LocateVex(char*Vex)//获取节点vex在图中的位置 { int i; for(i=0;i VexNum;i++) { if(strcmp(Vex,Vexs[i])==0) return i; } return 0; } void UnDirectGraph:CreateGraph()//创建无向图 { cout"输入顶点数和边数:"; cin VexNum ArcNum; int i,j,k; cout"输入各个顶点:"endl; for(i=0;i VexNum;i++)//输入顶点 cin Vexs[i]; for(i=0;i VexNum;i++) { for(j=0;j VexNum;j++) AdjMax[i][j].adj=0;//邻接矩阵初始化各点不相邻 } for(k=0;k ArcNum;k++) { cout"输入边的信息:"; cin ArcInfo.v1 ArcInfo.v2; i=LocateVex(ArcInfo.v1); j=LocateVex(ArcInfo.v2); AdjMax[j][i].adj=AdjMax[i][j].adj=1;//无向图中两个顶点相邻 } } void UnDirectGraph:ShowGraph()//输出邻接矩阵 { int i,j; for(i=0;i VexNum;i++) { for(j=0;j VexNum;j++) cout""AdjMax[i][j].adj; cout endl; } } void UnDirectGraph:InsertVex(char*&newVex)//向图中插入一个节点 { Vexs[VexNum]=newVex; VexNum++; for(int i=0;i VexNum;i++) { AdjMax[i][VexNum-1].adj=AdjMax[VexNum-1][i].adj=0;//插入一个孤立 节点 } } void UnDirectGraph:InsertArc(char*&v1,char*&v2)//在图中增加一条 边 { int i,j; i=LocateVex(v1); j=LocateVex(v2); if(i 0||j 0) return; ArcNum++; AdjMax[i][j].adj=AdjMax[j][i].adj=1; } void UnDirectGraph:DeleteArc(char*&v1,char*&v2)//删除两个节点之 间的边 { int i,j; i=LocateVex(v1); j=LocateVex(v2); ArcNum--; AdjMax[i][j].adj=AdjMax[j][i].adj=0; } void UnDirectGraph:DeleteVex(char*oldVex) { int k; int k1,k2; k=LocateVex(oldVex);//待删除节点的序号 for(int i=0;i VexNum;i++) { k1=LocateVex(Vexs[i]); if(AdjMax[k][k1].adj==1)//两节点之间有边 DeleteArc(oldVex,Vexs[i]);//删除该节点与其他结点之间的边 } for(int j=k+1;j VexNum;j++) Vexs[j-1]=Vexs[j];//该节点之后的元素向前移 VexNum--; cout"删除后顶点数:"VexNum endl; cout"删除后边数:"ArcNum endl; } DirectGraph:DirectGraph()//派生类的构造函数，首先要实现基类的构 造函数 { VexNum=0; ArcNum=0; int i; for(i=0;i 20;i++) Vexs[i]=new char; ArcInfo.v1=new char; ArcInfo.v2=new char; } DirectGraph:~DirectGraph() { } void DirectGraph:CreateGraph()//创建有向图 { cout"输入有向图顶点数和弧数:"; cin VexNum ArcNum; int i,j,k; cout"输入有向图的各个顶点:"endl; for(i=0;i VexNum;i++) cin Vexs[i]; for(i=0;i VexNum;i++) { for(j=0;j VexNum;j++) AdjMax[i][j].adj=0; } for(k=0;k ArcNum;k++) { cout"输入有向图1条弧的弧头和弧尾:"endl; cin ArcInfo.v1 ArcInfo.v2; i=LocateVex(ArcInfo.v1); j=LocateVex(ArcInfo.v2); AdjMax[i][j].adj=1; } } void DirectGraph:InsertArc(char*&v1,char*&v2)//向有向图中插入一 条弧 { int i,j; i=LocateVex(v1); j=LocateVex(v2); if(i 0||j 0) return; ArcNum++; AdjMax[i][j].adj=1; } void DirectGraph:DeleteArc(char*&v1,char*&v2)//删除有向图中的一 条弧 { int i,j; i=LocateVex(v1); j=LocateVex(v2); ArcNum--; AdjMax[i][j].adj=0; } void DirectGraph:DeleteVex(char*oldVex)//删除有向图中的一个顶点 { int k,k1; k=LocateVex(oldVex); for(int i=0;i VexNum;i++) { k1=LocateVex(Vexs[i]);// if(AdjMax[k][k1].adj==1)//要删除结点为弧头的弧 DeleteArc(oldVex,Vexs[i]); if(AdjMax[k1][k].adj==1)//要删除结点为弧尾的弧 DeleteArc(Vexs[i],oldVex); } j VexNum;j++) for(int j=k+1; Vexs[j-1]=Vexs[j]; VexNum--; cout"删除后结点数:"VexNum endl; cout"删除后弧数:"ArcNum endl; } int main() { cout"无向图操作"endl; UnDirectGraph UDG=UnDirectGraph(); UDG.CreateGraph(); cout"图的邻接矩阵:"endl; UDG.ShowGraph(); char*newVex=new char; cout"插入一个新节点:"endl; cin newVex; UDG.InsertVex(newVex); cout"插入新增加的边:"endl; for(int i=0;i UDG.VexNum-1;i++) UDG.InsertArc(newVex,UDG.Vexs[i]);cout"新图的邻接矩阵:"endl; UDG.ShowGraph(); cout"删除一个节点"endl; UDG.DeleteVex(UDG.Vexs[3]); UDG.ShowGraph(); cout"有向图操作"endl; DirectGraph DG=DirectGraph(); DG.CreateGraph(); cout"有向图的邻接矩阵:"endl; DG.ShowGraph(); cout"向有向图中插入一个节点:"endl; char*newVex1=new char; cin newVex1; DG.InsertVex(newVex1); DG.InsertArc(newVex1,DG.Vexs[0]);//向有向图中插入几条弧 DG.InsertArc(DG.Vexs[2],newVex1); DG.InsertArc(DG.Vexs[1],newVex1); DG.ShowGraph(); 删除有向图中的一个节点"endl; cout" DG.DeleteVex(DG.Vexs[3]); DG.ShowGraph(); return 0; }