Brains


Algorithm、Machine Learning、Search、cloud computing
on Algorithm, 图的存储结构

图的基础数据结构与遍历算法

快要面临实习了,最近打算专攻一些算法,这篇主要回顾一下图的基本算法,以及基本的的数据结构。 简介 本文主要回顾本科所学的关于图的一些数据结构和基本算法,图在实际问题中应用很广泛,是一种非常重要的数据结构。第一部分叙述图的定义以及基本表示形式,第二部分叙述关于图的一些常用算法。 图的描述 图的定义 图是顶点的非空集合和顶点之间边的非空集合组成的,常用G(V,E)表示,其中G表示一个图,V代表图G中顶点的集合,E表示图中边的集合。 图主要分为两类:一种是有向图,一种是无向图。其中有向图是顶点到顶点之间的边是有方向的,而无向图说明顶点间的边是不区分方向的。还有一种特殊的图称为网:顶点间的每条边有一个权重值。 图的基本表示 邻接矩阵 邻接矩阵可以非常简单明了的描述一个图。其主要思想是用一个二维数组描述图中顶点间的关系。它也可以很方便的描述网,其中无向图的邻接矩阵是沿对角线对称的。图的邻接矩阵的C语言描述如下所示: #define MAXVEX 100 // 最大顶点数 #define MAXWEIGHT 65535 // 边的最大权重 typedef char VertextType; // 顶点表示 typedef int EdgeTypde; // 边的表示
Read More