麻将网站开发公司品牌策划公司排行榜
树和图的概念
图是一种特殊的数据结构，由点和边构成，它可以用来描述元素之间的网状关系，这个网状没有顺序，也没有层次，就是简单的把各个元素连接起来。
图的概念和基本性质
图(graph)：图(graph)由边(edge)的集合及顶点(vertex)的集合组成。通常记为：G=(V,E)。对于两个图G和G’，如果G’的顶点集合与边集合均为G的顶点集合与边集合的子集，那么称G’是G的子图。子图实际上就是一张图里面小一点的图，也可以是点，不难理解。
图常用来表示“多对多”的关系，如常说的：六度空间理论(Six Degrees Separation)
顶点(vertex)的属性：
度数(degree)，与该顶点相关联的总边数，一个图G的总度数d(V)等于总边数2倍：2E。当图的边具有方向时，一个顶点又分为出度(out-degree)和入度(in-degree)，出度是以该顶点为起点的边数，入度是以该顶点为终点的边数。
阶数(order)，图G中顶点集V的大小为G的阶数。
边又称为线(line)或弧(arc)，边(u,v)中表示u和v邻接(adjacent)，(u, v) ∈ E，
边(edge)的属性：
一条边是一个顶点对(u,v)，u, v ∈ V，按照图的顶点对是否有序，顶点对有序的图称为有向图(directed graph, digraph)，此时边(u,v)和(v,u)是两条不同的边，顶点对无序的图称为无向图(undirected graph)，此时边(u,v)和(v,u)是两条相同的边，无向图可看作一个特殊的有向图
具有成分的边包含：权(weight)、值(cost/value)，此时图由可分为有权图(weighted graph)和无权图(unweighted graph)，无权图可以看作是所有边权值相同的有权图。
路径(path)，一条路径是一个顶点序列u1, u2, u3, …, un，(ui, u(i+1)) ∈E，1<=i
简单路径：路径上所有顶点互异，起点和终点可以相同
环或圈(cycle)，此时u1=un，而且路径长至少为1，有向图(u,v)和(v,u)是一个圈，无向图(u,v)和(v,u)通常不被认为是一个圈。其中无圈图(acyclic graph)中没有圈，无圈有向图又称为DAG(directed acyclic graph)
自环边(self loop)，两个顶点都相同的边。
重边或平行边(parallel edges)，连接两个顶点的边数超过一条，又称为多重边(multiple edges)
连通图(connected graph)，无向图中每个顶点到任意顶点都存在一条路径，连通的有向图称为强连通(strongly connected)，非连通的有向图，去掉方向其基础图(underlying graph)是连通的，则成为弱连通的(weakly connected)
完全图(complete graph)，图中任意一对顶点都存在一条边
稀疏图(sparse graph)，每个顶点的度数较小的图
图的基本基本概念
顶点的度：无向图中连着顶点的边的数目。
顶点的入度和出度：有向图中，以这个顶点为起点的边的数量称为这个顶点的出度；以这个顶点为终点的边称为这个顶点的入度。
边权：边的费用，可以形象的理解为“过路费”。对于一张存在边权的图，我们称为“带权图”。
连通：如果图中两点U,V之间存在一条由U经过若干边、点到达V的路径，则称U，V是连通的。
回路：起点和终点相同的路径，称为“回路”或“环”。另外，不存在环的有向图称为Directed Acyclic Graph(DAG)。
完全图：每个点都与其它所有的点有连边的图。
无向图：图的边没有方向，可以双向。
有向图：图的边有方向，只能按箭头方向从一点到另一点。
网络：带权重的图
连通：如果从v 到w存在一条(无向)路径，则称v和w是连通的
路径：v到w的路径是一系列顶点的集合，其中任意一对相邻的顶点间都有图中的边。
路径的长度：是路径中的边数(如果带权，则是所有边的权重和)。如果v和w之间的所有顶点都不同，则称简单路径
连通图：图中任意两顶点都连通
连通分量：无向图的极大连通子图
极大顶点数：再加一个顶点就不连通了
极大边数：包含子图中所有顶点相连的所有边
强连通：有向图中顶点v和w之间存在双向路劲，则称v和w是强连通的
强连通图：有向图中任意两顶点均强连通
弱连通图：不符合强连通图的条件，但是若是将边的方向都去掉，如果是连通的，则称为弱连通图
强连通分量：有向图的极大强连通子图
图的简单应用
图的应用很广泛，这里举几个简单的例子。
航空系统：顶点表示机场，边表示时间、距离或飞行的费用，一般最好有强连通的航空系统，另外常见的需求问题有：求任意两个机场的最佳航线。
交通流：顶点表示街道的交叉口或红绿灯点，边表示速度限度或车辆容量，这时可以求最可能参数交通瓶颈的位置，或找出一条最短路。
社交网络：顶点表示用户，用户的活动、推荐或好友代表边，这样可以表示一个完整的社交用户网络。
电商推荐系统：顶点表示用户已浏览、收藏、购物过等相关的商品，边表示两个商品的相似性，可表示为有权图，权值为相似性的大小。
另外图论又可用于研究物理学和化学中的分子
图的遍历
深度优先搜索(Depth Firsh Search, DFS)：走一步，看一步，走不通后返回到上一个能走通的结点
广度优先搜索(Breadth First Search, BFs)：出队一个，访问一圈，访问的同时入队，相当于树的层序遍历(计划性非常强，个人感觉用这种遍历方式更好一些)
本系列主要讲二叉树，关于图，推荐阅读文章有：