专题四总结
在这一专题里，首先了解了图数据结构的一些基础知识以及图的存储方式。
图的一些基础知识包括：图的概念，图的一些部件的命名，以及一些基本的数量关系
图的表示形式一般包括：矩阵，邻接表
我感到最有趣的就是邻接表的数组表示形式了，开销低且高效，感觉甚是神奇，下面贴出邻接表的数组表示形式：
struct edge
{
int x, y, nxt; typec c;
} bf[E];
void addedge(int x, int y, typec c)
{
bf[ne].x = x; bf[ne].y = y; bf[ne].c = c;
bf[ne].nxt = head[x]; head[x] = ne++;
}
基础知识学习了解之后，又学习了并查集。并查集理解起来很简单，写起来也很简单，但是它的作用很强大。并查集是之后的求最短路的kruskal算法的基础。而在求最小生成树时，我觉得kruskal算法比prim算法更容易理解，也更容易实现。下面是kruskal算法（并查集）的代码实例：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX=105;
int c[MAX];
struct xy
{
int x;
int y;
int c;
}dis[MAX*(MAX-1)/2];
int find(int i)
{
while(c[i]!=i)
i=c[i];
return c[i];
}
void merg(int a,int b)
{
a=find(a);
b=find(b);
if(a!=b){
c[a]=c[b];
}
}
bool cmp(xy a,xy b)
{
return a.c<b.c;
}
int main()
{
//freopen("date.in","r",stdin);
//freopen("date.out","w",stdout);
int n,tem,res;
while(cin>>n&&n!=0){
res=0;
for(int i=1;i<=n;i++){
c[i]=i;
}
for(int i=0;i<n*(n-1)/2;i++){
scanf("%d%d%d%d",&dis[i].x,&dis[i].y,&dis[i].c,&tem);
if(tem==1)
merg(dis[i].x,dis[i].y);
}
sort(dis,dis+n*(n-1)/2,cmp);
for(int i=0;i<n*(n-1)/2;i++){
if(find(dis[i].x)!=find(dis[i].y)){
res+=dis[i].c;
merg(dis[i].x,dis[i].y);
}
}
printf("%d
",res);
}
}
上述实例是我的此专题的1005的AC代码，题目是最经典的“畅通工程”，即用最短的道路连接所有城镇。可以看到，完全是并查集，只不过最后有一个排序（贪心），然后选择边的过程。很好理解。
另外，通过对并查集实现的循序渐进的一次次优化，我也体会到了思考的乐趣。
学习完了并查集及两种最小生成树的几种经典算法：prim算法，kruskal算法后，又学习了最短路问题的三种算法：Dijkstra算法（贪心），Bellman-Ford算法，spfa算法（Bellman-Ford算法的队列实现）
三者都应用了松弛技术，刚开始学的时候是一脸懵逼啊，怎么起个这么奇怪的名字。。。。想明白了其实很好理解，就是用现在的最小路径去更新其他的路径。
三种算法当然有区别了：Dijkstra算法不能用于处理带有负权值的图，因为这一算法对标记过得点就不能进行更新了。有负权值边时，有可能会使已标记过的点的最短距离变短，但Dijkstra算法就不会进行更新。注意这一点与Dijkstra算法中松弛技术的区别。
而Bellman-Ford算法，spfa算法可以实现处理带负权值的图，处理的情况更一般些。下面贴出Bellman-Ford算法的模板：
#define MAX_VER_NUM 10 //顶点个数最大值
#define MAX 1000000
int Edge[MAX_VER_NUM][MAX_VER_NUM]; //图的邻接矩阵
int vexnum; //顶点个数
void BellmanFord(int v) //假定图的邻接矩阵和顶点个数已经读进来了
{
int i, k, u;
for(i=0; i<vexnum; i++)
{
dist[i]=Edge[v][i]; //对dist[ ]初始化
if( i!=v && dis[i]<MAX ) path[i] = v; //对path[ ]初始化
else path[i] = -1;
}
for(k=2; k<vexnum; k++) //从dist1[u]递推出dist2[u], …,distn-1[u]
{
for(u=0; u< vexnum; u++)//修改每个顶点的dist[u]和path[u]
{
if( u != v )
{
for(i=0; i<vexnum; i++)//考虑其他每个顶点
{
if( Edge[i][u]<MAX &&
dist[u]>dist[i]+Edge[i][u] )
{
dist[u]=dist[i]+Edge[i][u];
path[u]=i;
}
}
}
}
}
}
以上就是这学期图论学习的内容了，看大神的介绍都是很基础的东西，还是继续努力，希望能在暑假期间的集训好好巩固基础