定义

• 加上数字（权重）就成了网络。

图的表示

邻接矩阵

• 对角线必须全部是0，因为我们不允许自回路
• 对称矩阵。0到3有边，3到0也有边。但是这样就浪费了一半的空间。

  

• 对于有向图来说，有入度和出度。

• 邻接矩阵的缺点：浪费空间，如果顶点很多边很少的话；浪费时间，在统计边的时候，如果很多都是没边的话。

• 完全图：任意两个顶点间都有边，边数达到极大。

  邻接表

  

• 定义一个长度为顶点数的数组，存放指向一个链表的头指针，这个头指针指向的链表存放着所有和顶点相连的顶点。
• 其实也并不节省空间，因为边同样是被存了两次，链表中每个结点都要有数据域和指针域，如果这个图是网络的话还要加上权重，所以一定要够稀疏才合算。

深度优先搜索

• 利用堆栈来做。
• 其实就是把每一条路都走一遍，走进死胡同则结束递归进入最近一个分叉路口的下一个循环，即另一条岔路。
• 可以把深度优先搜索想象成是一组发散的线。
• 算法实例：第六讲->6.2第1小节

  广度优先搜索

  

• 利用队列来做。
• 其实就是把结点的所有邻接点都入队，然后往这边岔路走几步，往那边岔路也走几步。就像长了分身一样，这条岔路前进一点，那条岔路也前进一点，一圈一圈的往外走，只要出口被包围到圈子里就结束循环。
• 可以把广度优先搜索想象成是辐射圈。
• 算法实例：第七讲->6.2第3小节

  两种遍历的比较

• 算法实例：第七讲->6.2第5小节

  图的连通

  

• 不简单的路径就是指路径上有环，有环则称为回路。

• 所有连通的顶点都包含在里面
• 连通分量指的是无向图

• 是双向路径而不是双向边。
• 弱连通：不是强连通，但是抹掉方向以后是连通的。
• D自己是一个单独的强连通分量。

• 第二个算法就是用来找所有的连通分量的