用邻接表存储图并输出结果

精心整理课程设计题目九：图的广度优先遍历基本要求：采用邻接表存储结构实现图的广度优先遍历。

（2）对任意给定的图（顶点数和边数自定），建立它的邻接表并输出；（3）实现图的广度优先遍历*/#include<iostream.h>#include<stdio.h>#include<malloc.h>#defineMAX_NUM20intvisited[MAX_NUM]={0};typedefintVertexType;typedefenum{DG=1,UDG}GraphKind;typedefstructArcNode{intadjvex;intweight;structArcNode*nextarc;ArcNode*info;}ArcNode;typedefstructVNode{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;GraphKindkind;}ALGraph;voidPRIN(ALGraph&G);voidCreat_adjgraph(ALGraph&G);voidbfs(ALGraph&G,intv);voidCreat_adjgraphDG(ALGraph&G);voidCreat_adjgraphUDG(ALGraph&G);voidCreat_adjgraph(ALGraph&G);voidCreat_adjgraphDG(ALGraph&G){inti,s,d;ArcNode*p=NULL,*q=NULL;G.kind=DG;printf("请输入顶点数和边数：");scanf("%d%d",&G.vexnum,&G.arcnum);for(i=0;i<G.vexnum;++i){printf("第%d个顶点信息：",i+1);scanf("%d",&G.vertices[i].data);G.vertices[i].firstarc=NULL;}for(i=0;i<G.arcnum;++i){printf("第%d条边的起始顶点编号和终止顶点编号：",i+1);scanf("%d%d",&s,&d);while(s<1||s>G.vexnum||d<1||d>G.vexnum){printf("编号超出范围，重新输入");scanf("%d%d",&s,&d);}s--;d--;p=new(ArcNode);p->adjvex=d;p->nextarc=G.vertices[s].firstarc;G.vertices[s].firstarc=p;}}voidCreat_adjgraphUDG(ALGraph&G){inti,s,d;ArcNode*p,*q;G.kind=UDG;printf("请输入顶点数和边数：");scanf("%d%d",&G.vexnum,&G.arcnum);for(i=0;i<G.vexnum;++i){printf("第%d个顶点信息：",i+1);scanf("%d",&G.vertices[i].data);G.vertices[i].firstarc=NULL;}for(i=0;i<G.arcnum;++i){printf("第%d条边的起始顶点编号和终止顶点编号：",i+1);scanf("%d%d",&s,&d);while(s<1||s>G.vexnum||d<1||d>G.vexnum){printf("编号超出范围，重新输入");scanf("%d%d",&s,&d);}s--;d--;p=new(ArcNode);p->adjvex=d;p->nextarc=G.vertices[s].firstarc;G.vertices[s].firstarc=p;q=new(ArcNode);q->adjvex=s;q->nextarc=G.vertices[d].firstarc;G.vertices[d].firstarc=q;}}voidPRIN(ALGraph&G){inti;ArcNode*p;if(G.kind==DG||G.kind==UDG){for(i=0;i<G.vexnum;++i){printf("V%d:",G.vertices[i].data);p=G.vertices[i].firstarc;while(p!=NULL){printf("%d\t",p->adjvex+1);p=p->nextarc;}printf("\n");}}}voidbfs(ALGraph&G,intv){v--;ArcNode*p;intqueue[MAX_NUM],front=0,rear=0;intw,i;for(i=0;i<G.vexnum;i++)visited[i]=0;printf("%4d",v+1);visited[v]=1;rear=(rear+1)%MAX_NUM;queue[rear]=v;while(front!=rear){front=(front+1)%MAX_NUM;w=queue[front];p=G.vertices[w].firstarc;while(p!=NULL){if(visited[p->adjvex]==0){printf("%3d",p->adjvex+1);visited[p->adjvex]=1;rear=(rear+1)%MAX_NUM;queue[rear]=p->adjvex;}p=p->nextarc;}}printf("\n");}voidCreat_adjgraph(ALGraph&G){printf("1：有向图2：无向图\n");printf("请根据上述提示输入图的类型：");scanf("%d",&G.kind);switch(G.kind){caseDG:Creat_adjgraphDG(G);PRIN(G);break;caseUDG:Creat_adjgraphUDG(G);PRIN(G);break;default:printf("ERROR");break;}}voidmain(){ALGraphG;Creat_adjgraph(G);printf("\n");printf("广度优先搜索遍历序列为：\n");bfs(G,1);printf("\n");}。

//用邻接表存储有向图，输出各顶点的出度和入度#include <cstdio>#include <cstdlib>#define MAXN 100struct ArcNode //边结点{int adjvex; //有向边的另一个邻接点的序号ArcNode *nextarc; //指向下一个边结点的指针};struct VNode //顶点{int data; //顶点信息ArcNode *head1; //出边表的表头指针ArcNode *head2; //入边表的表头指针};struct LGraph //图的邻接表存储结构{VNode vertexs[MAXN]; //顶点数组int vexnum, arcnum; //顶点数和边数};LGraph lg; //图(邻接表存储)void CreateLG( ) //采用邻接表存储表示，构造有向图G{int i = 0; //循环变量ArcNode *pi; //用来构造边链表的边结点指针int v1, v2; //有向边的两个顶点for( i=0; i<lg.vexnum; i++ ) //初始化表头指针为空lg.vertexs[i].head1 = lg.vertexs[i].head2 = NULL;for( i=0; i<lg.arcnum; i++ ){scanf( "%d%d", &v1, &v2);//输入一条边的起点和终点v1--; v2--;pi = new ArcNode; //假定有足够空间pi->adjvex = v2;pi->nextarc = lg.vertexs[v1].head1; //插入链表lg.vertexs[v1].head1 = pi;pi = new ArcNode; //假定有足够空间pi->adjvex = v1;pi->nextarc = lg.vertexs[v2].head2; //插入链表lg.vertexs[v2].head2 = pi;}//end of for}//end of CreateLG//释放图G邻接表各顶点的边链表中的所有边结点所占的存储空间void DeleteLG( ){int i; //循环变量ArcNode *pi; //用来指向边链表中各边结点的指针for( i=0; i<lg.vexnum; i++ ){pi = lg.vertexs[i].head1;//释放第i个顶点出边表各边结点所占的存储空间while( pi!=NULL ){lg.vertexs[i].head1 = pi->nextarc;delete pi;pi = lg.vertexs[i].head1;}pi = lg.vertexs[i].head2;//释放第i个顶点入边表各边结点所占的存储空间while( pi!=NULL ){lg.vertexs[i].head2 = pi->nextarc;delete pi;pi = lg.vertexs[i].head2;}}}int main( ){int i; //循环变量int id, od; //顶点的入度和出度ArcNode *pi; //用来遍历边链表的边结点指针while( 1 ){lg.vexnum = lg.arcnum = 0;//首先输入顶点个数和边数scanf( "%d%d", &lg.vexnum, &lg.arcnum );if( lg.vexnum==0 ) break; //输入数据结束CreateLG( ); //构造有向图的邻接表结构for( i=0; i<lg.vexnum; i++ ) //统计各顶点出度并输出{od = 0;pi = lg.vertexs[i].head1;while( pi!=NULL ){od++; pi = pi->nextarc;}if(i==0) printf( "%d", od );else printf( " %d", od );}printf( "\n" );for( i=0; i<lg.vexnum; i++ ) //统计各顶点入度并输出{id = 0;pi = lg.vertexs[i].head2;while( pi!=NULL ){id++; pi = pi->nextarc;}if(i==0) printf( "%d", id );else printf( " %d", id );}printf( "\n" );DeleteLG( ); //释放}return 0;}代码来自共享。

《数据结构与算法分析》课程实验报告【实验目的】1. 理解图形结构的逻辑和存储特点。

2. 掌握图形结构遍历递归算法。

【实验内容】1. 用邻接矩阵或者邻接表存储一个图形结构。

2. 采用深度或者广度优先搜索算法，遍历一个图，并输出遍历结果。

【实验方式】个人实验。

【实验设备与环境】PC机，Windows XP操作系统，VC++6.0开发环境。

【数据结构及函数定义】（1）类的定义：类的数据成员，成员函数．．．．．．．．．．．．．．．．．．．（2）主函数main（）实现初始化操作，完成对子函数的调用．．．．．．．．．．．．．．．．．．．（3）子函数．．．．．．．．．．．．．．．．．．．。

【测试数据与实验结果】（请用截图的方式展示实验结果，并辅以必要的文字说明）【源程序清单】（请附上源程序）#include<iostream>using namespace std;#include<string.h>class Graph{public:c har Vtx[20];d ouble AdjMtx[20][20];i nt CurrentVnum;i nt CurrentEnum;G raph(){CurrentVnum=CurrentEnum=0;} i nt first_adj(int v);i nt next_adj(int v1,int v2);v oid visite(int v);v oid DFS();v oid DFS(int v,int visited[]);~Graph(){}};int Graph::first_adj(int v){f or(int v1=0;v1<CurrentVnum;v1++)if(AdjMtx[v][v1]>0)return v1;return -1;}int Graph::next_adj(int v1,int v2) {f or(int vn=v2+1;vn<CurrentVnum;vn++)if(AdjMtx[v1][vn]>0)return vn;return -1;}void Graph::visite(int v){c out<<Vtx[v]<<" ";}void Graph::DFS(){i nt *visited=new int[CurrentVnum];f or(int i=0;i<CurrentVnum;i++)visited[i]=0;f or(i=0;i<CurrentVnum;i++){if(visited[i]==0)DFS(i,visited);}d elete[] visited;}void Graph::DFS(int v,int visited[]) {v isite(v);v isited[v]=1;i nt w=first_adj(v);w hile(w!=-1){if(!visited[w])DFS(w,visited);w=next_adj(v,w);}}int LocateVex(Graph G,char u){i nt i;f or(i=0;i<G.CurrentVnum;i++)if(u==G.Vtx[i])return i;return -1;}void creat(Graph &G){i nt i,j,k;c har va,vb;c out<<"请输入图的顶点数,弧数:";c in>>G.CurrentVnum>>G.CurrentEnum;c out<<"请输入"<<G.CurrentVnum<<"个顶点的值:";f or(i=0;i<G.CurrentVnum;i++)cin>>G.Vtx[i];f or(i=0;i<G.CurrentVnum;i++)for(j=0;j<G.CurrentVnum;j++)G.AdjMtx[i][j]=0;c out<<"请输入"<<G.CurrentEnum<<"条弧的弧尾,弧头(以空格作为间隔):\n";f or(k=0;k<G.CurrentEnum;k++){cin>>va>>vb;i=LocateVex(G,va);j=LocateVex(G,vb);if(i!=j){G.AdjMtx[i][j]=1;G.AdjMtx[j][i]=1;}else G.AdjMtx[i][j]=1;}}void main(){G raph G;c reat(G);c out<<"深度优先搜索序列:"<<endl;G.DFS();c out<<endl;。

一、应用题1．首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。

1题图答．深度优先遍历序列：125967384宽度优先遍历序列：123456789注：（1）邻接表不唯一，这里顶点的邻接点按升序排列（2）在邻接表确定后，深度优先和宽度优先遍历序列唯一（3）这里的遍历，均从顶点1开始2．给出图G：（1）．画出G的邻接表表示图；（2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。

（3）宽度优先生成树3.在什么情况下，Prim算法与Kruskual算法生成不同的MST？答．在有相同权值边时生成不同的MST，在这种情况下，用Prim或Kruskal也会生成不同的MST4．已知一个无向图如下图所示，要求分别用Prim 和Kruskal 算法生成最小树（假设以①为起点，试画出构造过程）。

答．Prim 算法构造最小生成树的步骤如24题所示，为节省篇幅，这里仅用Kruskal 算法，构造最小生成树过程如下：（下图也可选(2,4)代替(3,4),(5,6)代替(1,5)）5．G=(V,E)是一个带有权的连通图,则：（1）．请回答什么是G 的最小生成树； （2）．G 为下图所示,请找出G 的所有最小生成树。

28题图答．（1）最小生成树的定义见上面26题 （2）最小生成树有两棵。

（限于篇幅，下面的生成树只给出顶点集合和边集合，边以三元组（Vi,Vj,W ）形式），其中W 代表权值。

V （G ）={1，2，3，4，5} E1(G)={(4，5，2)，（2，5，4），（2，3，5），（1，2，7）}；E2(G)={(4，5，2），（2，4，4），（2，3，5），（1，2，7）}6．请看下边的无向加权图。

（1）．写出它的邻接矩阵。

（2）．按Prim 算法求其最小生成树，并给出构造最小生成树过程中辅助数组的各分量值。

辅助数组各分量值：7．已知世界六大城市为:(Pe)、纽约(N)、巴黎(Pa)、伦敦(L) 、东京(T) 、墨西哥(M),下表给定了这六大城市之间的交通里程:世界六大城市交通里程表(单位:百公里)（1）．画出这六大城市的交通网络图;（2）．画出该图的邻接表表示法;（3）．画出该图按权值递增的顺序来构造的最小(代价)生成树.8．已知顶点1-6和输入边与权值的序列（如右图所示）：每行三个数表示一条边的两个端点和其权值，共11行。