本文最后更新于 710 天前，其中的信息可能已经有所发展或是发生改变。
建立所给 无向带权图 的 邻接矩阵存储 并输出该矩阵
/*
* @Author: Vastsea(lyx8851@qq.com)
* @Date: 2023-05-31 11:58:17
* @LastEditors: Vastsea(lyx8851@qq.com)
* @LastEditTime: 2023-06-05 08:45:08
* @FilePath: \Development\Cpp\3_SecondSemesterCollege\Experiment\InClass_Experiment_2\1_邻接矩阵.cpp
* @Description: 建立所给 无向带权图 的 邻接矩阵存储
* 并输出该矩阵
* Link:https://59888888.xyz/
* Phone:18893558104
*/
#include <iostream>
using namespace std;
#define MAXN 100
int G[MAXN][MAXN];
int n, m,u, v, w;
int main()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
G[i][j] = 0;
}
}
cout<<"请输入节点数和边数"<<endl;
cin >> n >> m;
cout<<"请依次输入边的起点、终点和权值"<<endl;
for (int i = 0; i < m; i++)
{
cin >> u >> v >> w;
G[u][v] = G[v][u] = w;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << G[i][j] << " ";
}
cout << endl;
}
return 0;
}建立所给无向图的邻接表 并输出该图的深度和广度优先遍历结果
这个写的好像有些问题，再看吧
/*
* @Author: Vastsea(lyx8851@qq.com)
* @Date: 2023-05-31 11:58:43
* @LastEditors: Vastsea(lyx8851@qq.com)
* @LastEditTime: 2023-06-05 09:47:53
* @FilePath: \Development\Cpp\3_SecondSemesterCollege\Experiment\InClass_Experiment_2\2_邻接表.cpp
* @Description: 建立所给无向图的邻接表
* 并输出该图的深度和广度优先遍历结果
* Link:https://59888888.xyz/
* Phone:18893558104
*/
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
typedef int ElemType;
struct ArcNode
{
int adjvex;
struct ArcNode *next;
};
struct VertexNode
{
ElemType vertex;
ArcNode *firstedge;
};
struct Graph
{
VertexNode vertex[100];
int n, m;
};
// 用邻接表创建一个无向图
void createGraph(Graph &G)
{
cout << "请输入节点数和边数" << endl;
cin >> G.n >> G.m;
cout << "将对点进行顺序编号" << endl;
for (int i = 0; i < G.n; i++)
{
G.vertex[i].vertex = i+1;
G.vertex[i].firstedge = NULL;
}
cout << "请依次输入边" << endl;
for (int i = 0; i < G.m; i++)
{
int u, v;
cin >> u >> v;
ArcNode *p = new ArcNode;
p->adjvex = v-1;
p->next = G.vertex[u-1].firstedge;
G.vertex[u-1].firstedge = p;
p = new ArcNode;
p->adjvex = u-1;
p->next = G.vertex[v-1].firstedge;
G.vertex[v-1].firstedge = p;
}
}
void DFS(Graph G, int v, bool visited[])
{
visited[v] = true;
cout << v+1 << " ";
ArcNode *p = G.vertex[v].firstedge;
while (p)
{
int w = p->adjvex;
if (!visited[w])
{
DFS(G, w, visited);
}
p = p->next;
}
}
void BFS(Graph G, int v, bool visited[])
{
queue<int> q;
q.push(v);
visited[v] = true;
while (!q.empty())
{
int u = q.front();
q.pop();
cout << u+1 << " ";
ArcNode *p = G.vertex[u].firstedge;
while (p)
{
int w = p->adjvex;
if (!visited[w])
{
visited[w] = true;
q.push(w);
}
p = p->next;
}
}
}
int main()
{
Graph G;
createGraph(G);
bool visited[100] = { false };
cout<<"深度优先遍历结果为:";
for (int i = 0; i < G.n; i++)
{
if (!visited[i])
{
DFS(G, i, visited);
}
}
cout << endl;
cout<<"广度优先遍历结果为:";
for (int i = 0; i < G.n; i++)
{
visited[i] = false;
}
for (int i = 0; i < G.n; i++)
{
if (!visited[i])
{
BFS(G, i, visited);
}
}
cout << endl;
return 0;
}以无向网表示n个城市之间通信网络的建设计划 顶点表示城市 边上的权表示该线路的造价
设计一个方案，使这个通信网的总造价最低
转，略有修改，原文链接
/*
* @Author: Vastsea(lyx8851@qq.com)
* @Date: 2023-05-31 11:59:11
* @LastEditors: Vastsea(lyx8851@qq.com)
* @LastEditTime: 2023-06-05 13:53:44
* @FilePath: \Development\Cpp\3_SecondSemesterCollege\Experiment\InClass_Experiment_2\3_通信网络建设.cpp
* @Description: 以无向网表示n个城市之间通信网络的建设计划
* 顶点表示城市
* 边上的权表示该线路的造价
* 设计一个方案，使这个通信网的总造价最低
* Link:https://59888888.xyz/
* Phone:18893558104
*/
#include <bits/stdc++.h>
using namespace std;
struct Edge
{
int x;
int y;
int weight;
} edge[100];
int ans = 0, n, e;
int father[100];
bool compare(Edge n1, Edge n2)
{
return n1.weight < n2.weight;
}
int findFather(int num)
{
while (father[num] != num)
{
num = father[num];
}
return num;
}
void kruskal()
{
for (int i = 0; i < e; i++)
{
int a = findFather(edge[i].x);
int b = findFather(edge[i].y);
if (a != b)
{
ans += edge[i].weight;
father[a] = b;
}
}
}
int main()
{
cout << "输入点和边的个数:" << endl;
cin >> n >> e;
cout << "依次输入边:" << endl;
for (int i = 0; i < e; i++)
{
cin >> edge[i].x >> edge[i].y >> edge[i].weight;
}
for (int i = 1; i <= n; i++)
{
father[i] = i;
}
sort(edge, edge + e, compare);
kruskal();
cout << "最少花费为:" << ans;
return 0;
}