1.图的基本概念
图这东西，说白了就是“一堆东西”和“这些东西之间的连接”。
我用最生活化的例子给你拆解：
图长什么样？
你可以在纸上随手画几个圈（代表东西），再用线把圈连起来（代表关系）。画出来的这张网，就是“图”。
图里的两个基本零件
1.顶点（点）：
就是那些圈。代表具体的“东西”。
比如人、车站、网页。
2.边（线）：
就是连接圈的线。代表“关系”。
比如朋友关系、铁路线。
图主要分两种（看你画的线带不带箭头）
无向图
线是没有箭头的。代表“双向关系”。
比如微信好友——你加了我，咱俩就是好友，关系是相互的。
有向图
线是带着箭头的。代表“单向关系”。
比如微博关注——你关注了明星，但明星不一定关注你，箭头只能从你指向明星。
带权图
图还可以给线“标价”如果线上带个数字（比如距离、时间、花费），这就叫带权图。
比如高德地图上的路线图，点是路口，线是马路，线上的数字代表堵车需要几分钟。
完全图
说白了就是“团伙里每个人都互相认识”。
在一个图里，任意两个点之间都有一条线连着，没有任何遗漏，这就叫完全图。
邻接顶点（邻居）
就是直接跟你用线连着的那些点。
比如你微信好友列表里，那些直接加了微信的人，就是你的“邻接顶点”。
注意：只有直接连着才算，朋友的朋友不算。
顶点的度（好友数量）
你身上连着几条线，度就是几。
无向图里（线没箭头）：度 = 你直接连的邻居个数。比如你有10个微信好友，你的度就是10
有向图里（线带箭头）：度要拆成两半；
入度：有多少条箭头指向你（别人关注你）。
出度：有多少条箭头从你指出去（你关注了别人）。
比如微博上，你关注了50人（出度=50），有100人关注你（入度=100）。
路径（走过的路线）
从一个点出发，沿着线走到另一个点，走过的这条“路”就叫路径。
比如从你家（A点）到公司（D点），中间经过地铁站B和公交站C，那A→B→C→D就是一条路径。
注意：路径可以很长，也可以很短，中间经过的点不能重复（简单路径），也可以绕圈圈（回路）。
路径长度（走了几步）
路径上经过的“边的条数”就是长度，不是距离米数。
比如路径A→B→C→D，经过了3条边（A-B、B-C、C-D），路径长度就是3。
如果边上有数字（带权图），那路径长度指数字之和，比如导航里总耗时10分钟。
连通图（大家都能联系上）
任意两个点之间，至少能找到一条路走过去（不管绕多远）。
比如中国的地铁网络，只要任意两个站之间都能坐地铁到达（可能换乘很多次），那这个地铁网络就是连通图。
反例：如果把武汉和长沙的地铁分开建，互相不通，那就是两个连通分量（各自是连通的，但整体不连通）。
注意：连通图不要求两个点直接连着（不要求是邻接顶点），只要绕路能到就行。
强连通图（有向图里的“互通有无”）
专门针对带箭头的图，任意两个点之间，不仅你能到我，我也能到你（双向都能走通）。
比如城市里的双向车道路网，你能开车到我家，我也能开车到你家，这就是强连通。
反例：单向车道，你从A能到B，但从B回不了A（因为箭头是单向的），那整体就不是强连通。
对比：
无向图里，只要连通，大家都能互相走到（因为线没方向），所以连通图 = 强连通图。
有向图里，连通分两种：
1.强连通：双向都能走到。
2.弱连通：把箭头去掉后是连通的，但按箭头方向走不通（比如A→B→C，去掉箭头是连的，但按箭头方向从C去不了A）。
生成树（连通图里的“精简骨架”）
从一个连通图里，挑出最少的边，让所有点还是连着的（而且不能有环，也就是不能绕圈子）。
特点：
假如有n个点，生成树一定有且仅有n-1条边（刚好够把所有点串起来）。
没有回路（不会绕回原点）。
比如你家到公司有好几条路（构成连通图），但你要设计一条最省路的快递路线，保证每个站点都能送到，但不绕路——这条路线就是一棵生成树。
最小生成树
如果每条边都有成本（比如修路费），你选的生成树里总成本最小的那棵，就叫最小生成树。（Kruskal或Prim算法解决的就是这个）。
2.图的存储结构
因为图中既有节点，又有边(节点与节点之间的关系)，因此，在图的存储中，只需要保存：节点和边关系即可。节点保存比较简单，只需要一段连续空间即可，那边关系该怎么保存呢？
2.1邻接矩阵
因为节点与节点之间的关系就是连通与否，即为0或者1，因此邻接矩阵(二维数组)即是：先用一个数组将定点保存，然后采用矩阵来表示节点与节点之间的关系。
2.2邻接表
使用数组表示顶点的集合，使用链表表示边的关系。
注意：
无向图中同一条边在邻接表中出现了两次。如果想知道顶点vi的度，只需要知道顶点 vi边链表集合中结点的数目即可。
有向图中每条边在邻接表中只出现一次，与顶点vi对应的邻接表所含结点的个数，就是该顶点的出度，也称出度表，要得到vi顶点的入度，必须检测其他所有顶点对应的边链表。
3.图的遍历
两种最基本的方法
图遍历就两种核心思路，一个"先扒拉最近的"(BFS)，一个"先一条道走到黑"(DFS)：
1. BFS（广度优先搜索）—— "一层一层剥洋葱"
从起点开始，先逛完所有"邻居"，再逛邻居的邻居，像水波纹一样一圈一圈往外扩。
工具：队列（先进先出，排队办事）特点：稳扎稳打，先近后远。
举个例子（社交网络找朋友）：
你（起点）先看你的微信好友（第一层）
看完所有好友后，再看好友的好友（第二层）
再看好友的好友的好友（第三层）……
BFS 的特点：找到的路径一定是最短的（因为是一层一层扩的）。导航软件找最短路径，底层是 BFS（或者带权重的 Dijkstra）。
2. DFS（深度优先搜索）—— "不撞南墙不回头"
从起点出发，选一条路一直往下走，走到死胡同（没路了）再退回来，换下一条路继续走。
工具：栈（后进先出，或者递归，递归本质上就是栈）。特点：一条道走到黑，不行就回退
举个例子（走迷宫）：
你进了迷宫，一直扶着右手边的墙走
走到死胡同，就原路退回到上一个岔路口
换另一条没走过的路，继续走到底
反复这么干，直到逛完所有房间
DFS 的特点：实现简单（递归一写就完事），但找到的路径不一定是最短的（它先探到底，不管远近）。
重要提醒：必须打"已访问"标记
无论用 BFS 还是 DFS，都得给每个点贴个标签："我来过没"。
因为图里可能有环（比如 A—B—C—A），如果不标记，你会死循环，在环里转一辈子出不来。
