初赛-图的概念
一、什么是图？
点用边连起来就叫做图，严格意义上讲，图是一种数据结构，定义为：graph=（V，E）。
V是一个非空有限集合，代表顶点（结点），E代表边的集合。
二、图的一些定义和概念
1. 有向图：图的边有方向，只能按箭头方向从一点到另一点。(a)就是一个有向图。
2. 无向图：图的边没有方向，可以双向。(b)就是一个无向图。
3.结点的度：无向图中与结点相连的边的数目，称为结点的度。
4.结点的入度：在有向图中，以这个结点为终点的有向边的数目。
5.结点的出度：在有向图中，以这个结点为起点的有向边的数目。
6.权值：边的“费用”，可以形象地理解为边的长度。
7.连通：如果图中结点U，V之间存在一条从U通过若干条边、点到达V的通路，则称U、V 是连通的。如果图中任意两点都是连通的，那么图被称作连通图。
8.回路：起点和终点相同的路径，称为回路，或“环”。
9.完全图：一个n 阶的完全无向图含有n*(n-1)/2 条边；一个n 阶的完全有向图含有n*(n-1)条边；
10.强连通分量：有向图中任意两点都连通的最大子图。下图中1-2-5构成一个强连通分量
1.二维数组邻接矩阵存储
定义int G[101][101];
G[i][j]的值，表示从点i到点j的边的权值，定义如下：
上图中的3个图对应的邻接矩阵分别如下：
图的遍历分为深度优先遍历和广度优先遍历两种方法。
1.深度优先遍历
深度优先遍历与深搜DFS相似，从一个点A出发，将这个点标为已访问visited[i]:=true;，然后再访问所有与之相连，且未被访问过的点。当A的所有邻接点都被访问过后，再退回到A的上一个点（假设是B），再从B的另一个未被访问的邻接点出发，继续遍历。
例如对右边的这个无向图深度优先遍历，假定先从1出发，程序以如下顺序遍历：
1→2→5，然后退回到2，退回到1。
从1开始再访问未被访问过的点3 ，3没有未访问的邻接点，退回1。
再从1开始访问未被访问过的点4，再退回1 。
起点1的所有邻接点都已访问，遍历结束。
2.广度优先遍历
广度优先遍历并不常用，从编程复杂度的角度考虑，通常采用的是深度优先遍历。
广度优先遍历和广搜BFS相似，因此使用广度优先遍历一张图并不需要掌握什么新的知识，在原有的广度优先搜索的基础上，做一点小小的修改，就成了广度优先遍历算法。