无向图的邻接矩阵

阅读数:87 评论数:0

跳转到新版页面

算法/数据结构

定义：设G=（V，E）的顶点集为V={v1,v2,...}用a（i,j)表示G中顶点vi到vj的边数。称矩阵A（G)=（aij）为G的邻接矩阵。

（1）是一个对称矩阵

（2）若为无环图，则第i行（列）的无素之和等于顶点vi的度数

在邻接矩阵A的幂矩阵中，每个元素有待定的含义，

定理：设G是具有n个结点集{v1,v2,...，vn}的图，其邻接矩阵为A，则A^l(l=1,2,...)的（i,j)项元素是从vi到vj的长度等于l的的路的总数。

Trie，又称单词查找树或键树，是一种树形结构，是一种哈希树

单模式VS多模式（1）单模式单模就是给你一个单词，然后给你一个字符串，问你这个单词是否在这个字符串中出现过（匹配）（2）多模式给你

1、已知前序、中序求后序（1）确定根（前序中第一个结点为根），确定左子树，确定右子树（在中序中，找到前序所示根，其左为左子树，其右为右子树）（2）在左子树中递

1、B树 B 树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树。与红黑树很相似，但在降低磁盘I/0操作方面要更好一些。 B树与红黑树最大的不同在于，B树的结点可以有许多子女

Log Structured Merge Tree，简单地说，LSM的设计目标是提供比传统的B+树

一、二叉树 Binary Search Tree 1、二叉树性质（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。（2）若它的右子树不空，则右子树上的所有结点的值均大于它的根结点