数据结构与算法
1-基本数据结构
2-分治策略
3-堆
4-排序
5-选择 & 树
6-搜索树 & 散列表 & 并查集
6.1-搜索树
6.2-散列表
6.3-并查集
int find(int x)
{
if(pre[x] == x) return x;
return pre[x] = find(pre[x]);
}
void join(int x,int y)
{
int fx=find(x), fy=find(y);
if(fx != fy)
pre[fx]=fy;
}
7-图
7.1-BFS(邻接表)
vector<vector<int>> graph; // 图的邻接表表示
vector<int> color; // 访问标记数组
void BFS(int start)
{
queue<int> q; // BFS队列
q.push(start); // 将起始节点加入队列
color[start] = 1; // 标记起始节点为已访问
while (!q.empty())
{
int current = q.front(); // 取出队列的第一个元素
q.pop(); // 将该元素从队列中移除
color[current] = 2;
// 遍历当前节点的所有邻接节点
for (auto &neighbour:graph[current])
{
color[neighbour] = 1;
q.push(neighbour);
}
}
}
7.2-DFS(邻接表)
vector<vector<int>> graph; // 图的邻接表表示
vector<int> color; // 访问标记数组
void DFS(int node)
{
color[node] = 1;
for (auto &neighbour : graph[node])
{
if (color[neighbour]==0)
{
DFS(neighbour);
}
}
color[node] = 2;
}
8-深度优先算法&生成树
- DAG：有向无环图
- (S)CC：(强)连通图
- MST：最小生成树
8.1-Topological Sort(DAG)
int V; //顶点个数
vector<vector<int>> graph;
vector<int> indegree;
queue<int> q; // 维护一个入度为0的顶点的集合
bool topological_sort()
{
for(int i=0; i<V; ++i)
if(indegree[i] == 0)
q.push(i); // 将所有入度为0的顶点入队
int count = 0; // 计数，记录当前已经输出的顶点数
while(!q.empty())
{
int current = q.front(); // 从队列中取出一个顶点
q.pop();
cout << current << " "; // 输出该顶点
count++;
// 将所有current指向的顶点的入度减1，并将入度减为0的顶点入栈
for(auto &node:graph[current])
{
indegree[node]--;
if(indegree[node]==0)
q.push(node);
}
}
if(count < V)
return false; // 没有输出全部顶点，有向图中有回路
else
return true; // 拓扑排序成功
}
8.2-Minimum Spanning Trees
8.2.1-Kruskal算法
int V; //顶点个数
int parent[MAX]; //定义parent数组用来判断边与边是否形成环路
struct Edge
{
int u,v,w;
};
vector<Edge> edges;
bool cmp(Edge a,Edge b)
{
return a.w < b.w;
}
int Find(int x)
{
return parent[x]==x ? x : parent[x] = find(parent[x])''
}
void Kruskal()
{
sort(edges.begin(),edges.end(),cmp); //把图中的所有边按代价从小到大排序
for(int i=0;i<V;i++) //把图中的n个顶点看成独立的n棵树组成的森林
parent[i] = i;
for(int i=0;i<edges.size();i++)
{
int u=edges[i].u,v=edges[i].v;
if(Find(u)!=Find(v)) //如果Find(u)=Find(v)，则形成环路
//将此边的结尾顶点放入下标为起点的parent数组中，表示此顶点已经在生成树集合中
parent[Find(u)] = Find(v);
}
}
8.2.2-Prim算法
#define inf INT_MAX
int n; //顶点个数
int res; //结果
vector<vector<int>> ma(n+1,vector<int>(n+1,inf)); //邻接矩阵，存边权，初始化为正无穷
vector<int> dist(n+1,0); //dist[]储存到生成树的距离
vector<bool> book(n+1,false); //用book数组记录某个点是否加入到生成树中
void prim()
{
dist[1] = 0;
book[1] = true;
for(int i = 2; i <= n; i++)
dist[i] = min(dist[i],ma[1][i]);//用点1去更新dist[]
for(int i = 2; i <= n; i++)
{
int temp = INF;//初始化距离
int t = -1; //接下来去寻找离生成树点集最近的点加入到集合中，用t记录这个点的下标。
for(int j = 2 ; j <= n; j++)
{
if(!book[j] && dist[j]<temp)
{
temp = dist[j];
t = j;
}
}
//如果t==-1，意味着在集合V找不到边连向集合S，生成树构建失败，将res赋值正无穷表示构建失败
if(t==-1)
{
res = INF;
return;
}
book[t] = true;//如果找到了这个点，就把它加入集合S
res += dist[t];//加上这个点到集合S的距离
for(int j = 2 ; j <= n ; j++)
dist[j] = min(dist[j],g[t][j]);//用新加入的点更新dist[]
}
8.2.3-Borůvka算法
int N,M;//N:点个数，M:边条数
struct Edge
{
int u,v,w;
}
vector<Edge> edges;
vector<bool> visited(M+1,0);
vector<int> parent(N+1,0),dist(M+1,0),e(M+1,0);
int find(int x)
{
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
bool cmp(Edge a,Edge b)
{
return a.w < b.w;
}
int boruvka()
{
int cnt = 0,sum = 0;
for(int i = 1;i <= N; i++)
parent[i] = i;
while (1)
{
int cnt_tmp=0;
memset(dist,inf,sizeof(dist)); //初始化dist数组
for (int i = 1; i <= M; i++) //每个边都计算一下dist
{
int f1 = find(edges[i].u),f2 = find(edges[i].v);//用并查集找到根
if (f1 == f2 || visited[i]) //如果一棵树或者拓展过这个边
continue;
cnt_tmp++; //记录一下看下有没有边可以拓展
if (edges[i].w < d[f1])
dist[f1] = edges[i].w,e[f1] = i; //更新，e数组表示dist数组对应的边
if (edges[i].w < d[f2])
dist[f2] = edges[i].w,e[f2] = i;
}
if (cnt_tmp == 0 || cnt == n - 1)
break;
for (int i = 1; i <= N; i++) //扫描每棵树
{
int f1 = find(edges[e[i]].u),f2 = find(edges[e[i]].v);
if(dist[i] == inf || f1 == f2 || visited[e[i]])
continue;
visited[e[i]] = 1; //加入最小生成树集合
parent[f1] = f2;
sum += edges[e[i]].w;
cnt++;
}
}
}
9-贪心
略
10-最短路
10.1-Floyd算法
int N; //顶点个数
vector<vector<int>> ma;//邻接矩阵，存储i到j的边权
void Floyd()
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
for (int k = 0; k < N; k++)
{
if (ma[j][k] > ma[j][i] + ma[i][k]) //若j到k间存在更短的通路，则更新
ma[j][k] = ma[j][i] + ma[i][k];
}
}
}
}
10.2-Dijkstra算法
#define inf INT_MAX
int N; //顶点个数
vector<vector<int>> ma(N+1,vector<int>(N+1,inf));//邻接矩阵，存储i到j的边权
vector<int> dist(N+1,0),finished(N+1,0);
void Dijkstra(int start,int end)
{
int min,k;
finished[s] = 1,dist[s] = 0;
for (int i = 1; i <= N; i++)
{
ma[i][i] = 0;
dis[i] = ma[s][i];
}
for (int i = 1; i <= N; i++)
{
if (i != s)
{
min = inf;
for (int j = 1; j <= N; j++)
{
if (flag[j] == 0 && dis[j] < min)
{
min = dist[j];
k = j;
}
}
flag[k] = 1;
if (k == t)
break;
for (int j = 1; j <= N; j++)
{
int tmp = (ma[k][j] == inf ? inf : (min + ma[k][j]));
if (finished[j] == 0 && tmp < dist[j])
dist[j] = tmp;
}
}
}
}
10.3-Bellman-Ford算法
//用于判断图中是否存在负权环
#define inf INT_MAX
int N,M;//N:顶点个数,M:边条数
struct Edge
{
int u, v, w;
};
vector<Edge> edges(M+1);
vector<int> dist(N+1,inf);
bool Bellman-Ford()
{
for (int i = 1; i <= N; i++) //将dist数组更新一次，存储i节点所在环的权
{
for (int j = 1; j <= M; j++)
{
int u = edges[j].u, v = edges[j].v, w = edges[j].w;
if (dist[v] > dist[u] + w)
dist[v] = dist[u] + w;
}
}
for (int i = 1; i <= M; i++) //再次更新dist数组，若权值改变，则图中存在负权环
{
if (dis[edges[i].v] > dis[edges[i].u] + edges[i].w)
return 1;
}
return 0;
}
11-动态规划
略
标签：dist,parent,int,算法,vector,ma,20241225,大二 From： https://www.cnblogs.com/landboat/p/18631441