void CreateGrape(Graph &G,int n) { for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { scanf("%d",&G.arcs[i][j]); } } }
时间: 2024-02-02 21:03:10 浏览: 25
这段代码是用来创建一个邻接矩阵表示的无向图,其中n表示图的顶点数,G.arcs[i][j]表示顶点i和顶点j之间是否有边相连,1表示相连,0表示不相连。你可以通过这个函数输入一个n*n的邻接矩阵来描述一个无向图。如果你想创建有向图,可以将G.arcs[i][j]表示为从顶点i到顶点j是否有一条有向边。
相关问题
#include <stdio.h> #include <stdlib.h> #define MAXN 1000 #define INF 0x3f3f3f3f int n, m; int graph[MAXN][MAXN]; int path[MAXN]; int dist; void dfs(int u, int depth, int distance, int visited[]) { if (depth == n) { if (graph[u][1] != INF && distance + graph[u][1] < dist) { dist = distance + graph[u][1]; for (int i = 1; i <= n; i++) { printf("%d ", path[i]); } printf("1\n"); } return; } for (int v = 2; v <= n; v++) { if (!visited[v] && graph[u][v] != INF) { visited[v] = 1; path[depth+1] = v; dfs(v, depth+1, distance+graph[u][v], visited); visited[v] = 0; } } } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { graph[i][j] = INF; } } for (int i = 1; i <= m; i++) { int x, y, z; scanf("%d,%d,%d", &x, &y, &z); graph[x][y] = graph[y][x] = z; } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (graph[i][k] != INF && graph[k][j] != INF && graph[i][k] + graph[k][j] < graph[i][j]) { graph[i][j] = graph[i][k] + graph[k][j]; } } } } int visited[MAXN] = {0}; visited[1] = 1; path[1] = 1; dist = INF; dfs(1, 1, 0, visited); printf("%d\n", dist); return 0; }修改改代码,使其只显示最短路径
可以在dfs函数中加入一个变量来记录当前的最短路径长度,每次更新路径时判断是否比当前最短路径更短。同时,在找到最短路径后就直接return,不再继续搜索其他路径。
修改后的代码如下:
```
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000
#define INF 0x3f3f3f3f
int n, m;
int graph[MAXN][MAXN];
int path[MAXN];
int dist;
int shortest_dist = INF;
void dfs(int u, int depth, int distance, int visited[]) {
if (depth == n) {
if (graph[u][1] != INF && distance + graph[u][1] < shortest_dist) {
shortest_dist = distance + graph[u][1];
dist = distance + graph[u][1];
for (int i = 1; i <= n; i++) {
path[i] = i;
}
path[n+1] = 1;
}
return;
}
for (int v = 2; v <= n; v++) {
if (!visited[v] && graph[u][v] != INF) {
visited[v] = 1;
path[depth+1] = v;
dfs(v, depth+1, distance+graph[u][v], visited);
visited[v] = 0;
}
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
graph[i][j] = INF;
}
}
for (int i = 1; i <= m; i++) {
int x, y, z;
scanf("%d,%d,%d", &x, &y, &z);
graph[x][y] = graph[y][x] = z;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (graph[i][k] != INF && graph[k][j] != INF && graph[i][k] + graph[k][j] < graph[i][j]) {
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
}
int visited[MAXN] = {0};
visited[1] = 1;
path[1] = 1;
dfs(1, 1, 0, visited);
printf("%d\n", dist);
for (int i = 1; i <= n+1; i++) {
printf("%d ", path[i]);
}
printf("\n");
return 0;
}
```
void BFS(Graph \\&G,int n) { LinkQueue Q; InitLinkQueue(\\&Q); for(int i=0; i<n; i++) { if(G.vexs[i]==0) { printf(%d ,i); G.vexs[i]=1; InLinkQue
这段代码是一个基于邻接表存储方式的图的广度优先遍历算法实现。下面是这段代码的分析:
1. 首先创建一个队列 Q,用于存储待访问的节点。
2. 对于图中的每个节点,如果该节点没有被访问过,则将其标记为已访问,并将其加入队列 Q 中。
3. 对于队列 Q 中的每个节点,依次取出该节点,并访问其所有邻接节点。如果邻接节点没有被访问过,则将其标记为已访问,并将其加入队列 Q 中。
4. 重复步骤 3,直到队列 Q 中的所有节点都被访问过。
该算法可以用于计算图的连通性、最短路径等问题。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)