文档介绍：数据结构课后习题标准答案作者:日期:(P235)的无向图,给出:表示该图的邻接矩阵。表示该图的邻接表。图中每个顶点的度。解:邻接矩阵:01110001001100100101011101110101001001**********邻接表:1 :2——3——4——NULL;2:1——4——5——NULL;3:1——4——6——NULL;4:1—2—3—5—6—7—NULL;5:2——4——7——NULL;6:3——4——7——NULL;7:4——5——6——NULL;图中每个顶点的度分别为: 3,3,3,6,3,3,3。,给出:(1) 从顶点1出发,按深度优先搜索法遍历图时所得到的顶点序(2) 从顶点1出发,按广度优先法搜索法遍历图时所得到的顶点序列。(1)DFS法:存储结构:本题采用邻接表作为图的存储结构,邻接表中的各个链表的结点形式由类型 L_NODE规定,而各个链表的头指针存放在数组 head中。数组e中的元素e[0],e[1],…..,e[m-1]给出图中的m条边,e中结点形式由类型E_NODES定。visit[i]数组用来表示顶点i是否被访问过。遍历前置visit各元素为0,若顶点i被访问过,则置visit[i]:,选择一个与v相邻接且未被访问过的的顶点w访问之,再从w开始进行深度优先搜索。每当到达一个其所有相邻接的顶点都被访问过的顶点,就从最后访问的顶点开始,依次退回到尚有邻接顶点未曾访问过的顶点 u,并从U开始进行深度优先搜索。这个过程进行到所有顶点都被访问过,或从任何一个已访问过的顶点出发,再也无法到达未曾访问过的顶点,则搜索过程就结束。数组,另一方面,先建立一个相应的具有 n个顶点,m条边的无向图的邻接表。初始化visit使其各个元素置为 0,表示图中每个顶点都没被访问过。下面给出程序:#include<>#defineMAXN50#defineMAXM100typedefstructl_node{intver;structl_node*link;}L_NODE;typedefstructe_node{intver1;intver2;}E_NODE;voidcreat_adj_list(L_NODE*head[],intn,E_NODEe[],intm){inti,u,v;L_NODE*p,*q;for(i=1;i<=n;i++)head[i]=NULL;for(i=0;i<m;i++){u=e[i].ver1;v=e[i].ver2;p=(L_NODE*)malloc(sizeof(L_NODE));p->ver=v;p->link=NULL;if(head[u]==NULL)head[u]=p;else{q=head[u];while(q->link!=NULL)q=q->link;q->link=p;}p=(L_NODE*)malloc(sizeof(L_NODE));p->ver=u;p->link=NULL;if(head[v]==NULL)head[v]=p;else{q=head[v];while(q->link!=NULL)q=q->link;q->link=p;}}}voidinit(intvisit[],intn){inti;for(i=1;i<=n;i++)visit[i]=0;}voiddfs(intu,L_NODE*head[],intvisit[]){L_NODE*t;visit[u]=1;printf("%4d",u);t=head[u];while(t!=NULL){if(visit[t->ver]==O)dfs(t->ver,head,visit);t=t->link;}}测试报告:voidmain(){L_NODE*head[MAXN];intvisit[MAXN],n,m,u;E_NODEe[12];e[0].ver1=1;e[0].ver2=3;e[1].ver1=1;e[1].ver2=4;e[2].ver1=1;e[2].ver2=2;e[3].ver1=2;e[3].ver2=4;e[4].ver1=2;e[4].ver2=5;e[5].ver1=3;e[5].ver2=6;e[6].ver1=3;e[6].ver2=4;e[7].ver1=4;e[7].ver2=6;e[8].ver1=4;e[8].ver2=7;e[9].ver1=4;e[9].ver2=5;e[10].ver1=5;e[10].ver2=7;e[11].ver1=6;e[11].ver2=7;creat_adj_list(head,7,e,12);init(visit,7);dfs(head