弄清楚图 本章重点
1.邻接矩阵：表示顶点之间相邻关系的矩阵
邻接矩阵表示法的特点：
优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边、找顶点的邻接点等等。
缺点：n个顶点需要n*n个单元存储边; 空间效率为O(n2)。对稀疏图而言尤其浪费空间。
2.邻接表
（1）图的链式存储结构
（2）图的邻接表存储表示
1 #define MVNum 100//最大顶点数 2 3 typedef struct ArcNode//边结点 4 5 { 6 7 int adjvex;//该边所指向的顶点的位置 8 9 struct ArcNode *nextarc;//指向下一条边的指针10 11 OtherInfo info；//和边相关的信息12 13 }ArcNode;14 15 typedef struct VNode//顶点信息16 17 {18 19 VerTexType data;20 21 ArcNode *firstarc;//指向第一条依附于边的指针 22 23 }VNode，AdjList[MVNum];//AdjList表示邻接表类型24 25 typedef struct26 27 {28 29 VerTexType vexs[MVNum]; //顶点表30 31 ArcType arcs[MVNum][MVNum]; //邻接矩阵32 33 int vexnum,arcnum; //图的当前点数和边数34 35 }AMGraph; 3.图的遍历
图的遍历：从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。
！！！深搜和广搜
DFS：从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到
重点：（1）递归过程（2）为了区别顶点是否被访问，附设访问标志数组visited[n],其初值为“false”，一旦某个顶点被访问，则其相应的置被赋为“true”
BFS：在访问了起始点v之后，依次访问 v 的邻接点； 然后再依次访问这些顶点中未被访问过的邻接点； 直到所有顶点都被访问过为止。
重点：（1）分层搜索，不是递归（2）①从图中某个顶点v出发，访问v，并置visited[v]的值为true，然后将v 进队。② 只要队列不空，则重复下述处理： （1）队头顶点u出队。 （2）依次检查u的所有邻接点w，如果visited[w]的值为false，则访问w，并置visited[w]的值为true，然后将w 进队。
列出连通图
1 #include2 #include 3 4 using namespace std; 5 6 #define MAXNUM 15 7 bool check[MAXNUM] = { false}; 8 9 //建立邻接矩阵//Create Graph 10 int G[MAXNUM][MAXNUM] = { 0}; 11 int N,E;//N为顶点数，E为边数 12 13 void DFS(int ); 14 int BFS(int ); 15 void ListComponentsDFS(); 16 void ListComponentsBFS(); 17 void isvisited(); 18 void BuildGraph(); 19 20 int main() 21 { 22 //建图 23 BuildGraph(); 24 //DFS遍历连通集 25 ListComponentsDFS(); 26 isvisited(); 27 //BFS遍历连通集 28 ListComponentsBFS(); 29 return 0; 30 } 31 32 33 void BuildGraph() 34 { 35 int i,j; 36 int v1,v2;//每一行的顶点名称 37 38 cin >> N >> E;//N是顶点数，E是边数 39 40 for(i = 0;i< E;i++)//每行输出一个连通集 41 { 42 cin >> v1 >> v2;//InsertEdge 43 G[v1][v2] = 1;//联通 置为1 44 G[v2][v1] = 1; 45 46 } 47 } 48 49 //DFS 50 void DFS(int v) 51 { 52 check[v] = true;//已被访问置为true 53 cout << v <<" "; 54 for(int i=0;i
