Graph

写了一些关于图的板子

DFS&BFS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
  
#define MAXSIZE 100
  
typedef struct arcnode {
	int index;
	struct arcnode* next;
} arcnode;
  
typedef struct {
	int data;
	arcnode* firstarc;
} vexnode;
  
typedef struct {
	vexnode vers[MAXSIZE];
	int vexnum, arcnum;
} Gra;
  
void DFS(Gra g, int *v, int begin) {
	v[begin] = 1;
	printf("%d", g.vers[begin]. data);
	arcnode* p = g.vers[begin].firstarc;
	while (p) {
		if (!v[p->index]) {
			DFS(g,v,p->index);
		}
		p=p->next;
	}
}
  
void BFS(Gra g,int *v,int begin){
	int queue[MAXSIZE];
	int front = -1, rear = -1;
	queue[++rear] = begin;
	v[begin] = 1;
	while (rear > front) {
		arcnode* p = g.vers[queue[++front]].firstarc;
		while (p) {
			if (!v[p->index]) {
				queue[++rear] = p->index;
				v[p->index] = 1;
			}
			p = p->next;
		}
	}
}

Prim

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
  
#define INF 0x3f3f3f3f
#define MAXSIZE 100
  
typedef struct arcnode {
	int index;
	int weight;
	struct arcnode* next;
} arcnode;
  
typedef struct {
	arcnode* firstarc;
} vexnode;
  
typedef struct {
	vexnode vers[MAXSIZE];
	int vexnum, arcnum;
}Gra;
  
int Prim(Gra* g, int *v, int begin){
	v[begin] = 1;
	int sum = 1, sumweight = 0;
	int weight = INF;
	int idx;
	  
	while (sum < g->vexnum) {
		weight = INF;
		for (int i = 1; i < g->vexnum+1; i++){
			if (v[i]) {
				arcnode* p = g->vers[i].firstarc;
				while (p) {
					if(p->weight < weight && !v[p->index]){
						weight = p->weight;
						idx = p->index;
					}
					p = p->next;
				}
			}
		}
		if (weight == INF) return -1;
		sumweight += weight;
		v[idx] = 1;
		sum++;
	}
	return sumweight;
}
  
int main(){
	Gra g;
	memset(&g, 0, sizeof(Gra));
	scanf("%d %d", &g.vexnum, &g.arcnum);
	for (int i = 0; i < g.arcnum; i++) {
		int idx1, idx2, w;
		scanf("%d %d %d", &idx1, &idx2, &w);
		arcnode* t = (arcnode*)malloc(sizeof(arcnode));
		t->index = idx2;
		t->weight = w;
		t->next = g.vers[idx1].firstarc;
		g.vers[idx1].firstarc = t;
		  
		arcnode* p = (arcnode*)malloc(sizeof(arcnode));
		p->index = idx1;
		p->weight = w;
		p->next = g.vers[idx2].firstarc;
		g.vers[idx2].firstarc = p;
	}
	  
	int visited[g.vexnum+1];
	memset(visited, 0, sizeof(visited));
	printf("%d", Prim(&g, visited, 1));
	return 0;
}

Kruskal

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
  
#define INF 0x3f3f3f3f
#define MAXSIZE 100
  
typedef struct arcnode {
	int begin;
	int end;
	int weight;
}arcnode;
  
int cmp(const void* a, const void* b){
	arcnode* nodea = (arcnode*)a;
	arcnode* nodeb = (arcnode*)b;
	return nodea->weight - nodeb->weight;
}
  
int find_root(int idx, int *root){
	if(idx != root[idx]){
		root[idx] = find_root(root[idx], root);
	}
	return root[idx];
}
  
//实际上只需要边节点
int Kruskal(arcnode* edges, int size, int vexnum){
	qsort(edges, size, sizeof(arcnode), cmp);
	int root[vexnum];
	int rootsize[vexnum];
	int total = 0,finised = 0;
	for (int i = 0; i < vexnum; i++){
		root[i] = i;
		rootsize[i] = 1;
	}
	for (int i = 0; i < size; i++) {
		int idx1 = edges[i].begin;
		int idx2 = edges[i].end;
		int weight = edges[i].weight;
		
		int root_a = find_root(idx1,root);
		int root_b = find_root(idx2,root);
		
		if(root_a == root_b) continue;
		  
		if(rootsize[root_a] > rootsize[root_b]){
			root[root_b] = root_a;
			rootsize[root_a] += rootsize[root_b];
		}else{
			root[root_a] = root_b;
			rootsize[root_b] += rootsize[root_a];
		}
		total += weight;
		finised++;
	}
	if(finised == vexnum-1) return total;
	return -1;
}
  
int main(){
	int vexnum, arcnum;
	scanf("%d %d", &vexnum, &arcnum);
	arcnode edges[arcnum];
	for (int i = 0; i < arcnum; i++)
		scanf("%d %d %d", &edges[i].begin, &edges[i].end, &edges[i].weight);
	printf("%d", Kruskal(edges, arcnum, vexnum));
	return 0;
}

Dijktra

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
  
#define MAXSIZE 100
#define INF 0x3f3f3f
  
typedef struct arcnode {
	int index;
	int weight;
	struct arcnode* next;
} arcnode;
  
typedef struct {
	int data;
	arcnode* firstarc;
} vexnode;
  
typedef struct {
	vexnode vers[MAXSIZE];
	int vexnum,arcnum;
}Gra;
  
int Findmin(Gra *g, int *v){
	int index, min = INF;
	for (int i = 0; i < g->vexnum; i++) {
		if (g->vers[i].data < min && !v[i]) {
			min = g->vers[i].data;
			index = i;
		}
	}
	if (min == INF){
		return -1;
	}
	else return index;
}
  
void Dijkstra(Gra *g, int begin, int *v) {
	v[begin] = 1;
	  
	arcnode *p = g->vers[begin].firstarc;
	while (p) {
		if (!v[p->index] &&
		g->vers[begin].data + p->weight < g->vers[p->index].data) {
			g->vers[p->index].data = g->vers[begin].data + p->weight;
		}
		p = p->next;
	}
	  
	int index = Findmin(g, v);
	if (index != -1) Dijkstra(g, index, v);
}


  
void Print(Gra* g, int begin){
	for (int i = 0; i < g->vexnum; i++) {
		if(i==begin) continue;
		printf("%d 到 %d 的距离为 %d \n",begin,i,g->vers[i].data);
	}
}
  
int main(){
	Gra g;
	memset(&g, 0, sizeof(Gra));
	scanf("%d %d", &g.vexnum, &g.arcnum);
	  
	for (int i = 1; i < g.vexnum; i++) {
		g.vers[i].data = INF;
	}
	  
	for (int i = 0; i < g.arcnum; i++)
	{
		int idx1, idx2, w;
		scanf("%d %d %d", &idx1, &idx2, &w);
		arcnode* t = (arcnode*)malloc(sizeof(arcnode));
		t->index = idx2;
		t->weight = w;
		t->next = g.vers[idx1].firstarc;
		g.vers[idx1].firstarc = t;
		arcnode* p = (arcnode*)malloc(sizeof(arcnode));
		p->index = idx1;
		p->weight = w;
		p->next = g.vers[idx2].firstarc;
		g.vers[idx2].firstarc = p;
	}
	  
	int visited[g.vexnum];
	memset(visited, 0, sizeof(visited));
	Dijkstra(&g, 0, visited);
	Print(&g, 0);
	return 0;
}