这是《计算机算法分析与设计》课件第二章“图与遍历算法”内容的总结。
1.关于有向图
有向图的表示也可以用邻接矩阵和关联矩阵，邻接矩阵的表示和无向图一样，但是关联矩阵为指明边的方向，只用 0,1 两个元素是不够的，可以增加一个元素-1。若i是j的始点，赋值为1，若i是j的终点，赋值为-1，其余赋值为0。
有向图 D 说是连通的是指其基础图是连通的。如果 D 中任意两个顶点都是相互有向可达的，则说有向图 D 是双向连通的（或叫强连通）
2.关于赋权图
描述一个赋权图时，如果顶点i、j之间有一条边连接，而且权值为a，则其邻接矩阵中的（i，j）元素为a（而不再是1），其余元素统一取微0或一个充分大的数。