学习笔记--图
图的定义
图（graph）是一种网状数据结构，图是由非空的顶点集合和一个描述顶点之间关系的集合组成。
其形式化定义为二元组：
Graph = （V，E）
其中：
V 是具有相同特性的数据元素的集合，V 中的数据元素通常称为 顶点（Vertex），
E是连接V中两个不同顶点（顶点对）的边的有限集合。
E = { < u , v > | P (u , v) ∩ (u,v ∈ V)}
有向图和无向图
在一个图中，如果任意两个顶点构成的偶对 (u , v) ∈ E 是无序的，即顶点之间的连线是没有方向的，则称该图为无向图（Undigrpah）。
在一个图中，如果任意两个顶点构成的偶对<u , v> ∈ E是有序的，即顶点之间的连线是有方向的，则称该图为有向图（Digrpah）。
有向图顶点之间的连线称为弧。弧有弧头和弧尾区别。
注意：无向边用“（）”，而有向边用“< >”表示。
图的存储
邻接矩阵 ： 二维数组 顺序结构
其中，wij表示边 (u , v) 或弧<u , v>上的权值；∞表示一个计算机允许的、大于所有边上权值的数。
邻接表：链表 链式存储结构
图的遍历
深度优先遍历（ DFS depth-first search ）:
类似于树的先根遍历，是树的先根遍历的推广（可以采用递归和借助栈的非递归方式实现）。
广度优先遍历（ BFS breadth-first search）:
类似于树的层次遍历，是树的按层次遍历的推广（借助队列 非递归方式实现）。
最短路径
权值最小的最短路径：迪杰斯特拉算法（Dijkstra）
版权声明：本文为shangyang原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。