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

《邻接矩阵实现无向图有向图基本操作》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、邻接矩阵实现无向图有向图基本操作/*//*以无向图为基类，有向图为派生类，以邻接矩阵为存储方式，实现无向图，有向图的建立，插入，删除等操作*//*/#includeiostream#includestringusingnamespacestd；struct_ArcInfo//边信息{char*v1；char*v2；}；struct_VexInfo{intadj；//顶点类型,是否相邻接}；classUnDirectGraph{public：intArcNum；//边数_ArcInfoArcInfo；_Ve

2、xInfoAdjMax[20][20]；//邻接矩阵intVexNum；//顶点数char*Vexs[20]；//存放顶点public：UnDirectGraph()；~UnDirectGraph()；intLocateVex(char*Vex)；//获得节点在图中序号，在邻接矩阵中使用virtualvoidCreateGraph()；//构造无向图voidShowGraph()；//输出邻接矩阵voidInsertVex(char*&newVex)；//向无向图中插入一个新节点virtualvoidIn

3、sertArc(char*&v1,char*&v2)；//向无向图中插入一条边virtualvoidDeleteVex(char*oldVex)；//删除一个节点virtualvoidDeleteArc(char*&v1,char*&v2)；//删除一条边}；classDirectGraph：publicUnDirectGraph//有向图继承无向图{public：DirectGraph()；~DirectGraph()；//重写基类的四个函数，基类中相应函数设为虚函数voidCreateGraph()；

4、//构造有向图voidInsertArc(char*&v1,char*&v2)；//向有向图中插入一条弧voidDeleteArc(char*&v1,char*&v2)；//删除有向图中一条弧voidDeleteVex(char*oldVex)；//删除有向图中的一个顶点}；UnDirectGraph：UnDirectGraph(){VexNum=0；ArcNum=0；inti；for(i=0；i20；i++)Vexs[i]=newchar；ArcInfo.v1=newchar；ArcInfo.v2=ne

5、wchar；}UnDirectGraph：~UnDirectGraph(){}intUnDirectGraph：LocateVex(char*Vex)//获取节点vex在图中的位置{inti；for(i=0；iVexNum；i++){if(strcmp(Vex,Vexs[i])==0)returni；}return0；}voidUnDirectGraph：CreateGraph()//创建无向图{cout"输入顶点数和边数："；cinVexNumArcNum；inti,j,k；cout"输入各个顶点："e

6、ndl；for(i=0；iVexNum；i++)//输入顶点cinVexs[i]；for(i=0；iVexNum；i++){for(j=0；jVexNum；j++)AdjMax[i][j].adj=0；//邻接矩阵初始化各点不相邻}for(k=0；kArcNum；k++){cout"输入边的信息："；cinArcInfo.v1ArcInfo.v2；i=LocateVex(ArcInfo.v1)；j=LocateVex(ArcInfo.v2)；AdjMax[j][i].adj=AdjMax[i][j].ad

7、j=1；//无向图中两个顶点相邻}}voidUnDirectGraph：ShowGraph()//输出邻接矩阵{inti,j；for(i=0；iVexNum；i++){for(j=0；jVexNum；j++)cout""AdjMax[i][j].adj；coutendl；}}voidUnDirectGraph：InsertVex(char*&newVex)//向图中插入一个节点{Vexs[VexNum]=newVex；VexNum++；for(inti=0；iVexNum；i++){AdjMax[i][V

8、exNum-1].adj=AdjMax[VexNum-1][i].adj=0；//插入一个孤立节点}}voidUnDirectGraph：InsertArc(char*&v1,char*&v2)//在图中增加一条边{inti,j；i=LocateVex(v1)；j=LocateVex(v2)；if(i0

9、

10、j0)return；ArcNum++；AdjMax[i][j].adj=AdjMax[j][i].adj=1；}voidU