1.本周学习总结
1.1思维导图
1.2.对图的认识及学习体会
图结构相对于树来说，比较好理解，邻接矩阵可以用二维数组来做，邻接表结构是好理解，就是结构体的定义以及代码编写过程较复杂。图这一章感觉难点在于最小生成树和最短路径的这几个算法，虽然图的结构容易定义，但是运用来解决问题，并结合算法，就想不出来了。还是对于解题思路这方面有着很大的难度。
2.PTA实验作业
2.1.题目1: 7-7 旅游规划
2.1.1设计思路
void dijkstra(int s) //修改后的最短路算法，+path 记录 和 花费计算
{
int i,j;
初始化标记数组vis
for(i=0 to n)//初始化数组dis,cost的值
{
dis[i]=mat[s][i];
cost[i]=pay[s][i];
if(边不为无穷大) //无穷大代表此路不通 path[i] =-1,否则就在路径加入这个点
path[i]中加入点s
else
path[i]等于-1
}
数组vis[s]标记为1;//起始点标记
数组dis[s]标记为0;//自己到自己的花费cost = 0
数组cost[s]标记为0;
for(i=1 to n)
{
int k=s,u=maxn;//找出到s距离最短&没标记的点，作为中转点更新dis值
for(j=0 to n)
{
if(!vis没有被标记且dis最短路径没有u)
{
u=dis[j];
k=j;
}
}
数组vis[k]标记为1;//标记这个点
for(j=0;j<n;j++)
{
if(!vis[j]&&mat[k][j]!=maxn)
{
if(最短路径dis相同的话)
{
选择花费最少的，最小cost
}
else if(如果这个花费更加优)
{
那么把这个点加入，更新最优秀的路径
}
}
}
}
}
void print(int s,int t)
{
stack<int>q;
//从path里溯源t = path[t],返回上一个和t联通的路径，由后往前，把s~t路径放入队列里面，然后输出
while(t!=s)
{
入队t;
t=path[t];
}
入队t;
while(队列不为空)
{
cout<<q.top()<<" ";
移除队头元素;
}
}
2.1.2代码截图
2.1.3本题PTA提交列表说明。
2.2.题目2：7-4 公路村村通
2.2.1设计思路
void Prim()
{
MST={s};
while(1)
{
v=未收录顶点中dist最小者；
if（这样的v不存在）
break；
将v收录进MST：dist【v】=0；
for(v的每个邻接点w)
if(dist[w]!=0)
if(E<dist[w])
{
dist[w]=E;
parent[w]=v;
}
}
if(MST中收的顶点不到v个）
EEROR（“生成树不存在”）；
}
2.2.2代码截图
2.2.3本题PTA提交列表说明。
2.3.题目3：7-3 六度空间
2.3.1设计思路
int bfs(int z)
{
int i, level,count;
int visited[10001] = { 0 };
int last = z;//记录每层的最后一个元素：该层压入之后弹出之前更新：last=temp；
int tail;//用于记录每层压入时的结点
queue<int>q;
将z入队；
visited[z]置为1，表示访问过；
while (队列不空)
{
z置为队头元素；
移除队头元素；
for (i=1 to v)
if (两点有边&&节点未被访问)
{
count++;
visited[i]置为1;
将i入队
tail = i;
}
if (last == z)//一层全部弹出，准备开始弹下一层：弹出的(x)=当前层最后一个元素(last)
{
level++;
last = tail;//一层全都压入完后，更新last
}
if (level == 6) break;
}
返回 count;
}
2.3.2代码截图
2.3.3本题PTA提交列表说明。
3、上机考试错题及处理办法
3.1.1截图错题代码
3.1.2 错的原因及处理方法
箭头那一处漏了一句dist[s]=0;在上面for循环找到节点之后，就该把s节点置为0，表示访问
3.2.1截图错题代码
3.2.2 错的原因及处理方法
箭头处的for循环语句中，i应该从1开始循环。