matrix.c
#include#include #include #include #include "aqueue.h"#define MAX_VALUE INT_MAX#define MAX_NUM 100typedef char node_type;typedef struct matrix{ node_type vertex[MAX_NUM];//节点信息 int arcs[MAX_NUM][MAX_NUM];//矩阵 int vertexs, brim;//节点数,边数} Graph;void g_create(Graph * graph){ int num; int i, j, k; char c; printf("输入节点个数:"); scanf("%d", &graph->vertexs); getchar();//接受回车键 printf("输入节点信息:"); for ( i = 0; i < graph->vertexs; i++ ) { scanf("%c", &graph->vertex[i]); getchar(); } for ( i = 0; i < graph->vertexs; i++ )//初始化矩阵 for ( j = 0; j < graph->vertexs; j++ ) graph->arcs[i][j] = MAX_VALUE; graph->brim = 0;//初始化边数 // i 代表行数, j 是用来循环的, k 代表列数 for ( i = 0; i < graph->vertexs; i++ ) { printf("输入与%c节点相邻的节点与权值,输入#号键结束\n", graph->vertex[i]); for ( j = 0; j < graph->vertexs; j++ ) { scanf("%c", &c); if ( c == '#' ) { getchar(); break; } scanf("%d", &num); for ( k = 0; k < graph->vertexs; k++ ) { if ( graph->vertex[k] != c ) continue; graph->arcs[i][k] = num; graph->brim++; } getchar(); } } graph->brim /= 2;}void g_printMatrix(Graph * graph)//打印矩阵状态{ int i, j; printf("brim = %d\n", graph->brim); for ( i = 0; i < graph->vertexs; i++ ) { for ( j = 0; j < graph->vertexs; j++ ) { printf("%-10d ", graph->arcs[i][j]); } printf("\n"); }}//深度优先遍历static void dfs_graph(Graph * graph, bool visited[], const int i);void g_depth_first_search(Graph * graph){ bool visited[graph->vertexs]; int i; for ( i = 0; i < graph->vertexs; i++ ) visited[i] = false; visited[0] = true; dfs_graph(graph, visited, 0); printf("\n");}static void dfs_graph(Graph * graph, bool visited[], const int i){ int j; printf("%c\t", graph->vertex[i]); for ( j = 0; j < graph->vertexs; j++ )//依次检查矩阵 { if ( graph->arcs[i][j] != MAX_VALUE && !visited[j] )//i 代表矩阵的行, j 代表矩阵的列 { visited[j] = true; dfs_graph(graph, visited, j); } }}//广度优先遍历void g_breadth_first_search(Graph * graph){ Queue queue;//队列存储的是节点数组的下标(int) bool visited[graph->vertexs]; int i, pos; q_init(&queue); for ( i = 0; i < graph->vertexs; i++ ) visited[i] = false; visited[0] = true; q_push(&queue, 0); while ( !q_empty(&queue) ) { pos = q_front(&queue); printf("%c\t", graph->vertex[pos]); for ( i = 0; i < graph->vertexs; i++ )//把队头元素的邻接点入队 { if ( !visited[i] && graph->arcs[pos][i] != MAX_VALUE ) { visited[i] = true; q_push(&queue, i); } } q_pop(&queue); } printf("\n");}//最小生成树prim算法static void init_prim(Graph * graph, Graph * prim_tree);void Prim(Graph * graph, Graph * prim_tree){ bool visited[graph->vertexs]; int i, j, k, h; int power, power_j, power_k; for ( i = 0; i < graph->vertexs; i++ ) visited[i] = false; init_prim(graph, prim_tree); visited[0] = true; for ( i = 0; i < graph->vertexs; i++ ) { power = MAX_VALUE; for ( j = 0; j < graph->vertexs; j++ ) { if ( visited[j] ) { for ( k = 0; k < graph->vertexs; k++ ) { if ( power > graph->arcs[j][k] && !visited[k] ) { power = graph->arcs[j][k]; power_j = j; power_k = k; } } } } //min power if ( !visited[power_k] ) { visited[power_k] = true; prim_tree->arcs[power_j][power_k] = power; } }}static void init_prim(Graph * graph, Graph * prim_tree){ int i, j; prim_tree->vertexs = graph->vertexs; for ( i = 0; i < prim_tree->vertexs; i++ )//初始化节点 prim_tree->vertex[i] = graph->vertex[i]; for ( i = 0 ; i < prim_tree->vertexs; i++ )//初始化矩阵 { for ( j = 0; j < prim_tree->vertexs; j++ ) { prim_tree->arcs[i][j] = MAX_VALUE; } }}//最小生成树kruskal算法typedef struct{ int head;//边的始点下标 int tail;//边的终点下标 int power;//边的权值} Edge;static void init_kruskal(Graph * graph, Graph * kruskal_tree);static void my_sort(Edge * arr, int size);void kruskal(Graph * graph, Graph * kruskal_tree){ int visited[graph->vertexs]; Edge edge[graph->brim]; int i, j, k; int v1, v2, vs1, vs2; for ( i = 0; i < graph->vertexs; i++ ) visited[i] = i; k = 0; for ( i = 0; i < graph->vertexs; i++ ) { for ( j = i + 1; j < graph->vertexs; j++ ) { if ( graph->arcs[i][j] != MAX_VALUE ) { edge[k].head = i; edge[k].tail = j; edge[k].power = graph->arcs[i][j]; k++; } } } init_kruskal(graph, kruskal_tree); my_sort(edge, graph->brim); for ( i = 0; i < graph->brim; i++ ) { v1 = edge[i].head; v2 = edge[i].tail; vs1 = visited[v1]; vs2 = visited[v2]; if ( vs1 != vs2 ) { kruskal_tree->arcs[v1][v2] = graph->arcs[v1][v2]; for ( j = 0; j < graph->vertexs; j++ ) { if ( visited[j] == vs2 ) visited[j] = vs1; } } }}static void init_kruskal(Graph * graph, Graph * kruskal_tree){ int i, j; kruskal_tree->vertexs = graph->vertexs; kruskal_tree->brim = graph->brim; for ( i = 0; i < graph->vertexs; i++ ) kruskal_tree->vertex[i] = graph->vertex[i]; for ( i = 0; i < graph->vertexs; i++ ) for ( j = 0; j < graph->vertexs; j++ ) kruskal_tree->arcs[i][j] = MAX_VALUE;}static void my_sort(Edge * arr, int size){ int i, j; Edge tmp; for ( i = 0; i < size - 1; i++ ) { for ( j = i + 1; j < size; j++ ) { if ( arr[i].power > arr[j].power ) { tmp.head = arr[i].head; tmp.tail = arr[i].tail; tmp.power = arr[i].power; arr[i].head = arr[j].head; arr[i].tail = arr[j].tail; arr[i].power = arr[j].power; arr[j].head = tmp.head; arr[j].tail = tmp.tail; arr[j].power = tmp.power; } } }}int main(void){ Graph graph; Graph prim_tree; Graph kruskal_tree; g_create(&graph); g_printMatrix(&graph);// printf("\n");// g_depth_first_search(&graph);// g_breadth_first_search(&graph);//// Prim(&graph, &prim_tree);// g_printMatrix(&prim_tree);// g_depth_first_search(&prim_tree);// g_breadth_first_search(&prim_tree); kruskal(&graph, &kruskal_tree); g_printMatrix(&kruskal_tree); return 0;}
aqueue.h
#ifndef _QUEUE_H#define _QUEUE_H#define MAXSIZE 10typedef struct queue{ int * arr; int front; int rear;} Queue;void q_init(Queue * queue);//初始化void q_push(Queue * queue, const int data);//入队void q_pop(Queue * queue);//出队bool q_empty(Queue * queue);//为空bool q_full(Queue * queue);//为满int q_size(Queue * queue);//队大小int q_front(Queue * queue);//队头元素int q_back(Queue * queue);//队尾元素void q_destroy(Queue * queue);//销毁#endif //_QUEUE_h aqueue.c
#include#include #include #include #include "aqueue.h"void q_init(Queue * queue){ queue->arr = (int *)malloc( sizeof(int) * MAXSIZE );//初始化数组 assert(queue->arr != NULL); queue->front = 0; queue->rear = 0;}void q_push(Queue * queue, const int data){ if ( q_full(queue) ) return; queue->arr[queue->rear++] = data;//入队，队尾+1 queue->rear = queue->rear % MAXSIZE;//如果队尾}void q_pop(Queue * queue){ if ( q_empty(queue) ) return; queue->front = ++queue->front % MAXSIZE;//front+1，对MAXSIZE取余}bool q_empty(Queue * queue){ return queue->front == queue->rear;}bool q_full(Queue * queue){ return queue->front == (queue->rear + 1) % MAXSIZE;}int q_size(Queue * queue){ return (queue->rear - queue->front) % MAXSIZE;}int q_front(Queue * queue){ assert( !q_empty(queue) ); return queue->arr[queue->front];}int q_back(Queue * queue){ assert( !q_empty(queue) ); return queue->arr[queue->rear - 1];}void q_destroy(Queue * queue){ free(queue->arr);}