图的相关知识

图的遍历
1.DFS(深度优先遍历)
就是先进行最深处的点(往最低下走)然后回一步往另一边走,以此走完所有的点

Void dfs(vertex v)
{
   visited[v]=true;
   for(v的每一个邻接点w)
      If( !visted [ w ] ) dfs(w);
}

2.BFS(广度优先遍历)

Void bfs(vertex v)
{
   Queue q;
   q.push(s);
   while(!q.empty()){
   取出队首top;
   访问队首top;
   将队首出队;
   将top的下一层中未曾入队的节点入队;
   }
}

最短路径
1.Dijkstra算法:
适用范围:无负权回路,边权为正
时间复杂度:O(n^2)
步骤
1.初始时令s=v0,t为其他顶点,若存在<v0,vi>为<v0,vi>的权值,不存在则为INf
2.从T钟选区一个距离值最小的顶点W,加入S,对T中顶点的距离值进行修改:如果把W当作中间顶点,从v0到vi的距离值比经过W的值长,则修改距离值
3.重复上面过程
PS:不能处理负权边
代码:

const int maxn = 105;
const int inf = 0x3f3f3f3f;
int dis[maxn];
bool vis[maxn];
int map_dis[maxn][maxn];
int n,m;
int dijkstra(int s, int t) {
   memset(vis, false, sizeof(vis));
   for (int i = 1; i <= n; ++i) { //初始化各点到s点的距离
      dis[i] = map_dis[s][i];
   }
   dis[s] = 0, vis[s] = true;
   for (int i = 0; i < n - 1; ++i) { //除s点外找n-1个点
      int u, tmin = inf;
      for (int j = 1; j <= n; ++j){ //找min{dis[]}
         if(!vis[j] && dis[j] < tmin){
             tmin = dis[j];
              u = j;
         }
      }
// if(tmin == inf) return -1; //无最短路
      vis[u] = true; //进入T集合
      for (int v = 1; v <= n; ++v){ //更新相邻点
         if(!vis[v] && dis[u] + map_dis[u][v] < dis[v]){ 
            dis[v] = dis[u] + map_dis[u][v]; 
         }
      } 
   } 
return dis[t]; 
} 
int main(){ 
   int a, b, c; 
   while (cin >> n >> m, n || m) {
      memset(map_dis,inf,sizeof(map_dis));
      for (int i = 1; i <= m; ++i) { 
         cin >> a >> b >> c;
         map_dis[a][b] = map_dis[b][a] = c;
       }
    cout << dijkstra(1,n) << endl;
   }
return 0;
}

2.Floyd算法:
适用范围:无负权回路,边权可正可负 全源最短路径
时间复杂度:O(n^3) n<=200
思路:枚举所有的点,当作中介点,每一个点都枚举所有顶点对i和j,即dist[i][j] = min(dist[i][k] + dist[k][j],dist[i][j]);
代码

void floyd() {
   for(int k=1; k<=n; k++) {
      for(int i=1; i<=n; i++) {
         for(int j=1; j<=n; j++) {//判断i到k有路k到j有路
            dist[i][j] = min(dist[i][k] + dist[k][j],dist[i][j]);
         }
      }
   }
}

3.SPFA算法
适用范围:边权可正可负,可以判断途中有无负权回路
时间复杂度: O(kE) BF算法的升级版
步骤:将源点加入队列,不断从队列中弹出顶点u,遍历u的邻接点进行松弛更新,更新完后v点不在队列中则放入队尾。不断取出节点直到队列为空。
判断有无负权回路:当某点进入队列的次数超过图的顶点数的时候
初始化:除了起点赋值为0,其他顶点赋值为INF,
代码:

const int maxn = 105;
const int maxm = 10000;
const int inf = 0x3f3f3f3f;
int inq[maxn], head[maxn], dis[maxn]; //inq[u]==1:u在队列里
struct Edge{
int v, w, next;
} edge[maxm * 2];
int spfa(int s, int t){
   memset(head, -1, sizeof(head));
   memset(inq, 0, sizeof(inq));
   memset(dis, inf, sizeof(dis));
   queueq;
   q.push(s);
   dis[s] = 0;
   inq[s] = 1;
   while (!q.empty()){
      int u = q.front();
      q.pop();
      inq[u] = 0;
      for (int i = head[u]; i != -1; i = edge[i].next) {
         int v = edge[i].v;
         int w = edge[i].w;
         if (dis[v] > dis[u] + w){
            dis[v] = dis[u] + w;
            if (!inq[v]){
               inq[v] = 1;
               q.push(v);
            }
         }
      }
   }
return dis[t];
}

4.Bellman-Ford算法(BF算法)
可以解决单元最短路径问题和负权边
跟dijkstra 一样需要一个d数组来存放源点到各点之间的距离,同时返回一个bool值:如果存在从源点可达的负环,则返回false,否则反之。
思路:对所有的边进行n-1轮操作,每次遍历图中所有的边,如果以u为中介点使得d[v]变小,就更新之
最后对所有边进行一次操作,如果还可以缩小,说明有负环,返回false。

最小生成树
性质:最小生成树是一棵树,边数等于定点数减1;最小生成树不唯一但边权之和为一

1.Prim算法
思路:设置集合s,存放已访问的顶点,从图中选择距离集合s最短的点为u访问并加入集合,令u为中介点,更新所有能到达u的顶点与集合的最短距离,重复以上过程,使得最后集合保存所有的点。(几乎与dijkstra相同)
性能:时间复杂度O(n^2) 尽量用于稠密图
代码:

Int n, G[maxn][maxn];
Int d[maxn];
Bool vis[maxn] ={false};
Prim(){
   Fill(d,d+maxn,inf);
   d[0]=0;
   int ans=0;
   for(int i=0;i<n;i++){
      int u=-1,minx =inf;
      for(int j=0;j<n;j++){
         if(vis[j]=false&&d[j]<minx){
            u=j;
            minx=d[j];
          }
       }
     if(u==-1) return ;
     Vis[u] = true;
     Ans+=d[u];//将最小的边加入集合中
     For(int j =0;j<n;j++){
         If(vis[j]==false&&G[u][j]<d[j]){//这里与dijkstra不同
         d[j]=G[u][j];
         }
     }
   }
return ans;
}

2.Ktuskal算法
思路·:对所有的边进行排序,从小到大开始测试所有边,当边的两个点不在同一个连通块的时候,将边加入到集合里面,否则弃之。重复之前的操作,直到最后得到一颗最小生成树。(中间用到了并查集的知识)
性能:适合用于顶点数多,边数较少的情况即稀疏图。
代码:

const int maxn=10005;
struct node {
int from,to,len;
} edge[maxn];//储存边的数据结构
int n, fa[maxn], m,ans,q;
bool cmp(node a,node b) {
return a.len<b.len;
}//边按从小到大的顺序排列
int Find(int x)
{
   if(fa[x]==x) return x;
   return fa[x]=Find(fa[x]);
}
void Merge(int x,int y)
{
   x=Find(x),y=Find(y);
   if(x!=y) fa[y]=x;
}
int kruskal(){
   sort(edge,edge+m,cmp);//边排序
   for(int i=0;i<=n;i++) fa[i]=i;//初始化并查集
   ans=0;
   for(int i=0;i<m;i++)//一条边的两个点不在同一集合,则选它,并合并端点 
      if(Find(edge[i].from)!=Find(edge[i].to)) 
         Merge(edge[i].from,edge[i].to),ans+=edge[i].len; 
   return ans; 
} 
int main() { 
while(cin>>n,n){
   m=n*(n-1)/2;
   for(int i=0;i<m;i++) 
      cin>>edge[i].from>>edge[i].to>>edge[i].len;
   cout<<kruskal()<<endl;
   }
return 0;
}

 

拓扑排序
思路:定义一个队列,将一开始入度为0的结点放入队列中;取出队首的结点,删去所有从它出发的边,并将终点的入度减1;当出现入度为0的结点的点时,将之放入队列中,直到队列为空。
代码:

Vector G[maxn];
Int n,m,degree[maxn];
Bool topologicalsort(){
   Int num=0;
   Queue q;
   For(int i=0;i<n;i++)
   If(degree[i]==0)
   q.push(i);
   while(!q.empty()){
   int u=q.front();
   q.pop();
   for(int i=0;i<n;i++){
   int v=G[U][I];
   degree[v]--;
   if(degree[v]==0) q.push(v);
   }
   G[u].clear();
   num++;
   }
   If(num==n) return true;
   Else return false;
}