帮我写一个链式前向星的模板
时间: 2023-03-29 11:01:48 浏览: 77
好的,以下是链式前向星的模板:
```c++
const int MAXN = 100005;
const int MAXM = 200005;
int head[MAXN], ver[MAXM], nxt[MAXM], edge[MAXM], tot;
void add(int x, int y, int z) {
ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
void init() {
memset(head, , sizeof(head));
tot = ;
}
```
以上是链式前向星的模板,希望对你有所帮助。
相关问题
前向星和链式前向星区别
前向星和链式前向星的区别在于实现方式和数据结构的不同。
前向星是一种存储图的边的数据结构,它使用两个数组来存储边的信息。一个数组存储每个顶点的第一条边的索引,另一个数组存储每条边的下一条边的索引。这种方式可以方便地遍历每个顶点的所有边。
链式前向星是一种基于链表的存储方式,它使用链表来存储每个顶点的边。每个顶点都有一个指向第一条边的指针,每条边都有一个指向下一条边的指针。这种方式可以动态地添加和删除边。
总结来说,前向星使用数组存储边的信息,链式前向星使用链表存储边的信息。链式前向星相比前向星更加灵活,可以方便地进行边的插入和删除操作。但是链式前向星的空间复杂度较高,因为需要额外的指针来存储链表的连接关系。
引用\[1\]中提到,链式前向星的整体结构很像邻接表,但是实现方式不同。链式前向星的思想和邻接表一致,只是在实现上有所区别。因此,链式前向星的使用和邻接表相一致,可以用于存储和遍历图的边的信息。
#### 引用[.reference_title]
- *1* *2* *3* [链式前向星](https://blog.csdn.net/MuShan_bit/article/details/123882339)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^koosearch_v1,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]
帮我把以上代码改成用链式前向星的形式
好的,我将把给出的代码改成链式前向星的形式。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 501;
int head[MAXN], nxt[MAXN * MAXN], to[MAXN * MAXN], cnt;
double w[MAXN * MAXN];
int n, m, cnt[MAXN];
bool in[MAXN];
double d[MAXN];
void addEdge(int u, int v, double weight) {
nxt[cnt] = head[u];
to[cnt] = v;
w[cnt] = weight;
head[u] = cnt++;
}
bool spfa() {
memset(d, 0, sizeof(d));
memset(in, 0, sizeof(in));
memset(cnt, 0, sizeof(cnt));
queue<int> qu;
for (int i = 0; i < n; i++) {
qu.push(i);
in[i] = cnt[i] = 1;
}
while (!qu.empty()) {
int f = qu.front(), v;
qu.pop();
in[f] = false;
for (int i = head[f]; i != -1; i = nxt[i]) {
if (d[v = to[i]] < w[i] + d[f]) {
d[v] = w[i] + d[f];
if (!in[v]) {
in[v] = true;
cnt[v]++;
qu.push(v);
if (cnt[v] > n)
return true;
}
}
}
}
return false;
}
int main() {
memset(head, -1, sizeof(head));
for (int shuju = 1;; ++shuju) {
cin >> n;
if (!n)
return 0;
string x;
map<string, int> id;
for (int i = 0; i < n; ++i) {
cin >> x;
id[x] = i;
}
cin >> m;
int u, v;
double r;
for (int i = 0; i < m; i++) {
cin >> x >> r >> y;
u = id[x];
v = id[y];
addEdge(u, v, log(r));
}
cout << "Case " << shuju << ": ";
cout << (spfa() ? "Yes" : "No") << endl;
// 清除链式前向星中的边
memset(head, -1, sizeof(head));
cnt = 0;
}
return 0;
}
```
在这个修改后的代码中,我们定义了一个`head`数组来表示链式前向星的头节点数组。每个节点的边都通过`nxt`数组和`to`数组来表示。`cnt`变量用于记录边的数量。
`addEdge`函数用于向链式前向星中添加边。在建图的过程中,我们将起点和终点的编号以及权值传入该函数,然后将边的信息存储在相应的数组中。
在主函数中,我们首先将`head`数组初始化为-1,表示链式前向星中没有边。然后读入节点数n和节点名称,并使用一个map将节点名称映射到节点编号。接着读入边数m和每条边的起点、终点和权值。在建图时,我们调用`addEdge`函数将边的信息添加到链式前向星中。
最后,我们使用SPFA算法判断是否存在负环,并输出结果。在每次循环之后,我们清除链式前向星中的边,将`head`数组重新初始化为-1,并将`cnt`变量重置为0,以便下一次循环使用。
希望这个修改后的代码对您有帮助!如果还有其他问题,请随时提问。