图邻接矩阵相关算法实现.doc

图邻接矩阵相关算法C+实现.cpp部分#include#includematrix.husing namespace std;int main()int item;cout输入矩阵大小:item; graphmatrix gmatrix(item); cout1:获取指定边权值endl;cout2:获取指定点的第一个邻接顶点endl;cout3:获取指定点相对于另一点的下一个临接点endl;cout4:深度优先遍历:endl;cout5:输出邻接矩阵:endl;cout6:插入一个顶点:endl;cout7:删除一个顶点:endl;cout8:插入一条边:endl;cout9:删除一条边:ch;while(ch!=0)switch(ch)case 1: int v1,v2; cout输入v1 ，v2:v1v2; cout权: gmatrix.getweight(v1,v2)endl;break;case 2:int v; cout输入指定点:v; coutfirst顶点: gmatrix.getfirstneighbor(v)endl; break;case 3:int v1,v2; cout输入v1,v2: v1v2; coutv1相对于v2的第一个邻接点:gmatrix.getnextneighbor(v1,v2)endl; break;case 4:gmatrix.DepthFS(); coutendl; break;case 5:gmatrix.print(); break;case 6: int v; cout输入欲插入顶点编号:v; gmatrix.insertv(v); gmatrix.print();break;case 7:int v; cout输入欲删除节点编号:v;gmatrix.delv(v);gmatrix.print();break; case 8:int v1,v2,w; cout输入v1,v2及其weight:v1v2w; gmatrix.inserte(v1,v2,w); break;case 9: int v3,v4; cout输入v1,v2:v3v4; gmatrix.dele(v3,v4); break; cout需要更多帮助吗?ch;if(ch=0)cout*谢谢使用*endl;return 0;.h部分#includeusing namespace std;templateclass graphmatrixprivate: int matrixmaxsize;int matrixsize;int maxweight;int edge256256;public:graphmatrix(int n);graphmatrix()cout*set memory free, program ends*matrixmaxsize)?1;-1);int getnumofV()return matrixsize;int getnumE();void insertv(int v);void delv(int v);void inserte(int v1,int v2,int w);void dele(int v1,int v2);templategraphmatrix:graphmatrix(int n)matrixmaxsize=256;maxweight=1000;if(n=matrixmaxsize) matrixsize=n;for(int i=0;in;i+)for(int j=0;jn;j+)cout输入点i+1到点j+1的边的权值edgeij;templateint graphmatrix:getweight(int& v1,int& v2)if(v1-1)=0&(v1-1)=0)&(v2-1)=matrixsize)return edgev1-1v2-1;else return -1;templateint graphmatrix:getfirstneighbor(int& v)if(v-1)=0&(v-1)matrixsize)for(int i=0;i0&edgev-1imaxweight)return i+1; return -1;templateint graphmatrix:getnextneighbor(int& v1,int& v2)if(v1-1)=0&(v1-1)=0&(v2-1)matrixsize)for(int j=0;j0&edgev1-1jmaxweight)return j+1;/遍找一行，看是否有其他邻接顶点/for(int i=v2;i0&edgev1-1imaxweight)return i+1;return -1;templatevoid graphmatrix:print()cout ;for(int i=0;imatrixsize;i+)couti+1 ;coutendl;for(int j=0;jmatrixsize;j+)cout j+1 ;for(int k=0;kmatrixsize;k+)cout edgejk ;coutendl;templatevoid graphmatrix:DepthFS()int * visited= new intmatrixsize;for(int i=0;imatrixsize;i+)visitedi=0;RDFS(1,visited);delete visited;templatevoid graphmatrix:RDFS(int v,int * visited)/针对有向图/coutv ;visitedv-1=1;int w=getfirstneighbor(v);while(w!=-1)if(visitedw-1=0)RDFS(w,visited);w=getnextneighbor(v,w); return ;templateint graphmatrix:getnumE()int num;for(int i=0;imatrixsize;i+)for(int j=0;j0&edgeijmaxweight)num+;return num;templatevoid graphmatrix:insertv(int v)if(v=matrixsize)cout节点已存在endl;return ;matrixsize+;for(int i=0;imatrixsize-1;i+)edgeiv-1=maxweight;edgev-1i=maxweight;edgev-1v-1=0;templatevoid graphmatrix:delv(int v)if(vmatrixsize)cout节点不存在endl;return ; int r,c;for(r=0;rv-1;r+)for(c=v;cmatrixsize;c+)edgerc-1=edgerc;for(r=v;rmatrixsize;r+)for(c=0;cv-1;c+)edger-1c=edgerc;for(r=v;rmatrixsize;r+)for(c=v;cmatrixsize;c+)edger-1c-1=edgerc;matrixsize-;templatevoid graphmatrix:inserte(int v1,int v2,int w)if(v1matrixsize|v2matrixsize|w=maxweight)cout参数异常0&edgev1-1v2-1maxweight)cout边已存在endl;return ; edgev1-1v2-1=w;template