图什么是图图是由顶点(Vertex)和边Edge组成的结构。为什么会出现图这种结构在现实生活中的关系不全是以“一对一”或”一对多“而是复杂的多对多。经典的”一对一““一对多””多对多“关系有1.线性结构数组链表栈队列 只能出现一对一关系。2.树形结构 一对多3.图结构 可以表示多对多的关系图 --有向图 --无向图无向图首先我们先来讲无向图无向图 顶点没有方向的边。假设有4个顶点V0,V1,V2,V3边集{(V0,V1), (V0,V2), (V1,V3), (V2,V3)}V0 —— V1| |V2 —— V3无向图的核心术语1.顶点的度 度与该顶点相连的边的数量V0连接 V1 V2 那么V0的度为22.路径3.环/回路无向图的特例1.完全图 每对不同顶点之间都有一条边直接相连。2.树 连通 无环的无向图3.森林 多个树的集合无向图的存储领接矩阵和邻接表1.领接矩阵V0 V1 V2 V3V0 0 1 1 0V1 1 0 0 1V2 1 0 0 1V3 0 1 1 02.邻接表V0 → [V1] → [V2]V1 → [V0] → [V3]V2 → [V0] → [V3]V3 → [V1] → [V2]无向图的遍历1.深度优先遍历DFS2.广度优先遍历 (BFS)有向图有向图 顶点有方向的边G (V,E) V顶点集合 E有向边的集合每条边是一个有序对顶点V {V0,V1,V2,V3} 边E {v0,v1,vo,v2,v0,v3,v1,v3}V0/↓ ↘↓ ↓ ↓V1 V2↓ /V3有向图的核心数据出度和入度出度 从顶点出去边的数量入度 进入该顶点边的数量强连通分量在有向图当中如果从顶点A可以到达顶点B并且从顶点B也可以到达顶点A那么称A和B是强连通性的。拓扑排序把有向无环图DAG的顶点排成一个线性序列如果存在边A - B 那么A在序列中一定会出现在B之前。有向图不意味着遍历顺序也固定图的方向性固定边有方向性 只可以单向移动。图的遍历顺序不固定会利用回溯的方式。