//图论复习
const int N = 100, M = 2 * N;
//树和无权图的存储
int h[N], e[M], ne[M], idx; //前插法建立链表
void add(int a, int b) { //添加一条a->b的无权边
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
//树和无权图的dfs
bool vis[N];//全局数组默认值为0
void dfs(int u) {
vis[u] = true; //只遍历一遍
//遍历边
for (int i = h[a]; i != -1; i = ne[i]) {
int j = e[i] //取顶点,i代表的是下标
dfs(j);
}
}
//广度优先遍历
queue<int> q;
void bfs(int u) {
q.push(u);
vis[u] = true;
int x;
while (q.size()) {
x = q.front();
q.pop();
for (int i = h[x]; i != -1; i = ne[i]) {
int j = e[i];
if (!vis[j]) {
vis[j] = true; //标记为访问过
q.push(j);
}
}
}
}
//拓扑排序
//数组模拟队列
int que[N], hh = 0, tt = -1; //hh 是队头 tt 是队尾
//队列有 front size empty push pop 操作
//向队尾插入一个数
q[++tt] = x; //x为插入的元素
hh++;//队首出去
q[hh];//队首的值
int size = tt - hh + 1; //个数
//判断是否为空 队列中是否含有元素
if (hh <= tt) {
}
//数组模拟栈
int sta[N], tt = 0;
sta[++tt] = x //x是压入栈的元素
sta[tt];//栈顶的值
tt--;//弹出栈
//判断栈是否为空
if (tt > 0) {
}
int d[N];//存放入度
bool topsort() { //判断是否存在拓扑序列(图中是否有环)
//模拟队列
int hh = 0, tt = -1, q[N];
//找到入度为0的点 删去顶点其所有的边,重复此过程
for (int i = 1; i <= n; i++)
if (!d[i])
q[++tt] = i;
while (hh <= tt) { //队列不为空
int t = q[hh++]; //取队列首元素,并且队首出去
//删除所有顶点
for (int i = h[t]; i != -1; i = ne[i]) { //i为顶点的下标
int j = e[i]; //取出边
if (--d[j] == 0) //删除点并且判断度是否为0,重复
q[++tt] = j;
}
}
// 如果所有点都入队了,说明存在拓扑序列;否则不存在拓扑序列。
return tt == n - 1;
}
//有权图
W[M];//区别在于多了个权值
void add(int a, int b, int c) { //多了c为权值
e[idx] = b;
ne[idx] = h[a];
W[idx] = c;
h[a] = idx++;
}
//基本跟无权图一样
//最小生成树
//要使用并查集,防止产生环
int ds[N];//并查集数组
int n, m; //n为顶点数,m为边数
//边集结构体
struct edge {
int a, b, w;
//小于运算符重载
bool operator <(const edge &x)const {
return w < x.w;
}
} eg[N];
bool vis[N];
int find(int x) { //查找父节点
if (ds[x] != x)
ds[x] = find(ds[x]); //优化
return ds[x];
}
int kruskal() {
//思想:贪心,贪边,每次扩展最小权值的边,要判断是否产生环直到遍及整个图
sort(eg, eg + m); //边排序
//初始化并查集
for (int i = 0; i < n; i++)
ds[i] = i;
int res = 0, cnt = 0; //res为生成树代价,cnt为连接顶点数
for (int i = 0; i < m; i++) {
//获取边的信息
int a = eg[i].a, b = eg[i].b, w = eg[i].w;
a = find(a), b = find(b);
if (a != b) { //防止产生环
ds[a] = b;
res += w;
cnt++;
}
}
//判断是否成功
if (cnt < n - 1)
return -1;
return res;
}
typedef pair<int, int> PII;
#define x first
#define y second
//最短路径
int dist[N];//存储该点到其他点的距离
bool st[N]; //判断该点到其他点的距离是否确定
int dijkstra() {
//前提性质:最短路径的任何连续子序列都为最短路径
//算法思想: 确定入选边集,找到最小边,对已经入选边的顶点,更新入选边集
//重复此过程
memset(dist, 0x3f, sizeof dist); //设置距离为无穷
dist[1] = 0; //到自己的距离为0
//堆申请
priority_queue<PII, vector<PII>, greater<PII>> heap; //PII默认参数
heap.push({0, 1}); //first为存储距离,second 为点的编号
//更新入选边集
while (heap.size()) {
auto t = heap.top();
int distance = t.x, ver = t.y; //提取编号和距离
if (st[ver])
continue;//如果该点最短距离已经确定,跳出
st[ver] = true;
//正式更新边集
for (int i = h[ver]; i != -1; i = ne[i]) { //读取边正常操作,i为顶点下标
int j = e[i];
//判断是否更新
if (dist[j] > distance + w[i]) {
dist[j] = distance + w[i];
//堆只能删除堆顶的元素
heap.push({dist[j], j});
}
}
}
if (dist[N] == 0x3f)
return -1;
else
return dist[N];
}
//二维数组存
int g[N][N];
bool vis[N];
//深度优先遍历
void dfs(int u) {
vis[u] = true;
for (int i = 0; i < n; i++)
if (g[u][i] && !vis[i])
dfs(i);
}
//广度优先遍历
void bfs(int u) {
queue<int> q;
q.push(u);
vis[u] = true;
while (q.size()) {
int t = q.front();
q.pop();
for (int i = 0; i < n; i++)
if (g[u][i] && !vis[i]) {
vis[i] = true;
q.push(i);
}
}
}
//拓扑排序
bool topsort() {
//模拟队列
int q[N], hh = 0, tt = -1;
//找到度为0的结点
for (int i = 0; i < n; i++)
if (!d[i])
q[++tt] = i;
//删除相关边,再重复
while (hh <= tt) {
//出队列
int t = q[hh++];
for (int i = 0; i < n; i++)
if (g[t][i])
if (--d[i] == 0)
q[++tt] = i;
}
}
int main() {
//图的初始化
idx = 0;
memset(h, -1, sizeof(h)); //邻接表和二维数组都一样 memset(g,-1,sizeof(g));
return 0;
}