文档介绍：(P235)的无向图,给出:螄表示该图的邻接矩阵。肂表示该图的邻接表。虿图中每个顶点的度。芀解:袅邻接矩阵:蒅0111000莂1001100螆1001010袇1110111薃0101001螂0011001蒇0001110蚄邻接表:蚁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_NODE规定。visit[i]数组用来表示顶点i是否被访问过。遍历前置visit各元素为0,若顶点i被访问过,则置visit[i]:,选择一个与v相邻接且未被访问过的的顶点w访问之,再从w开始进行深度优先搜索。每当到达一个其所有相邻接的顶点都被访问过的顶点,就从最后访问的顶点开始,依次退回到尚有邻接顶点未曾访问过的顶点u,并从u开始进行深度优先搜索。这个过程进行到所有顶点都被访问过,或从任何一个已访问过的顶点出发,再也无法到达未曾访问过的顶点,则搜索过程就结束。蒄另一方面,先建立一个相应的具有n个顶点,m条边的无向图的邻接表。初始化visit数组,使其各个元素置为0,表示图中每个顶点都没被访问过。膄下面给出程序:羁#include<>虿#defineMAXN50薆#defineMAXM100节typedefstructl_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]==0)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]