最小生成树

Created2020-05-30|Updated2022-05-22

|Post Views:

Minimum Spanning　Tree

若图中有v个顶点，那么将生成v-1条边
这棵树包含了全部的顶点
不能有回路，且向树添加一条边就有回路
图连通<=>最小生成树存在
不唯一

Related Articles

前言ADT（抽象数据类型），如果我们的程序需要使用类型，C中没有与之匹配的基本类型。那我们可以自己定义抽象数据类型。如果，我们要设计一个数据类型需要：提供存储数据的方法。（定义一个结构）描述操控该数据的方法如何实现？对数据类型进行一个属性和操作的描述。开发一个实现ADT的接口。（在.h头文件）编写代码实现接口。（.c文件）例如int类型给我们的属性是：它代表一个整数值。操作是：可以进行+ - * / % Anyway.ADT就是描述一些这个类型是属性和操作。如果要实现它，再通过接口(.h .c)来实现它。

图的存储邻接矩阵我们使用邻接矩阵来表示图的边。邻接表法这里的表是指链表。表面一个顶点所邻接的边。

线性表的顺序存储结构

前言线性表有一种物理结构叫顺序存储结构。它由一系列连续的存储单元组成，从而使得逻辑上相邻的两个元素也连续。这样的结构可以使用一维数组来实现。数组的下标从0开始，但我们的元素是从1开始。所以，我们可以这样看：元素均对应，但标志不一样（只需在用[]时，-1即可） 12345#define MaxSize 50 // 定义线性表的最大长度typedef struct{ ElemType data [MaxSize] ; // 表的元素 int length; // 线性表的当前长度}SqList; // 表的类型定义注意线性表长度和数组长度不同操作Insert 如果线性表长度等于数组长度，退出如果插入到线性表长度+1以外，退出如果不是插到最后（length + 1），那么for，从最后一个元素到第i个，一个个往后退 Delete 如果线性表为空，退出如果删除表以外的数据，退出如果不是删除最后位置，for，从i+1到length一个个向前移示例11234567891011121314151617#define TSIZE...

顺序查找暴力遍历顺序表通过数组下标递增来扫描每一个元素链表通过next指针来扫描整个链表二分查找（折半查找）(Binary Search)流程图代码实现123456789101112131415161718192021222324252627#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#define ElemType intint Binary_Search(ElemType e, ElemType* arr, int n) { int low = 0, high = n - 1, mid;//记录数组下标 while (low <= high) { mid = (low + high) / 2; if (arr[mid] == e) { return mid; } else if (e < arr[mid]) { high = mid - 1; } else { low = mid...

队列队列这种逻辑结构，也能用顺序表和链表实现，本次主要讲用顺序结构实现的循环队列。队列是一种被限制的线性表，只能在队列的队头进行删除，在队尾进行增加循环队列首先，我们要先认识一下循环队列。这里的循环队列，我们用顺序结构（数组）实现。从逻辑上，把队头和队尾拼接起来。（当指针指向队尾，再往前移动一个位置，就%MaxSize）结构12345typedef struct { ElemType data[MaxSize]; int front;//指向队头元素 int rear;//指向队尾元素的下一个元素} SqQueue; 要面临的两个问题是：队列为空的条件。队列为满的条件。由于队列在增加和删除的过程中，元素在队列中的序号是变化的，所以不能像栈一样用常量-1表示。所以，我们定义q.front == q.rear即队列为空。定义(q.rear + 1) % MaxSize ==...

栈栈也是一种线性表，它也可以由顺序表，和链表来实现。只不过栈是一种被限制的线性表，它只能对栈顶（线性表的最末端的元素）进行基本操作（增删改查）。本次，主要讲栈的顺序存储结构。顺序栈结构数组data[MaxSize] 当前栈顶top 1234typedef struct { ElemType data[MaxSize]; int top;}SqStack; 操作流程图实现代码1234567891011121314151617181920212223242526272829303132333435363738394041void Init(SqStack &s) { s.top = -1;}bool IsEmpty(SqStack s) { if (s.top == -1) { return true; } return false;}bool IsFull(SqStack s) { if (s.top >= MaxSize - 1)...

Loading Database