matrix.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h> #include "aqueue.h" #define MAX_VALUE INT_MAX
#define MAX_NUM 100 typedef 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 = ; i < graph->vertexs; i++ )
{
scanf("%c", &graph->vertex[i]);
getchar();
} for ( i = ; i < graph->vertexs; i++ )//初始化矩阵
for ( j = ; j < graph->vertexs; j++ )
graph->arcs[i][j] = MAX_VALUE;
graph->brim = ;//初始化边数 // i 代表行数, j 是用来循环的, k 代表列数
for ( i = ; i < graph->vertexs; i++ )
{
printf("输入与%c节点相邻的节点与权值,输入#号键结束\n", graph->vertex[i]);
for ( j = ; j < graph->vertexs; j++ )
{
scanf("%c", &c);
if ( c == '#' )
{
getchar();
break;
}
scanf("%d", &num);
for ( k = ; k < graph->vertexs; k++ )
{
if ( graph->vertex[k] != c )
continue;
graph->arcs[i][k] = num;
graph->brim++;
}
getchar();
}
}
graph->brim /= ;
} void g_printMatrix(Graph * graph)//打印矩阵状态
{
int i, j; printf("brim = %d\n", graph->brim);
for ( i = ; i < graph->vertexs; i++ )
{
for ( j = ; 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 = ; i < graph->vertexs; i++ )
visited[i] = false;
visited[] = true;
dfs_graph(graph, visited, );
printf("\n");
} static void dfs_graph(Graph * graph, bool visited[], const int i)
{
int j;
printf("%c\t", graph->vertex[i]);
for ( j = ; 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 = ; i < graph->vertexs; i++ )
visited[i] = false; visited[] = true;
q_push(&queue, );
while ( !q_empty(&queue) )
{
pos = q_front(&queue);
printf("%c\t", graph->vertex[pos]);
for ( i = ; 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 = ; i < graph->vertexs; i++ )
visited[i] = false;
init_prim(graph, prim_tree); visited[] = true;
for ( i = ; i < graph->vertexs; i++ )
{
power = MAX_VALUE;
for ( j = ; j < graph->vertexs; j++ )
{
if ( visited[j] )
{
for ( k = ; 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 = ; i < prim_tree->vertexs; i++ )//初始化节点
prim_tree->vertex[i] = graph->vertex[i];
for ( i = ; i < prim_tree->vertexs; i++ )//初始化矩阵
{
for ( j = ; 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 = ; i < graph->vertexs; i++ )
visited[i] = i; k = ;
for ( i = ; i < graph->vertexs; i++ )
{
for ( j = i + ; 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 = ; 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 = ; 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 = ; i < graph->vertexs; i++ )
kruskal_tree->vertex[i] = graph->vertex[i]; for ( i = ; i < graph->vertexs; i++ )
for ( j = ; 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 = ; i < size - ; i++ )
{
for ( j = i + ; 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 ;
}
aqueue.h
#ifndef _QUEUE_H
#define _QUEUE_H #define MAXSIZE 10 typedef 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 <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h> #include "aqueue.h" void q_init(Queue * queue)
{
queue->arr = (int *)malloc( sizeof(int) * MAXSIZE );//初始化数组
assert(queue->arr != NULL);
queue->front = ;
queue->rear = ;
} 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 + ) % 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 - ];
} void q_destroy(Queue * queue)
{
free(queue->arr);
}