typedef struct MGraph
时间: 2023-04-06 14:04:49 浏览: 77
抱歉,我可以回答这个问题。typedef struct MGraph是一种定义图的数据结构的方式,其中MGraph表示图的类型名,struct表示定义一个结构体,而typedef则是为这个结构体定义一个别名,方便在程序中使用。
相关问题
C语言实现用Dijkstra算法实现如图V0到其他结点的单源最短路径的计算:#include <bits/stdc++.h> using namespace std;#define MAX 100 #define MAX_NODE_NUM 1000 typedef struct Arcell{ int adj;//权重 }Arcell,AdjMatrix[MAX][MAX];typedef struct MGraph{ char vex[MAX];//点的数组 AdjMatrix arc;//边 int Vexnum,Arcnum;//顶点数,边数 }MGraph;//构建图 int Locate(MGraph G,char v){//找到某个点的位置 int i; for(i=0;v!=G.vex[i];i++); return i; } void CreatMGraph(MGraph &G){//创建图的矩阵 printf(“请输入顶点数和弧数: ”);scanf(“%d%d”,&G.Vexnum,&G.Arcnum);国际 i,j,w;char v1,v2;//一条边的两个顶点 printf(“请输入各顶点: ”);for(i=0;i<G.Vexnum;i++){//构建矩阵 cin>>G.vex[i]; for(j=0;j<G.Vexnum;j++) G.arc[i][j].adj=G.arc[j][i].adj=0;//初始化度为零 } printf(“请输入各弧(格式为:顶点 顶点 弧长): \n”);for(i=0;i<G.Arcnum;i++){ getchar(); cin>>v1>>v2>>w; int t1=Locate(G,v1); int t2=Locate(G,v2);G.arc[t2][t1].adj=G.arc[t1][t2].adj=w;} } void Cout(MGraph G){//总的输出 printf(“以下为各顶点的度\n”); int i,j; for(i=0;i<G.Vexnum;i++){ int s=0; for(j=0;j<G.Vexnum;j++) if(G.arc[i][j].adj) s++; printf(“%c顶点的度为: %d \n”,G.vex[i],s); } } int main(){ MGraph G;CreatMGraph(G);库特(G);返回 1;}
这段代码同样是实现了一个无向图的创建和输出,但是它并没有实现 Dijkstra 算法来计算单源最短路径。如果你想要使用 C 语言实现 Dijkstra 算法,可以参考以下代码:
```c
#include <stdio.h>
#include <limits.h>
// 定义图的最大顶点数
#define MAX_VERTICES 100
// 定义邻接矩阵
typedef struct {
int weight[MAX_VERTICES][MAX_VERTICES]; // 权重数组
int n; // 图的顶点数
} Graph;
// Dijkstra 算法
void dijkstra(Graph *g, int start, int *dist, int *prev) {
int i, j, k, min;
int tmp;
int s[MAX_VERTICES]; // 标记顶点是否已被访问
// 初始化
for (i = 0; i < g->n; i++) {
dist[i] = g->weight[start][i]; // 初始化起点到各个顶点的距离
s[i] = 0; // 初始化所有顶点均未被访问
if (dist[i] == INT_MAX) {
prev[i] = -1; // 若起点和顶点之间没有直接的边,则令 prev[i] 为 -1
} else {
prev[i] = start; // 若起点和顶点之间有直接的边,则令 prev[i] 为 start
}
}
dist[start] = 0; // 起点到自身的距离为 0
s[start] = 1; // 标记起点已被访问
// 迭代 n-1 次
for (i = 1; i < g->n; i++) {
min = INT_MAX;
// 找到未被访问的距离起点最近的顶点
for (j = 0; j < g->n; j++) {
if (!s[j] && dist[j] < min) {
min = dist[j];
k = j;
}
}
s[k] = 1; // 标记该顶点已被访问
// 更新其他顶点到起点的距离
for (j = 0; j < g->n; j++) {
tmp = (g->weight[k][j] == INT_MAX ? INT_MAX : (min + g->weight[k][j]));
if (!s[j] && (tmp < dist[j])) {
dist[j] = tmp;
prev[j] = k;
}
}
}
}
int main() {
Graph g;
int i, j;
int dist[MAX_VERTICES];
int prev[MAX_VERTICES];
int start;
// 输入图的顶点数
printf("请输入图的顶点数:");
scanf("%d", &g.n);
// 输入图的邻接矩阵
printf("请输入邻接矩阵,若两顶点之间没有直接的边则权重为 %d:\n", INT_MAX);
for (i = 0; i < g.n; i++) {
for (j = 0; j < g.n; j++) {
scanf("%d", &g.weight[i][j]);
}
}
// 输入起点
printf("请输入起点:");
scanf("%d", &start);
// 运行 Dijkstra 算法
dijkstra(&g, start, dist, prev);
// 输出起点到各顶点的最短路径
printf("起点到各顶点的最短路径如下:\n");
for (i = 0; i < g.n; i++) {
printf("起点到顶点 %d 的最短路径为:%d,路径为:", i, dist[i]);
j = i;
while (j != start) {
printf("%d<-", j);
j = prev[j];
}
printf("%d\n", start);
}
return 0;
}
```
这段代码实现了 Dijkstra 算法来计算单源最短路径。
优化以下代码#include<iostream> using namespace std; #include<algorithm> #define MAXSIZE 100 int father[MAXSIZE];//存放父亲节点 typedef struct Mgraph { int s[MAXSIZE][MAXSIZE]; int n;//节点数 }; struct graph { int a, b, c; }arr[MAXSIZE]; bool compare(graph x, graph y) {//对边按照权值从小到大排序 return x.c < y.c; } int Find(int x) {//找到一个节点的根节点,并将其下面的所有节点的father都改为根节点。 while (x != father[x]) { int temp = x; x = father[x]; father[temp] = x; } return x; } int main() { Mgraph p; int m; cin >> p.n >> m; for (int i = 0; i < m; i++) { cin >> arr[i].a >> arr[i].b >> arr[i].c;//a,b间,需要c天 } for (int i = 1; i < p.n + 1; i++)//初始化father数组,将每个节点的父亲节点设置为自己 father[i] = i; sort(arr, arr + m, compare);//对边按照权值从小到大排序 for (int i = 0; i < m; i++) { if (Find(arr[i].a) != Find(arr[i].b)) father[Find(arr[i].a)] = Find(arr[i].b);//遍历每条边,如果该边的两个节点不在同一个连通块中,则将它们连通,并将它们的父亲节点设置为同一个节点。 if (Find(1) == Find(p.n)) {//如果1号节点和n号节点在同一个连通块中,则输出当前边的权值,并结束程序 cout << arr[i].c << endl; break; } } }
这段代码是 Kruskal 算法的实现,用于解决最小生成树问题。优化的方向可以从以下几个方面考虑:
1. 可以使用并查集的路径压缩优化,将 Find 函数中的路径压缩操作加上,可以有效降低时间复杂度。
2. 可以使用快读和快输来优化输入输出,加快读入和输出的速度。
3. 可以使用堆优化的 Kruskal 算法,将边按照权值建立小根堆,每次取出堆顶的边进行处理,可以降低时间复杂度。
4. 可以使用邻接表存储图,减小程序所占用的空间。
下面是代码的优化版:
```c++
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
#define MAXSIZE 100010
struct Edge {
int u, v, w;
bool operator < (const Edge& e) const {
return w < e.w;
}
};
int father[MAXSIZE];
int n, m;
int find(int x) {
if (x != father[x]) {
father[x] = find(father[x]);
}
return father[x];
}
int main() {
scanf("%d%d", &n, &m);
vector<Edge> edges(m);
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);
}
sort(edges.begin(), edges.end());
for (int i = 1; i <= n; i++) {
father[i] = i;
}
int ans = 0;
for (int i = 0; i < m; i++) {
int fu = find(edges[i].u);
int fv = find(edges[i].v);
if (fu == fv) {
continue;
}
father[fu] = fv;
ans = edges[i].w;
if (find(1) == find(n)) {
break;
}
}
printf("%d\n", ans);
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)