图, 图的遍历
原创
图, 图的遍历
原创
关于数据结构与算法的学习其实主要分为两个方面,一方面就是我们可以动手实现某种数据结构,比如说链表的增删改查,这对于我们日常开发工作很有用的. 特别当如果后边如果要做开源项目其实对已有的数据结构进行封装都是很重要的,另一个就是算法的学习,这部分其实我们日常开发基本用不上,这方面学习我的建议是有余力就去学习,毕竟体会各种牛逼的代码也是对于程序员也很有意义.
图
图对于我们日常的生活来说其实更加普遍,我们日常的生活大多就是不规则的,不会像树一样那样结构紧密,我们日常生活更多接触就是图.
图的表示
图的表示一般有两种方式,一种是二维数组,例如在 (x, y) 的点表示 x, y之间的距离,或者权重.当然这种用来表示图对于空间产生了很大的浪费, 一方面因为 (x, y) 和 ( y, x) 一样的值没有必要表示两次, 另一方面就是(x, x) 的值必然为 0.,另外两个点之间如果没有连接,我们完全可以不用表示. 因此有了第二种表示方式邻接表.
邻接表是数组和链表的组合, 有点类似 hashmap, 具体见下图
我们可以吧所有点都当做数组的一项.链表内容表示这个节点有连接的其他节点,节点中可以存放相关的权重值.
图的遍历
图的遍历可以分为两种,一种是深度遍历,一种是广度遍历,也就是常说的深搜和广搜.我们首先用邻接表实现图,另外为了简单我们使用无向图表示.
class Graph {
private:
int v; //表示顶点的数目
vector<vector<int>> graph;
public:
Graph(int v){
v = v;
graph.resize(v);
}
void addEdge(int src, int dest){
graph[src].push_back(dest);
graph[dest].push_back(src);
}
};接下来就是图的遍历,分别是深度遍历和广度遍历.
广搜
广搜的跟树的层序遍历基本一致,就是需要使用另外一个数据用来标记是否访问过.
void bfs(int start){
vector<bool> visited(v, false);
queue<int> q;
q.push(start);
visited[start] = true;
while(!q.empty()){
int index = q.pop();
cout<<index<<endl;
for(int adj : graph[index]){
if(!visited[adj]){
visited[adj] = true;
q.push(adj);
}
}
}
}深搜
void dfs(int start){
vector<bool> visited(v, false);
dfsIncrement(visited, start);
}
void dfsIncrement(vector<bool> &visited, int start){
visited[start] = true;
cout<< start<< endl;
for(int adj : graph[start]){
if(!visited[adj]){
dfsIncrement(visited, adj);
}
}
}深搜和广搜都比较简单,是很多算法基础,我们在很多场景都回用到.这里只是简单场景后边几篇我们实现几个数据结构的操作.
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
