20172316 2018-2019-1《程序设计与数据结构》第九周学习总结

教材学习内容总结

第十五章图

图：

图同样是一种数据结构，和树一样是非线性的，我觉得可以理解为它是没有父子概念、结点可以连接多个结点的树

图的分类：

无向图（undirected graph），形如上图，两个结点之间的边没有方向，仅表示两结点存在关系。

有向图（directed graph），两结点之间的边拥有箭头来指示方向，在表述两点关系时，不能颠倒顺序（如上图，B→A，但不可以A→B）

连通图（connected graph），图中任意两结点都存在一条路径，称为连通。对于无向图和有向图定义都相同，但要注意若在有向图中存在没有入度的结点，那就是不连通的。

网络（加权图），每条边上都有权重或代价的图，

其他定义：

出度、入度，对于有向图中的A来说，A→B与B→A一个是出一个是入，两者有所区分，定义由A指向其他结点的边的数量是A的出度，反之是入度。

邻接矩阵：使用二维数组存储两顶点之间的连接情况，所以无向图的矩阵始终是对称的，有向图则不一定。
图一的邻接矩阵：

	A	B	C	D	E
A	F	T	T	F	T
B	T	F	T	T	F
C	T	T	F	T	F
D	F	T	T	F	T
E	T	F	F	T	F

常用图的算法

遍历：图的遍历分类两类：广度遍历和深度遍历
对于如图所使的图我们选定A为起始顶点：广度遍历会以A为中心辐射状遍历：A BCEF IDG H；
而深度遍历会沿着一条一条的路径分别遍历直到所有路径走完：A B CIDH EGF。
（具体遍历过程可能并非如此，但规律不变）

测试连通性：既有连通图又有不连通图，如何测试一个图的连通性呢？
如果一个图的遍历结果的顶点个数少于图中所有结点个数，那就说明有一些顶点不存在和其他结点相连的路径，也就是缺少连通性了。

最小生成树：树是图的一种，生成树是一个含有图中所有顶点和部分边（可能不是所有边）的树。而最小生成树是对于加权图而言的，一棵生成树的边的权重总和小于等于同一个图中其他任意一棵生成树的，就是最小生成树。

教材学习中的问题和解决过程

既然通过遍历的完整性来测试图的连通性，对于一个不连通的图，如何完整地遍历出它来呢？

书本上测试连通性时，使用了广度优先遍历的方法，将每一个顶点都作为起始顶点遍历了一次，虽然每次遍历都不是完整的，我的想法是：取它们结果的并集就可以得到所有顶点了。

找到一段C语言的代码，重点在BFS1方法上，它确实遍历了n遍，和我的想法差的不多

#include <stdio.h>
#include <malloc.h>
#include "graph.h"
int visited[MAXV];     //定义存放节点的访问标志的全局数组
void BFS(ALGraph *G, int v)
{
    ArcNode *p;
    int w;
    int queue[MAXV],front=0,rear=0; //定义循环队列
    printf("%2d",v);            //输出被访问顶点的编号
    visited[v]=1;                       //置已访问标记
    rear=(rear+1)%MAXV;
    queue[rear]=v;              //v进队
    while (front!=rear)         //若队列不空时循环
    {
        front=(front+1)%MAXV;
        w=queue[front];             //出队并赋给w
        p=G->adjlist[w].firstarc;   //找w的第一个的邻接点
        while (p!=NULL)
        {
            if (visited[p->adjvex]==0)
            {
                printf("%2d",p->adjvex); //访问之
                visited[p->adjvex]=1;
                rear=(rear+1)%MAXV; //该顶点进队
                queue[rear]=p->adjvex;
            }
            p=p->nextarc;       //找下一个邻接顶点
        }
    }
    printf("
");
}

//采用广度优先搜索遍历非连通无向图
void BFS1(ALGraph *G)
{
   int i;
   for (i=0;i<G->n;i++)
      if (visited[i]==0)
           BFS(G,i);
}

int main()
{
    int i;
    ALGraph *G;
    int A[8][8]=
    {
        {0,1,0,1,0,0,0,0},
        {1,0,1,0,0,0,0,0},
        {0,1,0,1,1,0,0,0},
        {1,0,1,0,1,0,0,0},
        {0,0,1,1,0,0,0,0},
        {0,0,0,0,0,0,1,0},
        {0,0,0,0,0,1,0,1},
        {0,0,0,0,0,0,1,0},
    };
    ArrayToList(A[0], 8, G);
    for (i=0; i<G->n; i++)
        visited[i]=0; //访问标志数组初始化
    printf(" 非连通图的广度优先遍历:
");
    BFS1(G);
    return 0;
}

代码调试中的问题和解决过程

创建了一个图，发现结果并不对劲

建立了0-1，0-2，0-4，1-2，1-3，2-3的联系，但是邻接矩阵中没有true，可见建立失败了。

利用索引的addEdge()不好用，试试对象直接add

直接蹦出异常

找到下列几个嫌疑人：getIndex()，indexIsValid()，addEdge()

后来发现indexIsValid()确实发生错误，也不知道当时怎么就把大于小于搞错了。

错误消灭。

代码托管

（statistics.sh脚本的运行结果截图）

上周考试错题总结

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）
目标	5000行	30篇	400小时
第一周	0/0	1/1	6/6
第二周	771/771	1/2	16/22
第三周	562/1233	1/3	15/37
第四周	1503/2736	2/5	15/52
第五周	1152/3888	1/6	10/62
第六周	787/4675	1/7	10/72
第七周	1214/5889	1/8	9/81
第八周	1534/7423	1/9	9/90
第九周	1240/8663	2/11	10/100

结对互评

唐才铭19：本次博客中记述问题较少，但是教材内容表述详细，理解到位。
王文彬29：本次博客引用了许多书本原话，非常充实，也提出了好几个自己的问题并且及时解决了。