数据结构--图

1.图的基本概念图这东西说白了就是“一堆东西”和“这些东西之间的连接”。我用最生活化的例子给你拆解图长什么样你可以在纸上随手画几个圈代表东西再用线把圈连起来代表关系。画出来的这张网就是“图”。图里的两个基本零件1.顶点点就是那些圈。代表具体的“东西”。比如人、车站、网页。2.边线就是连接圈的线。代表“关系”。比如朋友关系、铁路线。图主要分两种看你画的线带不带箭头无向图线是没有箭头的。代表“双向关系”。比如微信好友——你加了我咱俩就是好友关系是相互的。有向图线是带着箭头的。代表“单向关系”。比如微博关注——你关注了明星但明星不一定关注你箭头只能从你指向明星。带权图图还可以给线“标价”如果线上带个数字比如距离、时间、花费这就叫带权图。比如高德地图上的路线图点是路口线是马路线上的数字代表堵车需要几分钟。完全图说白了就是“团伙里每个人都互相认识”。在一个图里任意两个点之间都有一条线连着没有任何遗漏这就叫完全图。在有n个顶点的无向图中若有n * (n-1)/2条边即任意两个顶点之间有且仅有一条边则称此图为无向完全图。在n个顶点的有向图中若有n * (n-1)条边即任意两个顶点之间有且仅有方向相反的边则称此图为有向完全图。邻接顶点邻居就是直接跟你用线连着的那些点。比如你微信好友列表里那些直接加了微信的人就是你的“邻接顶点”。注意只有直接连着才算朋友的朋友不算。顶点的度好友数量你身上连着几条线度就是几。无向图里线没箭头度 你直接连的邻居个数。比如你有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因此邻接矩阵(二维数组)即是先用一个数组将定点保存然后采用矩阵来表示节点与节点之间的关系。注意1.无向图的邻接矩阵是对称的第i行(列)元素之和就是顶点i的度。有向图的邻接矩阵则不一 定是对称的第i行(列)元素之后就是顶点i的出(入)度。2.如果边带有权值并且两个节点之间是连通的上图中的边的关系就用可以用权值代替如果两个 顶点不通则可使用无穷大代替。3.用邻接矩阵存储图的优点是能够快速知道两个顶点是否连通缺陷是如果顶点比较多边比较少时矩阵中存储了大量的0成为系数矩阵比较浪费空间并且要求两个节点之间的路径不是很好求。2.2邻接表使用数组表示顶点的集合使用链表表示边的关系。注意无向图中同一条边在邻接表中出现了两次。如果想知道顶点vi的度只需要知道顶点 vi边链表集合中结点的数目即可。有向图中每条边在邻接表中只出现一次与顶点vi对应的邻接表所含结点的个数就是该顶点的出度也称出度表要得到vi顶点的入度必须检测其他所有顶点对应的边链表。3.图的遍历说白了就是怎么把图里所有的点都走一遍不重不漏。就像你进了个迷宫要把每个房间都看一遍关键问题就是怎么走才不走回头路。两种最基本的方法图遍历就两种核心思路一个先扒拉最近的(BFS)一个先一条道走到黑(DFS)1. BFS广度优先搜索—— 一层一层剥洋葱从起点开始先逛完所有邻居再逛邻居的邻居像水波纹一样一圈一圈往外扩。工具队列先进先出排队办事特点稳扎稳打先近后远。举个例子社交网络找朋友你起点先看你的微信好友第一层看完所有好友后再看好友的好友第二层再看好友的好友的好友第三层……BFS 的特点找到的路径一定是最短的因为是一层一层扩的。导航软件找最短路径底层是 BFS或者带权重的 Dijkstra。2. DFS深度优先搜索—— 不撞南墙不回头从起点出发选一条路一直往下走走到死胡同没路了再退回来换下一条路继续走。工具栈后进先出或者递归递归本质上就是栈。特点一条道走到黑不行就回退举个例子走迷宫你进了迷宫一直扶着右手边的墙走走到死胡同就原路退回到上一个岔路口换另一条没走过的路继续走到底反复这么干直到逛完所有房间DFS 的特点实现简单递归一写就完事但找到的路径不一定是最短的它先探到底不管远近。重要提醒必须打已访问标记无论用 BFS 还是 DFS都得给每个点贴个标签我来过没。因为图里可能有环比如 A—B—C—A如果不标记你会死循环在环里转一辈子出不来。