搜索
数据结构17_1对于图题7.1（P235）的无向图，给出：（1）表示该图的邻接矩阵。（2）表示该图的邻接表。（3）图中每个顶点的度。解：（1）邻接矩阵：0111000100110010010101110111010100100110010001110（2）邻接表：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，3，6，3，3，3。7_2对于图题7.1的无向图，给出：（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]为1.算法分析：首先访问出发顶点v.接着，选择一个与v相邻接且未被访问过的的顶点w访问之，再从w开始进行深度优先搜索。每当到达一个其所有相邻接的顶点都被访问过的顶点，就从最后访问的顶点开始，依次退回到尚有邻接顶点未曾访问过的顶点u,并从u开始进行深度优先搜索。数据结构2这个过程进行到所有顶点都被访问过，或从任何一个已访问过的顶点出发，再也无法到达未曾访问过的顶点，则搜索过程就结束。另一方面，先建立一个相应的具有n个顶点,m条边的无向图的邻接表。初始化visit数组，使其各个元素置为0，表示图中每个顶点都没被访问过。下面给出程序：#includestdio.h#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;im;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[])数据结构3{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].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,visit,1);printf(\n);}输出结果：1364257（1）BFS法：存储结构：本题采用邻接表作为图的存储结构，邻接表中的各个链表的结点形式由类型L_NODE规定，而各个链表的头指针存放在数组head中。数组e中的元素e[0],e[1],…..,e[m-1]给出图中的m条边，e中结点形式由类型E_NODE规定。visit[i]数组用来表示顶点i是否被访问过。遍历前置visit各元素为0，若顶点i被访问过,则置visit[i]为1.另外，使用一个队列QTYPE来存储已经访问过的顶点。算发分析：首先访问出发顶点v，然后访问与顶点v邻接的全部顶点w1,w2,…,wi,再依次访问与数据结构4w1,w2,…,wi,邻接的全部顶点（已访问的顶点除外），再从这些已访问的顶点出发，依次与它们邻接的全部顶点（已访问的顶点除外）。依次类推，直到图中或v所在的连通分量的所有顶点都被访问到为止，广度优先搜索结束。下面给出程序:#includestdio.h#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;im;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;}voidbfs(intu,L_NODE*head[],intvisit[])数据结构5{typedefstructqueuetype{intqa;intqe;intitem[MAXN];}QTYPE;intv,w;L_NODE*t;QTYPEqueue;printf(%4d,u);visit[u]=1;queue.qa=0;queue.qe=0;queue.item[0]=u;while(queue.qa=queue.qe){v=queue.item[queue.qa++];t=head[v];while(t!=NULL){w=t-ver;if(visit[w]==0){printf(%4d,w);visit[w]=1;queue.item[++queue.qe]=w;}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);数据结构6init(visit,7);bfs(1,head,visit);printf(\n);}输出结果：13426757_3对于图题7.3的有向图，给出：（1）表示该图的邻接矩阵。（2）表示该图的邻接表。（3）图中每个顶点的入度和出度。解：（1）邻接矩阵如下：0101000图题7.3000010010000000000110000000100100000000010(2)邻接表如下：123455^1^57^3^6^6^24^6735124数据结构767（4）设各顶点入度和出度分别为ri,ci:r1=1,c1=2r2=1,c2=1r3=1,c3=1r4=1,c4=2r5=2,c5=1r6=2,c6=1r7=1,c7=17_4对于图题7.3的有向图，给出：（1）从顶点1出发，按深度优先搜索法遍历图时的所得的顶点序列。（2）从顶点1出发，按广度优先搜索法遍历图时的所得的定点序列。解：（1）1－2－5－7－6－3－4（2）1－2－4－5－6－7－37_5对于图题7.1的无向图，试问它是（1）连通图吗？（2）完全图吗？1234567（1）该图是连通图。判断无向图是否为连通图，即判断该图中是否每对顶点之间都有路径。（2）该图不是完全图。判断无向图是否为完全图，即判断图中是否每对顶点之间都有边。7_6对于图题7.3的有向图，试问它是（1）弱连通图吗？（2）强连通图吗？12数据结构834567(1)该图是弱连通图。判断有向图是否为弱连通图，即需判断图中是否每对顶点v和w之间有一个由不同顶点组成的顶点序列（v0,v1,……vk），其中v0=v，vk=w，且（vi，vi+1）或（vi+1，vi）属于图的边集。(2)该图是强连通图。判断有向图是否为强连通图，即需判断图中是否每对顶点之间有一条路径。7_7图题7-7是有向图，试问其中哪个图是（1）弱连通的？（2）强连通的？(a)(b)[解]（1）(b)图是弱连通的。（2）(a)图是强连通的。7_8具有N个顶点的连通无向图至少有几条边？[解]具有N个顶点的连通无向图至少应有N—1条边。7_9具有N个顶点的强连通有向图至少有几条边？2N条边。7_10分别写出用深度和广度优先搜索法遍历具有六个顶点的完全无向图的顶点序列。（假设都以顶点1出发）。深度优先：1，2，3，4，5，6广度优先：1，2，3，4，5，612434321数据结构97_11题目：改写以深度优先搜索法遍历给定的连通图的dfs程序，要求不用递归方法，而用一个栈来实现。算法分析：用栈保存由结点V出发可到达的结点，并作上标记，以使下次遇到时不会重复输出。当一路结点访问完后，向前回溯（利用出栈）并访问其他结点，直到所有结点均已遍历。程序的流程：结点进栈结点出栈访问并标记结点相联结点进栈……。