- #include <stdio.h>
- #include <time.h>
- #include <stdlib.h>
- #define MAX_EDGE_NUM 30 //定义最大边数
- #define MAX_EDGE_SIZE 100 //定义边长的最大值
- #define set_bit(a, x) (a |= (1 << x)) //将a的第x位置1
- #define judge_bit(a, x) (a & (1 << x)) //判断a的第x位是否为1
- //////////////////////自定义类型/////////////////////////
- //定义节点类型,以起点和终点来表示
- typedef struct Node
- {
- short begin;
- short end;
- short weight;
- }Node;
- //定义图的类型,包括顶点数和边数
- typedef struct Graph
- {
- short vexnum;
- short edgenum;
- Node graph[MAX_EDGE_NUM];
- }Graph;
- //////////////////////自定义类型/////////////////////////
- void InputInfo(Graph &G)
- {
- unsigned short i = 0, j = 0, m = 0, n = 0;
- srand( (unsigned int)time(0) );
- printf("please input this graph vexnum and edgenum:");
- scanf("%d%d", &m, &n);
- //图的顶点数和边数不能超出限制
- if(m >= MAX_EDGE_NUM || n >= MAX_EDGE_NUM)
- {
- perror("beyond size limit!");
- exit(1);
- }
- G.vexnum = m;
- G.edgenum = n;
- for(i = 1; i <= G.edgenum; )
- {
- here:
- printf("please input the %d begin and end vertex:", i);
- scanf("%d%d", &m, &n);
- //防止输入边的起点和终点出错
- if(m <= G.vexnum && n <= G.vexnum && m != n)
- {
- for(j = 1; j < i; ++j)
- if( (m == G.graph[j].begin && n == G.graph[j].end) || (m == G.graph[j].end && n == G.graph[j].begin) )
- {
- printf("data is repeat!\\n");
- goto here;
- }
- //为图的节点赋值
- G.graph[i].begin = m;
- G.graph[i].end = n;
- //这里用到随机数赋权值
- G.graph[i].weight = rand() % MAX_EDGE_SIZE + 1;
- ++i;
- }
- else
- printf("beyond size limit!\\n");
- }
- }
- /////////////////////堆排序////////////////////////
- void SetInfo(Node &to, Node &from)
- {
- to.begin = from.begin;
- to.end = from.end;
- to.weight = from.weight;
- }
- void HeapAdjust(Graph &G, unsigned short s, unsigned short m)
- {
- unsigned short j = 0;
- Node tmp = { 0 };
- SetInfo(tmp, G.graph[s]);
- for(j = 2*s; j <=m; j*=2)
- {
- if(j<m && G.graph[j].weight < G.graph[j+1].weight)
- ++j;
- if(tmp.weight >= G.graph[j].weight)
- break;
- SetInfo(G.graph[s], G.graph[j]);
- s = j;
- }
- SetInfo(G.graph[s], tmp);
- }
- void SwapInfo(Node &one, Node &two)
- {
- Node tmp = { 0 };
- tmp.begin = one.begin;
- tmp.end = one.end;
- tmp.weight = one.weight;
- one.begin = two.begin;
- one.end = two.end;
- one.weight = two.weight;
- two.begin = tmp.begin;
- two.end = tmp.end;
- two.weight = tmp.weight;
- }
- void HeapSort(Graph &G)
- {
- unsigned short i = 0;
- for(i = G.edgenum/2; i > 0; --i)
- HeapAdjust(G, i, G.edgenum);
- for(i = G.edgenum; i > 1; --i)
- {
- SwapInfo(G.graph[1], G.graph[i]);
- HeapAdjust(G, 1, i-1);
- }
- }
- ///////////////////堆排序结束/////////////////////////
- /**
- *普利姆算法:
- * 图类型里的数据保存的是边的信息,因此个人感觉较不适合,但
- *考虑到已经进行了堆排序,因此尝试使用保存已经遍历的节点和可以
- *使用的顶点信息来进行。(表述不太好)
- **/
- void Pram(Graph &G)
- {
- unsigned short i = 0, j = 0;
- //嗯...英语不好
- long visited = 0, can_begin = 0;
- printf("Pram :\\n");
- do
- {
- printf("please input start vex:");
- scanf("%d", &i);
- }while(i > G.vexnum);
- set_bit(can_begin, i);
- for(i = 0; i < G.vexnum-1; ++i)
- for(j = 1; j < G.edgenum; ++j)
- {
- //如果边节点没有使用过,而且can_begin中存有该节点的起点或终点
- if(!judge_bit(visited, j) && ( judge_bit(can_begin, G.graph[j].begin) || judge_bit(can_begin, G.graph[j].end)) )
- {
- //输出并标记
- printf("[(%d,%d):%d] ", G.graph[j].begin, G.graph[j].end, G.graph[j].weight);
- set_bit(can_begin, G.graph[j].begin);
- set_bit(can_begin, G.graph[j].end);
- set_bit(visited, j);
- break;
- }
- }
- printf("\\n");
- }
- //克鲁斯克尔算法,很常规就不解释了
- void Kruskal(Graph &G)
- {
- unsigned short set[MAX_EDGE_NUM] = { 0 };
- unsigned short v1 = 0, v2 = 0;
- unsigned short i = 1, j = 1;
- printf("Kruskal:\\n");
- for(i = 1; i <=G.edgenum; ++i)
- set[i] = i;
- i = 1;
- while(j < G.vexnum && i <= G.edgenum)
- {
- v1 = set[G.graph[i].begin];
- v2 = set[G.graph[i].end];
- if(v1 != v2)
- {
- printf("[(%d,%d):%d] ", G.graph[j].begin, G.graph[j].end, G.graph[j].weight);
- set[v1] = v2;
- ++j;
- }
- ++i;
- }
- printf("\\n");
- }
- int main(void)
- {
- Graph G = { 0 };
- InputInfo(G);
- HeapSort(G);
- Pram(G);
- Kruskal(G);
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/251120137445.html
来源: http://www.codesnippet.cn/detail/251120137445.html