数据结构教学课件作者李学刚电子课件源代码05单元5图.doc

《数据结构教学课件作者李学刚电子课件源代码05单元5图.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、单元5图源代码SC020201050011．源代码编号SC020201050012．源代码来源单元5图5.2.13．问题描述建立无向网络的算法4．程序代码voidCreateMGraph(MGraph*G){//建立无向网（图）的邻接矩阵表示inti,j,k;EdgeTypew;printf("读入顶点数和边数：");scanf("%d%d",&G->n,&G->e);//输入顶点数边数getchar();printf("读入顶点信息，建立顶点表:");for(i=0;in;i++)//读入顶点信息，建立顶点表G->vexs[i]=getchar();get

2、char();for(i=0;in;i++)for(j=0;jn;j++)G->edges[i][j]=0;//邻接矩阵初始化for(k=0;ke;k++){//读入e条边,建立邻接矩阵scanf("%d%d%d",&i,&j,&w);//输入权wG->edges[i][j]=w;G->edges[j][i]=w;}}SC020201050021．源代码编号SC020201050022．源代码来源单元5图5.2.13．问题描述建立无向图的邻接表算法4．程序代码voidCreateALGraph(ALGraph*G){//建立无向图的邻接表in

3、ti,j,k;EdgeNode*s;scanf("%d%d",&G->n,&G->e);//读入顶点数和边数getchar();for(i=0;in;i++){//建立顶点表G->adjlist[i].vertex=getchar();//读入顶点信息G->adjlist[i].firstedge=NULL;//边表置为空表}for(k=0;ke;k++){//建立边表scanf("%d%d",&i,&j);//读入边(vi,vj)顶点对序号s=(EdgeNode*)malloc(sizeof(EdgeNode));//生成边表结点if(s==NUL

4、L){puts("空间申请失败");return;}s->adjvex=j;//邻接点序号为js->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s;//将新结点*s插入顶点vi的边表头部s=(EdgeNode*)malloc(sizeof(EdgeNode));if(s==NULL){puts("空间申请失败");return;}s->adjvex=i;//邻接点序号为is->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=s;//将新结点*s插入

5、顶点vj的边表头部}}SC020201050031．源代码编号SC020201050032．源代码来源单元5图5.3.13．问题描述邻接矩阵表示的深度优先遍历算法4．程序代码intvisited[VertexNum]={0};//定义标志向量voidDFSM(MGraph*G,inti){//以vi为出发点进行搜索，设邻接矩阵是0,l矩阵SC02020105003intj;printf("%4c",G->vexs[i]);//访问顶点vivisited[i]=1;for(j=0;jn;j++)//依次搜索vi的邻接点if((G->edges[i][j]==1

6、)&&(!visited[j]))DFSM(G,j);//(vi,vj)∈E，且vj未访问过}voidDFSTraverse(MGraph*G){//深度优先遍历以邻接矩阵表示Ginti;for(i=0;in;i++)visited[i]=0;//标志向量初始化for(i=0;in;i++)if(!visited[i])//vi未访问过DFSM(G,i);//以vi为源点开始DFSM搜索}SC020201050041．源代码编号SC020201050042．源代码来源单元5图5.3.13．问题描述邻接表表示的深度优先搜索算法4．程序代码intvisi

7、ted[VertexNum]={0};//定义标志向量voidDFS(ALGraph*G,inti){//以vi为出发点进行深度优先搜索EdgeNode*p;printf("%4c",G->adjlist[i].vertex);//访问顶点vivisited[i]=1;//标记vi已访问p=G->adjlist[i].firstedge;//取vi边表的头指针while(p){//依次搜索vi的邻接点vj，这里j=p->adjvexif(!visited[p->adjvex])//若vi尚未被访问DFS(G,p->adjvex);//则以vj为出发点向纵深搜索p