软件技术基础实验二报告

1.采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。#include<stdio.h>#include<malloc.h>intn;structVNode{//顶点intposition;structVNode*next;};structArcNode{//弧intmark;structVNode*first;};voidDFS(structArcNode*v,structArcNode*w){//深度优先搜索structVNode*L;w->mark=1;L=w->first;while(L!=NULL){if((v+(L->position))->mark==0){DFS(v,(v+L->position));//递归调用}L=L->next;}}intmain(){inti,j,k;intnum=0;structArcNode*p;structVNode*temp;structVNode*flag;printf("\n请输入顶点个数n：");scanf("%d",&n);while(n<1){printf("你输入的值不合理，请重新输入：\n");scanf("%d",&n);}p=(structArcNode*)malloc(n*sizeof(structArcNode));/*说明：1.Vi表示第i个顶点，它在表中的位置为i-1，如V3在表中的位置为2;2.如果输入以V1为弧尾的所有弧(假设存在弧<V1,V3>和<V1,V2>)则输入：21-1(只需输入弧头的位置，并用-1表示结束)*/for(i=0;i<n;i++){//创建无向图printf("\n请输入以V%d为弧尾的所有弧，并以-1结束输入\n",i+1);scanf("%d",&k);if(k==-1){p[i].mark=0;p[i].first=NULL;}else{temp=(structVNode*)malloc(sizeof(structVNode));temp->position=k;temp->next=NULL;p[i].first=temp;p[i].mark=0;flag=temp;scanf("%d",&k);while(k!=-1){temp=(structVNode*)malloc(sizeof(structVNode));temp->position=k;temp->next=NULL;flag->next=temp;flag=temp;scanf("%d",&k);}}}i=0;while(p[i].mark==0){//计算连通分量的个数DFS(p,(p+i));num++;i=0;while(p[i].mark!=0&&i<n){i++;}}printf("此图的连通分量个数为：%d\n",num);return0;}

2.试基于图的深度优先搜索策略编写一程序，判别以邻接表方式存储的有向图中是否存在有顶点Vi到Vj顶点的路径(i≠j)。#include"stdio.h"#include"malloc.h"#include"conio.h"typedefstructArcNode{intadjvex;//该弧指向的顶点structArcNode*nextarc;//下一个弧intin;//判断是否遍历过该顶点}ArcNode;typedefstructVNode{intdata;//顶点信息ArcNode*firstarc;//指向第一条弧}VNode,AdjList[20];typedefstructALGraph{AdjListvertices;intvexnum,arcnum;//顶点数和弧数intkind;//图的种类标志感觉没什么用}ALGraph;intn,i,j;intm=0;ints=1;ALGraph*graph;voidread(ArcNode*firstarc){intx;chary;scanf("%c",&y);while(y=='')scanf("%c",&y);firstarc->nextarc=NULL;if(y=='\n'){return;}else{x=(int)y-48;ArcNode*t;t=newArcNode;t->nextarc=NULL;t->in=0;t->adjvex=x;firstarc->nextarc=t;read(firstarc->nextarc);}}//输入该顶点出发的弧直到回车voidmkgraph(ALGraph*graph){charrub;ArcNode*t;VNode*list;scanf("%c",&rub);for(;s<=n;s++){printf("%d",s);t=newArcNode;graph->vertices[s].firstarc=t;read(graph->vertices[s].firstarc);}}//用循环控制输入每个顶点的信息voidrun(ArcNode*firstarc){ArcNode*t;t=firstarc;if(t->adjvex==j){m=1;//若找到则m=1return;}if(t->in==0&&m==0&&t->adjvex>0&&t->adjvex<=n&&graph->vertices[t->adjvex].firstarc->nextarc!=NULL){t->in=1;run(graph->vertices[t->adjvex].firstarc->nextarc);}if(m==0&&t->nextarc!=NULL)run(t->nextarc);}//深度优先搜索voidmain(){graph=newALGraph;printf("图中有几个顶点:");scanf("%d",&n);printf("请以邻接表方式依次输入各顶点的关系以回车作为结束标志:\n");mkgraph(graph);printf("已为您生成图.\n\n请输入您要寻找路径的起点i和终点j(i!=j):");scanf("%d%d",&i,&j);while(i==j||i<=0||i>n||j<=0||j>n){printf("对不起,您输入的数据有误,请重新输入:");scanf("%d%d",&i,&j);}//控制输入的数据run(graph->vertices[i].firstarc->nextarc);if(m==1)printf("存在从%d到%d的路径.",i,j);elseprintf("不存在从%d到%d的路径.",i,j);getch();}

3.在上述例题中，如改用邻接表的方式存储图，试编一程序实现上述算法。顶点表nodelist的每个元素包含四个字段：infomarkpreout其中mark为布尔类型，用来标记顶点是否被访问过。开始时，所有元素的mark字段为false，每访问过一个顶点，则mark字段置为true。info为顶点值，pre为访问路径上该顶点的前驱顶点的序号，out指向该顶点的出边表。#include<stdio.h>#include<stdlib.h>#defineMAXV100typedefstruct//邻接矩阵存储结构{intno;intinfo;}VertexType;typedefstruct{intedges[MAXV][MAXV];intn,e;VertexTypevexs[MAXV];}MGraph;typedefstructANode//邻接表存储结构{intadjvex;structANode*nextarc;intinfo;}ArcNode;typedefstructVnode{intdata;ArcNode*firstarc;}VNode;typedefVNodeAdjList[MAXV];typedefstruct{AdjListadjlist;intn,e;}ALGraph;typedefstructnode{intdata;structnode*next;}List;voidMatToList(MGraphg,ALGraph*&G){inti,j,n=g.n;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<n;i++)G->adjlist[i].firstarc=NULL;for(i=0;i<n;i++)for(j=n-1;j>=0;j--)if(g.edges[i][j]!=0){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;}G->n=n;G->e=g.e;}staticints1=0;voidFind(ALGraph*G,intx,intl,intk,intvisited[],intpath[],intd){inti,node;ArcNode*r;visited[x]=1;d++;path[d]=x;if(x==l&&d==k){s1++;if(s1==1)printf("\n给定的两个顶点%d,%d之间存在长度为%d的简单路径.\n所有路径为：\n",path[0],l,k);for(i=0;i<=k;i++)printf("%d",path[i]);printf("\n");}r=G->adjlist[x].firstarc;while(r!=NULL){node=r->adjvex;if(visited[node]==0)Find(G,node,l,k,visited,path,d);r=r->nextarc;}visited[x]=0;d--;}intmain(){intpath[MAXV],visited[MAXV],A[MAXV][MAXV],i,j,m,l,k;MGraphg;ALGraph*G;printf("请输入顶点个数：");scanf("%d",&g.n);g.e=0;//printf("\n请输入路径条数：");//scanf("%d",&g.e);printf("\n请输入邻接矩阵：（若(vi,vj)属于E(G),A[i][j]=1；其他，A[i][j]=0）\n\n");for(i=0;i<g.n;i++){for(j=0;j<g.n;j++)scanf("%d",&A[i][j]);getchar();}for(i=0;i<g.n;i++)for(j=0;j<g.n;j++){g.edges[i][j]=A[i][j];if(A[i][j]==1)g.e++;}MatTo