思维导图
练习题目注意点：
1.如果最短路径一共有10条边，而另一条路径虽然比最短路径长，但它只有一条边，如果图中所有路径的权值都加1，就会导致边少的路径可能会成为新的最短路径。
2.最小生成树VS最短路径：最小生成树只能说明整个路径是最小的，并不能说明树中单个结点的路径是最小的。
邻接表存储结构：
typedef struct ArcNode//边结点 { int adjvex;//所指向的顶点的位置 struct ArcNode *nextarc;//指向下一条边的指针 }ArcNode; typedef struct VNode//顶点结点 { int data;//顶点的名称 ArcNode *firstarc;//该顶点的第一条边 }VNode,AdjList[MAX]; typedef struct { AdjList vertices;//AdjList是一个数组类型，所以vertice就是数组名了 int vexnum,arcnum; }ALGraph;//邻接表
邻接矩阵存储结构：
typedef struct { int vexs[MAX]; int arc[MAX][MAX]; int vexnum,arcnum; }AMGraph;
BFS：
//基于邻接表 void BFS_AL(ALGraph G,int i) { cout<<i<<" "; visited_2[i]=true; int k; queue<int>Q; Q.push(i); while(!Q.empty()) { k=Q.front(); Q.pop(); ArcNode *p=G.vertices[k].firstarc; for(int w=p->adjvex;p!=NULL;p=p->nextarc) { if(!visited_2[w]) { cout<<w<<" "; visited_2[w]=true; Q.push(w); } } } }
//基于邻接矩阵 void BFS_AM(AMGraph G,int i) { cout<<i<<" "; visited_2[i]=1; queue<int> Q; Q.push(i); int k; while(!Q.empty()) { k=Q.front(); Q.pop(); for(int i=0;i<G.vexnum;i++) { if(G.arc[i][k]==1&&visited_2[i]==0) { cout<<i<<" "; visited_2[i]=1; Q.push(i); } } } }
目标：因为有不少大作业要提交，上期的目标完成的不太理想，每个图的应用的算法都是一个大工程，没有花很多心思去理清；下期需要合理安排时间，利用时间回顾知识，也要兼顾第7章。
原文：https://www.cnblogs.com/pqd-blog/p/13128568.html