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

邻接矩阵实现无向图有向图基本操作/*/*以无向图为基类，有向图为派生类，以邻接矩阵为存储方式，实现无向图，有向图的建立，插入，删除等操作*/*/#include iostream#include string using namespace std；struct _ArcInfo/边信息char*v1；char*v2；struct _VexInfoint adj；/顶点类型,是否相邻接；class UnDirectGraphpublic：int ArcNum；/边数_ArcInfo ArcInfo；_VexInfo AdjMax2020；/邻接矩阵int VexNum；/顶点数char*Vexs20；/存放顶点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+)Vexsi=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,Vexsi)=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 Vexsi；for(i=0；i VexNum；i+)for(j=0；j VexNum；j+)AdjMaxij.adj=0；/邻接矩阵初始化各点不相邻for(k=0；k ArcNum；k+)cout输入边的信息：；cin ArcInfo.v1 ArcInfo.v2；i=LocateVex(ArcInfo.v1)；j=LocateVex(ArcInfo.v2)；AdjMaxji.adj=AdjMaxij.adj=1；/无向图中两个顶点相邻void UnDirectGraph：ShowGraph()/输出邻接矩阵int i,j；for(i=0；i VexNum；i+)for(j=0；j VexNum；j+)coutAdjMaxij.adj；cout endl；void UnDirectGraph：InsertVex(char*&newVex)/向图中插入一个节点VexsVexNum=newVex；VexNum+；for(int i=0；i VexNum；i+)AdjMaxiVexNum-1.adj=AdjMaxVexNum-1i.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+；AdjMaxij.adj=AdjMaxji.adj=1；void UnDirectGraph：DeleteArc(char*&v1,char*&v2)/删除两个节点之间的边int i,j；i=LocateVex(v1)；j=LocateVex(v2)；ArcNum-；AdjMaxij.adj=AdjMaxji.adj=0；void UnDirectGraph：DeleteVex(char*oldVex)int k；int k1,k2；k=LocateVex(oldVex)；/待删除节点的序号for(int i=0；i VexNum；i+)k1=LocateVex(Vexsi)；if(AdjMaxkk1.adj=1)/两节点之间有边DeleteArc(oldVex,Vexsi)；/删除该节点与其他结点之间的边for(int j=k+1；j VexNum；j+)Vexsj-1=Vexsj；/该节点之后的元素向前移VexNum-；cout删除后顶点数：VexNum endl；cout删除后边数：ArcNum endl；DirectGraph：DirectGraph()/派生类的构造函数，首先要实现基类的构造函数VexNum=0；ArcNum=0；int i；for(i=0；i 20；i+)Vexsi=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 Vexsi；for(i=0；i VexNum；i+)for(j=0；j VexNum；j+)AdjMaxij.adj=0；for(k=0；k ArcNum；k+)cout输入有向图1条弧的弧头和弧尾：endl；cin ArcInfo.v1 ArcInfo.v2；i=LocateVex(ArcInfo.v1)；j=LocateVex(ArcInfo.v2)；AdjMaxij.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+；AdjMaxij.adj=1；void DirectGraph：DeleteArc(char*&v1,char*&v2)/删除有向图中的一条弧int i,j；i=LocateVex(v1)；j=LocateVex(v2)；ArcNum-；AdjMaxij.adj=0；void DirectGraph：DeleteVex(char*oldVex)/删除有向图中的一个顶点int k,k1；k=LocateVex(oldVex)；for(int i=0；i VexNum；i+)k1=LocateVex(Vexsi)；/if(AdjMaxkk1.adj=1)/要删除结点为弧头的弧DeleteArc(oldVex,Vexsi)；if(AdjMaxk1k.adj=1)/要删除结点为弧尾的弧DeleteArc(Vexsi,oldVex)；for(int j=k+1；j VexNum；j+)Vexsj-1=Vexsj；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.Vexsi)；cout新图的邻接矩阵：endl；UDG.ShowGraph()；cout删除一个节点endl；UDG.DeleteVex(UDG.Vexs3)；UDG.ShowGraph()；cout有向图操作endl；DirectGraph DG=DirectGraph()；DG.CreateGraph()；cout有向图的邻接矩阵：endl；DG.ShowGraph()；cout向有向图中插入一个节点：endl；char*newVex1=new char；cin newVex1；DG