还剩16页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
第章主要算法的代码4C++实验1图的存储
1.图的邻接矩阵存储及输出#include iostreamusing namespace std;typedef charVertexType;typedef intEdgeType;#define MAXVEX10typedef struct{〃顶点类型应由用户定义VertexType vexs[MAXVEX];〃边上的权值类型应由用户定义EdgeType arc[MAXVEX]〃最大顶点数,应由用户定义[MAXVEX];//邻接矩阵,可看作边int numVertexes,numEdges;〃图中当前的顶点数和边数}Graph;int locatesGraph*g,char ch{//定位int i=0;fori=0;ig-numVertexes;i++{ifgvexs[i]==ch{break;ifi=g-numVertexes{return-1;return i;〃建立一个无向网图的邻接矩阵表示void CreateGraphGraph*g{int i,j,k,w;coutvv”输入顶点数和边数:“endl;cin»g-numVertexes»g-numEdges;coutv”请输入顶点名称,每个顶点用单个字母或单个数字表示,并以回车键结束:fori=0;i n«endl;g-numVertexes;i++{g-vexs[i]=getchar;whileg-vexs[i]==\n{g-vexs[i]=getchar;你输入的顶点是”;COUt«”fori=0;ig-numVertexes;i++{cout«g-vexs[i];q二getchar;whileq==\n{q=getchar;cin»w;int m=-1;int n=-1;m=locatesg,p;n=locatesg,q;ifn==-1||m==-1{fprintfstderr,nthere isno thisvertex.\nn;return;g-arc[m][n]=w;g-arc[n][m]=g-arc[m][n];〃因为是无向图,矩阵对称void PrimGraph g{Edges edges[MAXVEX];bool s[MAXVEX];//bool型变量的S数组表示i是否已经包括在S中int i,k;s
[0]=true;〃从第一个结点开始寻找,扩展fori=l;ig.numVertexes;i++{//简单初始化edges[i].lowcost=g.arc
[0][i];edges[i].top=0;edges[i].tail=i;s[i]=false;fori=0;ig.numVertexes;i++{int min=1000;〃最小值,设大一点的值int j=l;fork=l;kg.numVertexes;k++{〃寻找最小值ifedges[k].Iowcostmin!s[k]{min=edges[k].lowcost;j=k;}s[j]=tnie;〃添加点j到集合S中fork=1;kg.numVertexes;k++{〃因为新加入了j点,所以要查找新加入的j点到未在S中的点K中的权值是不是可以因此更小ifg.arc[j][k]edges[k].lowcost!s[k]{edges[k].lowcost=g.arc[j][k];edges[k].top=j;}cout«n取小生成树为endl;fori=l;ig.numVertexes;i++cout«g.vexs[edges[i].top]«n-n«g.vexs[edges[i].tail]«n边值为n«edges[i].lowcost«endl;int main{Graph g;CreateGraphg;〃邻接矩阵创建图Primg;return0;}【运行结果】口c:\users\administrator.pc-201811182209\documents\visual studio
201...输入顶点数和边数611请输入顶点名称,每个顶点用单个字母或单个数字表示,并以回车键结束ABCDEF4845314BC20BE28CD请边为边为意为按露嚣生树键任鬻成边边续边有贬方然容居髓;名称,顶点名称和权值,每个输入后面以回键结束Jrrr算法运行结果Prim算法实现(采用邻接矩阵存储)Kruskal#include iostreainusing namespacestd;typedef charVertexType;typedef intEdgeType;#define MAXVEX100〃顶点类型应由用户定义#define MAX65535typedef struct{〃边上的权值类型应由用户定义VertexType vexs[MAXVEX];EdgeType〃最大顶点数,应由用户定义〃以65535代表无穷大int numVertexes,numEdges;/〃顶点表/图中当前的顶点数和arc[M AXVEX][MAXVEX];//邻接矩阵,可看作边边数DEFEFBE-8ft-039115hBc..48193•0}Graph;typedef struct{int top,tail;//用于存储选中边的两个顶点下标EdgeType cost;//边值int fig;}Edges;〃边结构三元组Edges e[MAXVEX];int locatesGraph*g,char ch{〃定位int i=0;fori=0;ig-numVertexes;i++{ifg-vexs[i]==ch{break;ifi=g-numVertexes{return-1;return i;//建立一个无向网图的邻接矩阵表示void CreateGraphGraph*g{int i,j,k,w;coutvv”输入顶点数和边数:endl;cin»g-numVertexes»g-numEdges;cout”请输入顶点名称,每个顶点用单个字母或单个数字表示,并以回车键结束«endl;fori=0;i g-numVertexes;i++{g-vexsfi]=getchar;whileg-vexs[i]==\n{g-vexs[i]=getchar;cout”你输入的顶点是”;fori=0;ig-numVertexes;i++{cout«g-vexs[i];cout«endl;fori=0;ig-numEdges;i++{forj=0;jg-numEdges;j++{g-arc[i][j]=MAX;//邻接矩阵初始化cout〈”输入边vi,vj上的顶点i名称,顶点j名称和权值海个输入后面以回键结束:”endl;fork=0;kg-numEdges;k++{char p,q;p二getchar;whilep==\n{p=getchar;q=getchar;whileq==\n{q=getchar;cin»w;int m=-1;int n=-1;m=locatesg,p;n=locatesg,q;ifn==-1||m==-1{fprintfstderr,nthere isno thisvertex.\nn;return;g-arc[m][n]=w;g-arc[n][m]=g-arc[m][n];〃因为是无向图,矩阵对称e[k].top=n;e[k].tail=m;e[k].cost=w;e[k].flg=0;void sorteGraph*g,Edges e[MAXVEX]{int ij;Edges f;fori=0;ig-numEdges;i++forj=1;jg-numEdges-i;j++ife[j-1].coste[j].cost{f.cost=e[j].cost;e[j].cost=e[j-l].cost;e[j-l].cost=f.cost;f.top=e[j].top;e[j].top=efj-l].top;e[j-l].top=f.top;f.tail=e[j].tail;e[j].tail=e[j-l].tail;e[j-l].tail=f.tail;}void KruskalGraph*g,Edges e[MAXVEX]{int ij,fl=0,f2=0;sorteg,e;e
[0].flg=l;fori=1;ig-numEdges;i++{forj=0;jg-numEdges;j++{ife[i].top=efj].top||e[i].top=e[j].tail e[j].flgfl=l;ife[i].tail==e[j].tail||e[i].tail==e[j].top e[j].flgf2=l;if!fl==f2fl==l;e[i]fg=lfl=0;f2=0;cout«n最小生成树为endl;fori=0;ig-numEdges;i++{ife[i].flg==lcout«g-vexs[e[i].top]«n-«g-vexs[e[i].tail]«*边值为e[i].cost«endl;}int main{Graph g;CreateGraphg;〃邻接矩阵创建图Kruskalg,e;return0;}【运行结果】输入顶点数和边数611请输入顶点名称,每个顶点用单个字母或单个数字表示,并以回车键结束ABCDEF小生成最边边边边边请意按任rrr落画畲黑?再贵居获富名称,顶点名称和权值,每个输入后面以回键结束j4算法运行结果Kruskal845拓扑排序算法实现3#include iostream#include stackusingnamespacestd;#define MAX_VERTEX_NUM26stackint s;typedef struct ArcNode{〃表结点结构int adjvex;…续structArcNode*nextarc;ArcNode{nextarc=0;}}ArcNode;typedef structVNode{//项点信息表结构F-EFE-.1252911D40803348910int data;ArcNode*firs tare;VNode{firstarc=O;}}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{AdjList vertices;int vexnum,arcnum;int kind;JALGraph;bool TopologicalSortALGraphG,int*indegree{int i,k;fori=l;iG.vexnum+l;i++{if!indegree[i]{s.push⑴;}//如果顶点i的入度为0,i进栈int count=0;ArcNode*p;while!s.empty{〃栈不为空时循环i=s.top;//取栈项元素s.pop;〃出栈cout〈vG.vertices[i].datavv”—”;〃输出项点count++;〃记录已输出的项点数〃以i项点为尾的弧删除,与之相连的弧头项点的入度减一forp=G.vertices[i].firstarc;p;p=p-nextarc{k=p-adjvex;indegree[k]--;//入度减一if!indegree[k]s.pushk;〃如果顶点k的入度为0,k进栈ifcountG.vexnum returnfalse;//如果输出的项点少于图的项点,则存在在环return true;int main{int i;ALGraph g;cout”输入节点数和边数”;cin»g.vexnum»g.arcnum;fori=1;ig.vexnum+1;i++g.vertices[i].data=i;mt b,e;ArcNode*p;int*indegree=new int[g.vexnum+l];//注意int*a=new intn;申请一个整型变量空间,赋初值为n,并定义一个整型指针a指向该地址空间//int*indegree=int*mallocsizeofint*g.vexnum4-1;memsetindegree,0,sizeofint*g.vexnum+l;cout”逐一输入边的顶点对,形如35H«endl;〃/*以下for语句构造有向图的邻接表*/fori=1;ig.arcnum+1;i++{coutvv第vivv条边〈cin»b»e;p=new ArcNode;p-adjvex=e;p-nextarc=g.vertices[b].firs tare;g.vertices[b].firstarc=p;〃采用头插法indegree[e]++;〃顶点e的入度加1ifTopologicalSortg,indegreecout正常完成!n«endl;elsecoutvv”该有向图有回路!endl;return0;【运行结果】输返X矍7124••逐返.B形文口边第返45顶第返7一第款・2线第・矗34第7\21第41051162第5323第334第安2-第键15第/・-演第7米螯71-一返64请-返卖rrr口c:\users\administrator,pc-201811182209\d...向口拓扑排序算法运行结果234724565怅.••-_________________________cout«endl;fori=0;ig-numEdges;i++{forj=0;jg-numEdges;j++{g-arc[i][j]=0;〃邻接矩阵初始化fork=0;kg-numEdges;k++{char p,q;cout«”输入边vi,vj上的顶点i名称,顶点j名称和权值,每个输入后面以回键结束:“《endl;p=getchar;whilep==*\n*{p=getchar;q=getchar;whileq==\n{q=getchar;cin»w;int m=-1;int n=-1;m=locatesg,p;n=locatesg,q;ifn==-1||m==-1{fprintfstderr,nthere isno thisvertex.\nH;return;g-arc[m][n]=w;g-arc[n][m]=g-arc[m][n];〃因为是无向图,矩阵对称〃打印图void printGraphGraph g{int i,j;coutv”这个邻接矩阵为vvendl;fori=0;ig.numVertexes;i++{forj=0;jg.numVertexes;j++{cout«n n«g.arc[i][j];cout«endl;int mainintargc,char**argv{Graphg;CreateGraphg;〃邻接矩阵创建图printGraphg;
2.图的邻接表存储及输出/**/邻接表表小的图结构#include iostreamusingnamespace std;#define DEBUG//最大顶点数#define MAXVEX1000〃顶点类型应由用户定义typedef charVertexType;〃边上的权值类型应由用户定义typedef intEdgeType;{〃边表结点typedef struct EdgeNode〃邻接点域,存储该顶点对应的下标int adjvex;〃用于存储权值,对于非网图可以不需要EdgeType weigth;structEdgeNode*next;〃链域,指向下一个邻接点return0;}EdgeNode;typedef structVertexNode{〃顶点表结构VertexType data;〃顶点域,存储顶点信息EdgeNode*firstedge;//边表头指针}VertexNode,AdjList[MAXVEX];typedef structAdjListadjList;int numVertexes,numEdges;〃图中当前顶点数和边数JGraphList;int LocateGraphList*g,char ch{int i;fori=0;i MAXVEX;i++ifch==g-adjList[i].data break;ifi=MAXVEX{fprintfstderr,nthere isno vertex.\nH;return-1;return i;//建立图的邻接表结构void CreateGraphGraphList*g{int i,j,k;EdgeNode*e;EdgeNode*f;cout«”输入顶点数和边数:\n”;cin»g-numVertexes»g-numEdges;cout”请输入少于10个顶点,每个顶点用单个字母或单个数字表示,并以回车键结束:“endl;fori=0;ig-numVertexes;i++{g-adjList[i].data=getchar;〃输入顶点信息g-adjList[i].firstedge=NULL;〃将边表置为空表whileg-adjList[i].data==\n{g-adjList[i].data=getchar;fork=0;kg-numEdges;k++{〃建立边表coutvv”输入边vi,vj上的顶点序号及权值:“endl;char p,q;int w;p=getchar;whilep==\n{p=getchar;q=getchar;whileq==\n{q=getchar;cin»w;int m,n;m=Locateg,p;n=Locateg,q;ifm二二-1||n二二-1{return;}〃向内存申请空间,生成边表结点e=EdgeNode*mallocsizeofEdgeNode;ife=NULL{fprintfstderr,nmalloc error.\nn;return;e-adjvex=n;//邻接序号为n〃将e指针指向当前顶点指向的结构e-weigth二w;//权值为we-next=g-adjList[m].firstedge;〃将当前顶点的指针指向eg-adjList[m].firstedge=e;f二EdgeNode*mallocsizeofEdgeNode;iff=NULL{fprintfstderr,Mmalloc error.\nn;return;f-adjvex=m;f-weigth=w;f-next=g-adjList[n].firstedge;g-adjList[n].firstedge=f;}void printGraphGraphList*g{int i=0;whileg-adjList[i].firstedge!=NULLi g-numVertexescout”顶点:n«g-adjList[i].data;EdgeNode*e=NULL;e=g-adjList[i].firstedge;whilee!=NULL{cout«n-;cout«nH«e-adjvex;cout«n,n«e-weigth«nn;e=e-next;〃图中当前的顶点数和边数}i++;cout«endl;int mainintargc,char**argv{GraphList g;CreateGraphg;printGraphg;return0;实验2图的遍历#include queue#include iostreamusingnamespace std;//最大顶点数#define MAXVEX100typedef intBoolean;//Boolean是布尔类型,其值是TRUE或FALSEBoolean visited[MAXVEX];〃访问标志数组#define TRUE1#define FALSE0〃顶点类型应由用户定义typedef charVertexType;typedef intEdgeType;〃边上的权值类型应由用户定义typedef struct{VertexType vexs[MAXVEX];〃顶点表EdgeType arc[M AXVEX][MAXVEX];//邻接矩阵,可看作边int numVertexes,numEdges;}Graph;int locatesGraph*g,char ch{〃定位int i=0;fori=0;ig-numVertexes;i++{ifg-vexs[i]==ch{break;ifi=g-numVertexes{return-1;return i;〃建立一个无向网图的邻接矩阵表示void CreateGraphGraph*g{int i,j,k;cout输入顶点数和边数:n«endl;cin»g-numVertexes»g-numEdges;cout”请输入顶点名称,每个顶点用单个字母或单个数字表示,并以回车键结束endl;fori=0;ig-numVertexes;i++{g-vexs[i]=getchar;whileg-vexs[i]==\n{g-vexs[i]=getchar;coutvv”你输入的顶点是:“;fori=0;ignumVertexes;i++{cout«g-vexs[i];cout«endl;fori=0;ig-numEdges;i++{forj=0;jg-numEdges;j++{g-arc[i][j]=0;//邻接矩阵初始化fork=0;kg-numEdges;k++{char p,q;cout输入边vi,vj上的顶点i名称,顶点j名称,每个输入后面以回键结束:“vvendl;p=getchar;whilep==\n{p=getchar;q=getchar;whileq==\n{q=getchar;int m=-1;int n=-1;m=locatesg,p;n=locatesg,q;ifn二二-1||m==-1{fprintfstderr,nthere isno thisvertex.\nH;return;}//getchar;g-arc[m][n]=1;g-arc[n][m]=g-arc[m][n];〃因为是无向图,矩阵对称void DFSGraphg,int i{〃邻接矩阵的深度优先递归算法intj;visited[i]=TRUE;cout«g.vexs[i];〃打印顶点,也可以其他操作forj=0;jg.numVertexes;j++{ifg.arc[i][j]==1!visited]{DFSg,j;〃对为访问的邻接顶点递归调用〃邻接矩阵的深度遍历操作void DFSTraverseGraphg{int i;fori=0;ig.numVertexes;i++{visited[i]=FALSE;//初始化所有顶点状态都是未访问过状态cout〈”深度优先遍历次序为”;fori=0;ig.numVertexes;i++{if!visited[i]{〃对未访问的顶点调用DFS,若是连通图,只会执行一次DFSg,i;cout«endl;〃邻接矩阵的广度遍历算法void BFSTraverseGraphg{int i,j;queueintq;fori=0;ig.numVertexes;i++{visited[i]=FALSE;广度优先遍历次序为COUtVV”11;fori=0;ig.numVertexes;i++{〃对每个顶点做循环if!visited[i]{//若是未访问过visited[i]=TRUE;coutvg.vexs[i];//打结点q.push⑴;〃将此结点入队列while!q.empty{〃将队中元素出队列,赋值给int m;m=q.front;;q.popOforj=0;jg.numVertexes;j++{〃判断其他顶点若与当前顶点存在边且未访问过ifg.arc[m][j]==1!visited[j]{visitedfj]=TRUE;cout«g.vexs[j];q.push;int mainintargc,char**argv{Graphg;CreateGraphg;〃邻接矩阵创建图DFSTraverseg;BFSTraverseg;return0;Pr im算法实现#include iostreamusingnamespace std;typedef charVertexType;typedef intEdgeType;〃顶点类型应由用户定义#define MAXVEX100〃边上的权值类型应由用户定义#define MAX65535〃最大顶点数,应由用户定义typedef struct{〃以65535代表无穷大VertexType vexs[MAXVEX];EdgeType〃顶点表arc[MAXVEX][MAXVEX];〃邻接矩阵,可看作边int numVertexes,numEdges;〃图中当前的顶点数和边数}Graph;typedef struct{int top,tail;//用于存储选中边的两个顶点下标EdgeType lowcost;〃最小边值}Edges;〃边结构三元组〃定位int locatesGraph*g,char ch{int i=0;fori=0;ig-numVertexes;i++{ifg-vexs[i]==ch{break;}ifi=g-numVertexes{return-1;return i;〃建立一个无向网图的邻接矩阵表示void CreateGraphGraph*g{int i,j,k,w;coutvv”输入顶点数和边数:vvendl;cin»g-numVertexes»g-numEdges;coutv”请输入顶点名称,每个顶点用单个字母或单个数字表示,并以回车键结束n«endl;fori=0;ig-numVertexes;i++{g-vexs[i]=getchar;whileg-vexs[i]==\n{g-vexs[i]=getchar;coutv〈”你输入的顶点是”;fori=0;ig-numVertexes;i++{cout«g-vexs[i];cout«endl;fori=0;ig-numEdges;i++{forj=0;jg-numEdges;j++{g-arc[i][j]=MAX;//邻接矩阵初始化fork=0;kg-numEdges;k++{char p,q;cout«”输入边vi,vj上的顶点i名称,顶点j名称和权值,每个输入后面以回键结束:“endl;p=getchar;whilep==\n{p=getchar;。