企业官网建设流程全解析

网站和app开发,有的网站打不开是什么原因,齐鲁人才网泰安招聘,网页设计与制作项目教程题目背景给定一个包含 n 个点和 m 条边的无向图。点从 1 到 n 编号。请分别使用深度优先搜索 (DFS) 和 广度优先搜索 (BFS) 遍历该图#xff0c;并输出遍历序列。题目要求存储结构#xff1a;使用邻接表#xff08;链式前向星#xff09;存储图结构。遍历起点#xff1a;两…题目背景给定一个包含 n 个点和 m 条边的无向图。点从 1 到 n 编号。请分别使用深度优先搜索 (DFS) 和 广度优先搜索 (BFS) 遍历该图并输出遍历序列。题目要求存储结构使用邻接表链式前向星存储图结构。遍历起点两次遍历均从1号节点开始。邻居顺序在遍历每个节点的邻居时遵循链式前向星“头插法”的特性即输入顺序靠后的边在遍历时会优先访问。输出要求第一行输出 DFS 遍历序列。第二行输出 BFS 遍历序列。每个数字后面跟一个空格。输入格式第一行包含两个正整数 n 和 m表示点数和边数。接下来 m 行每行包含两个整数 u, v表示点 u 和点 v 之间有一条无向边。输出格式第一行DFS 遍历序列。第二行BFS 遍历序列。数据范围1n10001m2000样例输入8 9 1 2 1 3 2 4 2 5 4 8 5 8 3 6 3 7 6 7样例输出(注意链式前向星由于是头插法邻接点的顺序通常是输入顺序的倒序所以遍历结果可能与直觉从小到大不同但符合代码逻辑)1 3 7 6 2 5 8 4 1 3 2 7 6 5 4 8#include iostream #include cstring #include queue using namespace std; int h[2000]; int vtex[4000]; int nxt[4000]; int vis[2000]; int idx0; queueint q; void dfs(int x){ coutx ;//输出这个节点 int ph[x];//h[x]存的是x下一个相邻节点在vtex数组中的编号 vtex[p]的值就是相邻节点 while(p!-1){//如果指针指向的节点不为空 if(vis[vtex[p]]0){//如果相邻节点没走过就可以去走 vis[vtex[p]]1;//先标记为走过 dfs(vtex[p]);//然后从相邻节点继续往下走 } pnxt[p];//让指针变成指向链表的下一个指针 } } void bfs(int x){ q.push(x); while(!q.empty()){ int tmpq.front();//访问队首元素 couttmp ; q.pop();//删除队首 int ph[tmp]; while(p!-1){//如果指向下一个数的指针不为空 if(vis[vtex[p]]0){//如果下一个数没被访问过 q.push(vtex[p]);//入队 vis[vtex[p]]1;//标记为访问过 pnxt[p];//更新指针指向下一个数 } else pnxt[p];//如果被访问过更新指针指向下一个数 直到指向下一个数的指针为空 } } } void addedge(int a,int b){ vtex[idx]b; nxt[idx]h[a]; h[a]idx; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n,m;//点数 边数 cinnm; //先把图的邻接表建出来 memset(h,-1,sizeof(h));//初始化h数组 for(int i1;im;i){ int u,v; cinuv; addedge(u,v); addedge(v,u); } //图的深搜遍历 vis[1]1; dfs(1); coutendl; memset(vis,0,sizeof(vis));//进行完深搜再去进行广搜要对vis数组初始化 /*输出邻接表 for(int i1;in;i){ couti: ; int tmph[i]; while(tmp!-1){ coutvtex[tmp] ; tmpnxt[tmp]; } coutendl; } */ //图的广搜遍历 vis[1]1; bfs(1); return 0; }1. 为什么选择链式前向星在竞赛和工程中我们常用三种方式存图邻接矩阵O(N^2)空间太浪费稀疏图点多边少直接爆炸。Vector 邻接表动态扩容方便但有额外内存开销且 vector 的常数较大。链式前向星本质是静态数组模拟单链表。它内存连续、没有碎片、空间可控O(M)是处理大规模图论题的最优解。2. 核心原理内存里的“穿针引线”链式前向星由三个核心数组构成它们配合完成“由点找边”的任务h[u](Head)索引数组。存储节点 u 的最后一条被加入的边的编号即链表头。初始化必须为-1代表空链表。vtex[i](Vertex)数据数组。记录第 i 条边指向的终点节点。nxt[i](Next)指针数组。记录第 i 条边的下一条边的编号同起点的上一条加入的边。2.1 插入过程模拟头插法假设我们要给节点 1 添加两条边先加 1-2后加 1-5。idx 是边的计数器从 0 开始。初始状态h[1] -1加入边 1-2 (idx0)记录终点vtex[0] 2链接旧头nxt[0] h[1](即 -1)更新新头h[1] 0加入边 1-5 (idx1)记录终点vtex[1] 5链接旧头nxt[1] h[1](即 0)更新新头h[1] 1结果当我们遍历节点 1 时从 h[1] 开始先访问 idx1 (终点5)-顺着 nxt[1] 找 idx0 (终点2)-顺着 nxt[0] 找 -1 (结束)。结论这就是为什么链式前向星遍历顺序与输入顺序相反LIFO 后进先出。3. 无向图的“空间陷阱”无向图的一条边 u-v 在逻辑上等价于两条有向边 u-v 和 v-u。这意味着如果题目给出 m 条边我们实际调用的 addedge 次数是 2m。易错点vtex和nxt数组的大小必须开到2*M。后果如果不乘以 2存最后几条反向边时数组越界直接 Runtime Error。4. 搜索算法的关键细节DFS (递归实现的深度优先)机制利用系统栈进行回溯。要点vis数组用于剪枝。只要nxt指针没指到-1就通过vtex取出邻居判断是否访问过没访问过则递归。BFS (队列实现的广度优先)机制利用queue维护访问层级。法则标记必须在入队 (Push) 时进行正确Push - Mark。保证队列里不会有重复节点。错误Pop - Mark。会导致同一层级的节点将同一个邻居重复加入队列在稠密图中时间复杂度从 O(NM) 退化为指数级。5. 复杂度分析设点数为 N边数为 M无向图边数为 2M。空间复杂度O(N 2M)。由三个数组决定线性空间非常优秀。时间复杂度建图O(M)。DFS/BFSO(N 2M)。每个点访问一次每条边访问一次。总结这道题不仅是图论入门更是对指针操作和内存管理的一次降维打击训练。掌握了链式前向星就掌握了图论高性能实现的基石。