使用存储图结构的邻接表的创建算法 设计算法实现 基础项目: <1>设计算法实现图的深度优先遍历。(递归或非递归算法均可) <2>设计算法实现图的广度优先遍历。(递归或非递归算法均可) <3>求顶点的度(入度或出度)。 <4>设计算法实现AOV网的拓扑排序,输出拓扑序列。 拓展项目: <5>使用普瑞姆算法求最小生成树。
时间: 2024-02-25 21:51:33 浏览: 28
好的,我会为您解答。
1. 图的深度优先遍历
使用邻接表存储图,深度优先遍历可以使用递归或非递归算法实现。以下是递归实现的代码:
```c++
void DFS(int v, bool visited[]) {
visited[v] = true;
cout << v << " ";
for (auto i = adj_list[v].begin(); i != adj_list[v].end(); ++i) {
if (!visited[*i])
DFS(*i, visited);
}
}
```
其中,`v`是当前访问的顶点,`visited[]`记录顶点是否访问过。
2. 图的广度优先遍历
使用邻接表存储图,广度优先遍历可以使用递归或非递归算法实现。以下是非递归实现的代码:
```c++
void BFS(int s) {
bool visited[V];
memset(visited, false, sizeof(visited));
queue<int> q;
visited[s] = true;
q.push(s);
while (!q.empty()) {
int v = q.front();
cout << v << " ";
q.pop();
for (auto i = adj_list[v].begin(); i != adj_list[v].end(); ++i) {
if (!visited[*i]) {
visited[*i] = true;
q.push(*i);
}
}
}
}
```
其中,`s`是起始顶点,`visited[]`记录顶点是否访问过,`q`是保存待访问顶点的队列。
3. 求顶点的度
顶点的度是指与该顶点相邻的边的数目。对于有向图,顶点的入度是指指向该顶点的边的数目,出度是指从该顶点出发的边的数目。以下是求顶点度的代码:
```c++
int get_degree(int v, bool is_indegree) {
int degree = 0;
for (int i = 0; i < V; ++i) {
for (auto j = adj_list[i].begin(); j != adj_list[i].end(); ++j) {
if (*j == v) {
degree++;
}
}
}
if (!is_indegree) {
degree = adj_list[v].size();
}
return degree;
}
```
其中,`v`是要求度的顶点,`is_indegree`表示求入度还是出度。
4. AOV网的拓扑排序
AOV网是指只有有向边没有环的有向图。在AOV网中,拓扑排序可以得到一种满足所有有向边从前往后的顺序。以下是拓扑排序的代码:
```c++
void topological_sort() {
vector<int> in_degree(V, 0);
for (int i = 0; i < V; ++i) {
for (auto j = adj_list[i].begin(); j != adj_list[i].end(); ++j) {
in_degree[*j]++;
}
}
queue<int> q;
for (int i = 0; i < V; ++i) {
if (in_degree[i] == 0) {
q.push(i);
}
}
int count = 0;
vector<int> top_order;
while (!q.empty()) {
int u = q.front();
q.pop();
top_order.push_back(u);
for (auto i = adj_list[u].begin(); i != adj_list[u].end(); ++i) {
if (--in_degree[*i] == 0) {
q.push(*i);
}
}
count++;
}
if (count != V) {
cout << "Graph contains a cycle" << endl;
return;
}
for (auto i = top_order.begin(); i != top_order.end(); ++i) {
cout << *i << " ";
}
}
```
其中,`in_degree`记录每个顶点的入度。
5. 普瑞姆算法求最小生成树
普瑞姆算法是一种贪心算法,用于求加权连通图的最小生成树。以下是普瑞姆算法的代码:
```c++
int prim_mst() {
priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > pq;
vector<int> key(V, INT_MAX);
vector<bool> in_mst(V, false);
int src = 0;
int mst_cost = 0;
pq.push(make_pair(0, src));
key[src] = 0;
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
in_mst[u] = true;
for (auto i = adj_list[u].begin(); i != adj_list[u].end(); ++i) {
int v = (*i).first;
int weight = (*i).second;
if (in_mst[v] == false && key[v] > weight) {
key[v] = weight;
pq.push(make_pair(key[v], v));
}
}
}
for (int i = 1; i < V; ++i) {
mst_cost += key[i];
}
return mst_cost;
}
```
其中,`pq`是保存顶点和权重的最小堆,`key`是保存顶点与已包含的顶点之间的最小权重,`in_mst`记录顶点是否在最小生成树中。