企业网站建设顾问,wordpress如何用API采集,做服装网站要那些照片,html编辑器哪个好用一、存图
存图方式一共有三种#xff1a;邻接矩阵、邻接表、前向星 纯前向星还需要再加上排序的时间复杂度#xff08;当排序不是主要复杂度时适用#xff09;#xff0c;如果快排#xff0c;时间复杂度是O(n log n)#xff0c;可以用别的排序方式优化#xff0c;即基数…一、存图
存图方式一共有三种邻接矩阵、邻接表、前向星 纯前向星还需要再加上排序的时间复杂度当排序不是主要复杂度时适用如果快排时间复杂度是O(n log n)可以用别的排序方式优化即基数排序不写纯前向星了不会写基数排序 事实上不用排序也能模仿出来前向星的核心思路即链式前向星链式前向星也是最常用的存图方式
邻接矩阵
int edge[100][100],vis[100],m,n;
void add_edge(int u,int v,int w) //添加边
{edge[u][v]w;
}
void dfs(int x) //遍历
{vis[x]1;coutx;for(int i1;in;i){if(edge[x][i]!vis[i]){cout-;dfs(i);}}
}
int main()
{cinnm;for(int i1;im;i){int u,v,w;cinuvw;add_edge(u,v,w);add_edge(v,u,w);}dfs(1);return 0;
}/*
test4 5
1 2 5
1 3 8
1 4 7
2 3 6
3 4 9*/邻接表链式前向星
int n,m,cnt,head[100],vis[100];
struct edge{int nxt,to,w;
}e[100];
void add_edge(int u,int v,int w)
{e[cnt] (edge){head[u],v,w};head[u] cnt;
}
void dfs(int x)
{coutx;vis[x]1;for(int ihead[x];i;ie[i].nxt){if(!vis[e[i].to]){cout-;dfs(e[i].to);}}
}
int main()
{cinnm;for(int i1;im;i){int u,v,w;cinuvw;add_edge(u,v,w);add_edge(v,u,w);}dfs(1);return 0;
}邻接表vector存边
vectorpairint,int e[100];
int n,m,vis[100];
void add_edge(int u,int v,int w) //存边
{e[u].push_back(make_pair(v,w));
}
void dfs(int x) //遍历
{coutx;vis[x]1;for(int i0;ie[x].size();i){if(!vis[e[x][i].first]){cout-;dfs(e[x][i].first);}}
}
int main()
{cinnm;for(int i1;im;i){int u,v,w;cinuvw;add_edge(u,v,w);add_edge(v,u,w);}dfs(1);return 0;
}二、遍历
由于邻接表使用广泛因此以邻接表为例说明图的遍历
1.DFS遍历
DFSDepth First Search维护一个栈每次从栈中取出点/放入点以栈的出栈顺序遍历图 对于栈的使用可以利用天然的递归栈 递归形式 也可以手写栈 递推形式
DFS递归形式
void dfs(int x)
{coutx;vis[x]1;for(int ihead[x];i;ie[i].nxt){if(!vis[e[i].to]){cout-;dfs(e[i].to);}}
}DFS非递归形式
void dfs(int x)
{stackint order; //原先天然的递归栈用手写栈代替order.push(x);vis[x]1;while(!order.empty()){xorder.top();order.pop();coutx-;for(int ihead[x];i;ie[i].nxt){if(!vis[e[i].to]){vis[e[i].to]1;order.push(e[i].to);}}}
}2. BFS遍历
BFSBreadth First Search维护一个队列每次从队列中取出点/放入点以队列的出队顺序遍历图
void bfs(int x)
{queueint order;order.push(x);vis[x]1;while(!order.empty()){xorder.front();coutx ;order.pop();for(int ihead[x];i;ie[i].nxt){if(!vis[e[i].to]){vis[e[i].to]1;order.push(e[i].to);}}}
}对于BFS因为是 “广度优先” 可以用于最短路径算法具体请移步我的下一篇博客
