用c语言实现图的各种操作
时间: 2023-05-19 22:03:45 浏览: 52
可以使用邻接矩阵或邻接表来表示图,然后实现图的遍历、最短路径、最小生成树等操作。以下是一些示例代码:
邻接矩阵表示法:
```c
#define MAX_VERTICES 100
typedef struct {
int n; // 图中顶点数
int adj[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
} Graph;
void init_graph(Graph* g, int n) {
g->n = n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
g->adj[i][j] = 0;
}
}
}
void add_edge(Graph* g, int u, int v) {
g->adj[u][v] = 1;
g->adj[v][u] = 1; // 无向图需要反向连接
}
void dfs(Graph* g, int v, int visited[]) {
visited[v] = 1;
printf("%d ", v);
for (int i = 0; i < g->n; i++) {
if (g->adj[v][i] && !visited[i]) {
dfs(g, i, visited);
}
}
}
void bfs(Graph* g, int v, int visited[]) {
int queue[MAX_VERTICES], front = 0, rear = 0;
visited[v] = 1;
printf("%d ", v);
queue[rear++] = v;
while (front < rear) {
int u = queue[front++];
for (int i = 0; i < g->n; i++) {
if (g->adj[u][i] && !visited[i]) {
visited[i] = 1;
printf("%d ", i);
queue[rear++] = i;
}
}
}
}
void dijkstra(Graph* g, int start, int dist[]) {
int visited[MAX_VERTICES] = {0};
for (int i = 0; i < g->n; i++) {
dist[i] = INT_MAX;
}
dist[start] = 0;
for (int i = 0; i < g->n; i++) {
int u = -1;
for (int j = 0; j < g->n; j++) {
if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
u = j;
}
}
visited[u] = 1;
for (int v = 0; v < g->n; v++) {
if (g->adj[u][v]) {
int new_dist = dist[u] + 1;
if (new_dist < dist[v]) {
dist[v] = new_dist;
}
}
}
}
}
void prim(Graph* g, int parent[]) {
int key[MAX_VERTICES], visited[MAX_VERTICES] = {0};
for (int i = 0; i < g->n; i++) {
key[i] = INT_MAX;
}
key[0] = 0;
parent[0] = -1;
for (int i = 0; i < g->n - 1; i++) {
int u = -1;
for (int j = 0; j < g->n; j++) {
if (!visited[j] && (u == -1 || key[j] < key[u])) {
u = j;
}
}
visited[u] = 1;
for (int v = 0; v < g->n; v++) {
if (g->adj[u][v] && !visited[v] && g->adj[u][v] < key[v]) {
parent[v] = u;
key[v] = g->adj[u][v];
}
}
}
}
```
邻接表表示法:
```c
#define MAX_VERTICES 100
typedef struct Node {
int v; // 相邻顶点编号
int weight; // 边权重
struct Node* next; // 指向下一个相邻顶点的指针
} Node;
typedef struct {
int n; // 图中顶点数
Node* adj[MAX_VERTICES]; // 邻接表
} Graph;
void init_graph(Graph* g, int n) {
g->n = n;
for (int i = 0; i < n; i++) {
g->adj[i] = NULL;
}
}
void add_edge(Graph* g, int u, int v, int weight) {
Node* node = (Node*)malloc(sizeof(Node));
node->v = v;
node->weight = weight;
node->next = g->adj[u];
g->adj[u] = node;
}
void dfs(Graph* g, int v, int visited[]) {
visited[v] = 1;
printf("%d ", v);
for (Node* p = g->adj[v]; p != NULL; p = p->next) {
int u = p->v;
if (!visited[u]) {
dfs(g, u, visited);
}
}
}
void bfs(Graph* g, int v, int visited[]) {
int queue[MAX_VERTICES], front = 0, rear = 0;
visited[v] = 1;
printf("%d ", v);
queue[rear++] = v;
while (front < rear) {
int u = queue[front++];
for (Node* p = g->adj[u]; p != NULL; p = p->next) {
int w = p->v;
if (!visited[w]) {
visited[w] = 1;
printf("%d ", w);
queue[rear++] = w;
}
}
}
}
void dijkstra(Graph* g, int start, int dist[]) {
int visited[MAX_VERTICES] = {0};
for (int i = 0; i < g->n; i++) {
dist[i] = INT_MAX;
}
dist[start] = 0;
for (int i = 0; i < g->n; i++) {
int u = -1;
for (int j = 0; j < g->n; j++) {
if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
u = j;
}
}
visited[u] = 1;
for (Node* p = g->adj[u]; p != NULL; p = p->next) {
int v = p->v, weight = p->weight;
int new_dist = dist[u] + weight;
if (new_dist < dist[v]) {
dist[v] = new_dist;
}
}
}
}
void prim(Graph* g, int parent[]) {
int key[MAX_VERTICES], visited[MAX_VERTICES] = {0};
for (int i = 0; i < g->n; i++) {
key[i] = INT_MAX;
}
key[0] = 0;
parent[0] = -1;
for (int i = 0; i < g->n - 1; i++) {
int u = -1;
for (int j = 0; j < g->n; j++) {
if (!visited[j] && (u == -1 || key[j] < key[u])) {
u = j;
}
}
visited[u] = 1;
for (Node* p = g->adj[u]; p != NULL; p = p->next) {
int v = p->v, weight = p->weight;
if (!visited[v] && weight < key[v]) {
parent[v] = u;
key[v] = weight;
}
}
}
}
```