本篇文章给大家讲解关于图的五种存储方式与其对应的DFS遍历方式。传送门邻接矩阵建图遍历边集数组建图遍历邻接表建图遍历链式邻接表建图遍历链式前向星建图遍历邻接矩阵邻接矩阵使用二维数组是最简单直接容易理解的存储方式适用于稠密图以及节点数较小的图。它的时间复杂度为平方级按照行列顺序访问。二维数组大小为n*n邻接矩阵 a[i][j] 则表示从 i 到 j 有没有边。建图constintN110;intmain(){intn,m,a[N][N];//n节点数m边数a邻接矩阵cinnm;for(inti1;im;i){intu,v,w;//起点终点边权值cinuvw;a[u][v]w;//若无权值标记1表示有边即可//a[v][u]w; 若为无向图需要反向再存一条边}return0;}遍历intdfs(intu){vis[u]1;//标记当前节点已经访问过了for(inti1;in;i)//按顶点一个个找{if(a[u][i]!0)//点u到点i之间有边{//输出路径coutu-i;//couta[u][i]; 有权值的情况coutendl;}if(vis[i]0)//如果点i还没有访问过则先去找它{dfs(i);}}return0;}边集数组只记录边的信息应用不多。适用于稀疏图以及边较少的图。建图constintM110;//M代表边structnode{intu,v,w;//该边的起点终点权值}e[M];//e是边集数组intmain(){intm;//边数cinm;for(inti1;im;i){intu,v,w;//起点终点权值e[i]{u,v,w};//建图}return0;}遍历intdfs(intu){vis[u]1;//标记当前节点已经访问过了for(inti1;im;i)//找哪条边的起点为u{if(e[i].uu){//输出路径intve[i].v,we[i].w;coutu-v;//cout w; 有权值的情况coutendl;if(vis[v]0)//如果该边的中点还没有访问过则先去找它{dfs(v);}}}return0;}邻接表用动态数组vector记录每个点所有的出边信息。适用于所有的图与算法。建图constintN110;structnode{intv,w;};vectornodee[N];//如果带权就用结构体类型不带权直接定义int类型即可intmain(){intn,m;//节点数边数cinnm;for(inti1;im;i){intu,v,w;cinuvw;e[u].push_back({v,w});//e[v].push_back({u,w}); 无向图需要反向再存一遍}return0;}遍历intdfs(intu,intfa)//当前节点和前驱节点{for(inti0;ie[u].size();i)//找当前点的所有出边{intve[u][i].v,we[u][i].w;if(vfa){continue;}//输出路径coutu-v;//cout w; 有权值的情况coutendl;dfs(v,u);}return0;}链式邻接表能处理各种图与反向边。边集数组e[j]存储第j条边的起点、终点和权值用结构体表头数组h[u][i]存储顶点u的所有出边的编号建图constintN110;//N代表点structnode{intu,v,w;//起点终点权值};vectornodee;vectorinth[N];intmain(){intm;//边数cinm;for(inti1;im;i){intu,v,w;cinuvw;e.push({u,v,w});h[u].push_back(e.size()-1);/*无向图还需反向建一次边 e.push({v,u,w}); h[v].push_back(e.size()-1); */}return0;}遍历intdfs(intu,intfa)//当前节点和前驱节点{for(inti0;ih[u].size();i)//循环找u的所有出边编号{intjh[u][i];//编号为j的这条边是从节点u出发的intve[j].v,we[j].wif(vfa)//不往回找{continue;}//路径输出coutu-v;//带权输出权值 coutw;coutendl;dfs(v,u);}return0;}链式前向星一个表头数组悬挂多个链表可以处理各种图与反向边应用范围广。边集数组e[i]存储第i条出边的终点、权值与下一条边的编号。用结构体表头数组h[u]存储节点u的第一条出边的编号。建图constintN110,M110;//N代表点M代表边structnode{intv,w,nxt;//终点权值下一条边的编号}e[M];//边集数组inth[N],cnt;//表头数组边的编号intadd(intu,intv,intw)//链式前向星建图{e[cnt].vv;//当前边的终点e[cnt].ww;//当前边的权值e[cnt].nxth[u];//当前边的下一条边存为当前起点的前一条出边h[u]cnt;//更新出边cnt;//编号更新return0;}intmain(){memset(h,-1,sizeof(h));//便于遍历intm;//边数cinm;for(inti1;im;i){intu,v,w;cinuvw;add(u,v,w);//无向图须反向建边 add(v,u,w);}return0;}遍历intdfs(intu,intfa)//当前节点和前驱节点{//在主函数内给表头数组hmemset成-1for(intih[u];i!-1;ie[i].nxt)//从节点u的第一条出边开始找它存在边集数组e里的所有出边其实是倒序找到-1就表示找完了{intve[i].v,we[i].w;if(vfa)//不往回找{continue;}//输出路径coutu-v;//带权值的情况 coutw;coutendl;dfs(v,u);}return0;}谢谢观看不明白的同学可以私信或评论。