用 c 语言写图论的生成查找
时间: 2024-04-29 13:22:23 浏览: 18
生成图:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_VERTICES 100
#define MAX_EDGES 1000
typedef struct {
int vertex1;
int vertex2;
} Edge;
int rand_int(int min, int max) {
return min + rand() % (max - min + 1);
}
void generate_graph(int vertices, int edges, Edge *graph) {
int i, j, count = 0;
for (i = 0; i < vertices; i++) {
for (j = i + 1; j < vertices; j++) {
if (count >= edges) return;
graph[count].vertex1 = i;
graph[count].vertex2 = j;
count++;
}
}
while (count < edges) {
int vertex1 = rand_int(0, vertices - 1);
int vertex2 = rand_int(0, vertices - 1);
if (vertex1 != vertex2) {
graph[count].vertex1 = vertex1;
graph[count].vertex2 = vertex2;
count++;
}
}
}
void print_graph(int vertices, int edges, Edge *graph) {
int i;
for (i = 0; i < edges; i++) {
printf("%d -- %d\n", graph[i].vertex1, graph[i].vertex2);
}
}
int main() {
srand(time(NULL));
int vertices = 7;
int edges = 15;
Edge *graph = malloc(sizeof(Edge) * edges);
generate_graph(vertices, edges, graph);
print_graph(vertices, edges, graph);
free(graph);
return 0;
}
```
查找图:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 100
#define MAX_EDGES 1000
typedef struct {
int vertex1;
int vertex2;
} Edge;
int find_parent(int *parent, int vertex) {
if (parent[vertex] == vertex) return vertex;
return parent[vertex] = find_parent(parent, parent[vertex]);
}
bool union_vertices(int *parent, int *rank, int vertex1, int vertex2) {
int parent1 = find_parent(parent, vertex1);
int parent2 = find_parent(parent, vertex2);
if (parent1 == parent2) return false;
if (rank[parent1] > rank[parent2]) {
parent[parent2] = parent1;
} else if (rank[parent1] < rank[parent2]) {
parent[parent1] = parent2;
} else {
parent[parent2] = parent1;
rank[parent1]++;
}
return true;
}
bool is_connected(int vertices, int edges, Edge *graph) {
int i, parent[MAX_VERTICES], rank[MAX_VERTICES];
for (i = 0; i < vertices; i++) {
parent[i] = i;
rank[i] = 0;
}
for (i = 0; i < edges; i++) {
int vertex1 = graph[i].vertex1;
int vertex2 = graph[i].vertex2;
if (!union_vertices(parent, rank, vertex1, vertex2)) {
return true;
}
}
return false;
}
int main() {
int vertices = 7;
int edges = 15;
Edge *graph = malloc(sizeof(Edge) * edges);
graph[0].vertex1 = 0; graph[0].vertex2 = 1;
graph[1].vertex1 = 0; graph[1].vertex2 = 2;
graph[2].vertex1 = 0; graph[2].vertex2 = 5;
graph[3].vertex1 = 1; graph[3].vertex2 = 2;
graph[4].vertex1 = 1; graph[4].vertex2 = 3;
graph[5].vertex1 = 1; graph[5].vertex2 = 4;
graph[6].vertex1 = 2; graph[6].vertex2 = 3;
graph[7].vertex1 = 2; graph[7].vertex2 = 5;
graph[8].vertex1 = 3; graph[8].vertex2 = 4;
graph[9].vertex1 = 3; graph[9].vertex2 = 5;
graph[10].vertex1 = 3; graph[10].vertex2 = 6;
graph[11].vertex1 = 4; graph[11].vertex2 = 5;
graph[12].vertex1 = 4; graph[12].vertex2 = 6;
graph[13].vertex1 = 5; graph[13].vertex2 = 6;
graph[14].vertex1 = 6; graph[14].vertex2 = 6;
if (is_connected(vertices, edges, graph)) {
printf("The graph is connected.\n");
} else {
printf("The graph is not connected.\n");
}
free(graph);
return 0;
}
```
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)