共有回帖数 0 个
-
1 每条边都有方向-有向图，反之则为无向图。
2 在有向图中，通常将边称作弧，含箭头一端为弧头，另一端为弧尾，记作vi,vj。
3 若有向图有n个顶点，则最多有n(n-1)条弧，又将具有n(n-1)条弧的有向图称作有向完全图。
4 以顶点v为弧尾的弧的数目称作顶点v的出度，以顶点v为弧头的弧的数目称作顶点v的入度。
5 具有n个顶点的有向图可以用一个n*n的方形矩阵表示，假设该矩阵的名称为M，则当vi,vj是该有向图中的一条弧时，M[i,j]=1;否则M[i,j]=0。
6 具有n个顶点的无向图也可以用一个n*n的方形矩阵表示；假设该矩阵的名称为M，则当(vi,vj)是该无向图中的一条边时，M[i,j]=M[j,1]=1,否则M[i,j]=M[j,i]=0。
7 常见的图遍历方式有两种：深度优先遍历，广度优先遍历。
8 深度优先遍历的思想类似于数的先序遍历。
9 深度优先遍历-从某个顶点v出发，访问该顶点，然后依次从v的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有与v有路径相通的顶点都被访问完为止。
10 图的广度优先遍历-从顶点v出发，访问v之后，依次访问v的所有未被访问过的邻接点，然后再访问每个邻接点的邻接点，且访问顺序应保持先被访问的顶点其邻接点也优先被访问，直到图中的所有顶点都被访问为止。
楼主 2016-05-26 12:19 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
