数据结构（第六章）

图上
图&＃xff08;上&＃xff09;
第一讲
一.什么是图
图其实是一种很抽象的东西&＃xff0c;它可以表示很多东西&＃xff0c;举个例子&＃xff0c;就你的朋友圈而言&＃xff0c;你所交的朋友就可以构成一个图&＃xff0c;生活中有很多很多的例子&＃xff0c;因此图是比较复杂的&＃xff0c;它表示的是“多对多"的关系。
回到数据结构&＃xff0c;图一般包含两个要素&＃xff1a;
一组顶点&＃xff1a;通常用V表示顶点集合&＃xff1b;
一组边&＃xff1a;通常用E表示边的集合&＃xff1b;
边是顶点对&＃xff1a;&＃xff08;v&＃xff0c;w&＃xff09;属于E&＃xff0c;其中圆括号表示无向边&＃xff0c;类似于一个这样的东西&＃xff0c;——&＃xff0c;双行线。
有向边表示v——>w,它是单行线。
我们不考虑重边和自回路&＃xff0c;重边容易理解&＃xff0c;自回路是什么呢&＃xff1f;自回路其实就是一个由自己指出的边然后又指回自己&＃xff0c;这就是自回路。
二.图的表示方法
作为程序员的我们&＃xff0c;怎么用程序来表示一个图呢&＃xff1f;
这里我们要引出一个新的概念叫邻接矩阵。
邻接矩阵其实就是存放关系的矩阵&＃xff0c;有关系则为1&＃xff0c;没有关系则为0&＃xff1b;当然数值不一定用01表示&＃xff0c;你可以用任何数。这里来放一个图就一目了然了

在图中&＃xff0c;我们很清楚的看到&＃xff0c;如果v1与v2有关系&＃xff0c;则为1&＃xff0c;没有关系就为0&＃xff0c;然后图中的一条红线&＃xff0c;红线经过的数字全为0&＃xff0c;这是为什么呢&＃xff0c;因为我们没有自回路&＃xff0c;也就是没有自己指向自己的。而且以红线为轴&＃xff0c;两边是对称的&＃xff0c;因为我们是无向边&＃xff0c;很好理解。
同时我们会发现既然是对称的&＃xff0c;那么我们就没必要存放两个一样的东西&＃xff0c;这样会浪费了一半的空间呀&＃xff0c;与此同时&＃xff0c;完善的方法就诞生了。
我们可以用一个长度为N&＃xff08;N&＃43;1&＃xff09;/2的一维数组存储&＃xff0c;存储的顺序是按照从上至下&＃xff0c;从左至右的&＃xff0c;
那么i与j的关系如何呢&＃xff0c;通过计算也就是规律&＃xff0c;可得 数组的下标为&＃xff08;i*&＃xff08;i&＃43;1&＃xff09;/2&＃43;j&＃xff09;&＃xff0c;然后我们看它对应的数组元素的值&＃xff0c;就可以判断有无关系了。
邻接矩阵的缺点&＃xff1a;很明显&＃xff0c;浪费空间&＃xff0c;但是也是相对而言的&＃xff0c;对于稀疏图&＃xff0c;也就是顶点很多&＃xff0c;边很少&＃xff0c;显然很浪费空间也浪费时间&＃xff0c;但是对于稠密图&＃xff0c;特别是对于完全图&＃xff08;一个点和所有点都有关系&＃xff09;&＃xff0c;还是很合算的。
看完了邻接矩阵&＃xff0c;看看邻接表吧
邻接表&＃xff1a;G[N]为指针数组&＃xff0c;对应矩阵每行一个链表&＃xff0c;只存非0元素&＃xff0c;也就是说只存有关系的。

大概就长这个样子吧&＃xff01;让我们想一想&＃xff0c;它真的比邻接矩阵要好吗&＃xff1f;
我们仔细分析&＃xff0c;一个结点既要存指针&＃xff0c;还要存有关系的下标&＃xff0c;就占了两个域了&＃xff0c;然后每一个结点都有&＃xff0c;所以也无法避免重复的情况&＃xff0c;因此它也是浪费空间的。但是&＃xff0c;它很方便找出所有的相邻的点&＃xff0c;比邻接矩阵还是要节约一些空间的&＃xff0c;但也存在浪费。
第二讲
一.图的遍历
从图中某这一点出发访遍图中其余顶点&＃xff0c;且每一个顶点仅被访问一次&＃xff0c;这一过程叫做图的遍历。
对于图的遍历来说&＃xff0c;为了避免陷入死循环&＃xff0c;设计出两种遍历方案&＃xff1a;DFS&＃xff08;深度优先搜索&＃xff09;&＃xff0c;BFS&＃xff08;广度优先搜索&＃xff09;。
二.深度优先搜索
具体思想&＃xff1a;打个比方&＃xff0c;比如我们需要在100间房子里找一把钥匙&＃xff0c;深度优先搜索就是&＃xff0c;从任意的一间房子开始&＃xff0c;把该房间里的所有地方都搜遍了&＃xff0c;才肯离开&＃xff0c;然后在另一间房间继续按照此方法找&＃xff0c;知道找到为止。
深度优先搜索其实就像似一棵树的先序遍历&＃xff0c;它是从图上的某个顶点v出发&＃xff0c;访问此顶点&＃xff0c;然后从v的未被访问的邻接点出发深度优先遍历图&＃xff0c;直到所有顶点都被访问到。如果有些顶点没有访问到&＃xff0c;则另选图中的一个未被访问的顶点作为起始点&＃xff0c;重复上述过程直到所有顶点被访问到。
邻接矩阵

void DFS(MGraph G,int i)//递归算法
{int j;visit[i]&＃61;1;//标记为已访问printf("%c",G.data[i]);for(j&＃61;0;j<G.num;j&＃43;&＃43;){if(G.map[i][j]&&!visit[j])//相邻的点&＃xff0c;未被访问&＃xff0c;直接DFSDFS(G,j);}
}
void DFSL(MGraph G)//遍历操作
{int i;for(i&＃61;0;i<G.num;i&＃43;&＃43;){visit[i]&＃61;0;}for(i&＃61;0;i<G.num;i&＃43;&＃43;){if(!visit[i])DFS(G,i);}
}


邻接表

void DFS(MGraph G,int i)//递归算法
{MGraph *p;visit[i]&＃61;1;printf("%c",G->List[i].data);p&＃61;G->List[i].first;while(p){if(!visit[p->ad]){DFS(G,p->ad);//访问邻接点}p&＃61;p->next}
}
void DFSL(MFGraph G)//遍历操作
{int i;for(i&＃61;0;i<G.num;i&＃43;&＃43;){visit[i]&＃61;0;}for(i&＃61;0;i<G.num;i&＃43;&＃43;){if(!visit[i])DFS(G,i);}
}


三.广度优先搜索
具体思想&＃xff1a;还是以房间为例&＃xff0c;广度优先搜索是先把家里钥匙可能掉的地方找一遍&＃xff0c;一步一步扩大面积去找&＃xff0c;扩大查找范围&＃xff0c;知道找到为止。广度优先搜索就类似与树的层序遍历。
邻接矩阵

void BFS&＃xff08;MGraph G)
{int i,j;Queue Q;for(i&＃61;0;i<G.num;i&＃43;&＃43;)//初始化全部没有访问visit[i]&＃61;0;InitQueue(&Q);for(i&＃61;0;i<G.num;i&＃43;&＃43;){if(!visit[i])//未访问进入{visit[i]&＃61;1;printf("%c",g->data[i]);EnQueue(&Q,i);while(!QueueEmpty(Q)){DeQueue(&Q,&i);for(j&＃61;0;j<G.num;j&＃43;&＃43;){if(G.map[i][j]&&!visit[j]){visit[j]&＃61;1;printf("%c",G->data[j]);EmqQueue(%&Q,j);}}}}}
}


邻接表

void BFS&＃xff08;MGraph G)
{int i;MGraph *p;Queue Q;for(i&＃61;0;i<G.num;i&＃43;&＃43;){visit[i]&＃61;0;}InitQueue(&Q);for(i&＃61;0;i<G.num;i&＃43;&＃43;){if(!visit[i]){visit[i]&＃61;1;printf("%c",G->ad[i].data);EnQueue(&Q,i);while(!QueueEmpty(Q)){DeQueue(&Q,&i);p&＃61;G->ad[i].first;while(p){if(!visit[p->da]){visit[p->da]&＃61;1;printf("%c",G->ad[p->da].data);EnQueue(&Q,p->da);}p&＃61;p->next;}}}}
}