图论的复习/(ㄒoㄒ)/

图论基本概念

完全图: 每对顶点之间有边并且只有唯一的一条边.

强连通分量:有向图中任意2点都联通的最大子图.

图的储存

邻接矩阵:也就是一个二维数组,a[i][j]的值代表是否相连.

适用范围:

1.稠密图

2.无多重边

3.数据规模小

链式前向星:(模拟链表)

代码实现(主要部分)

 void add_eage(int from,int to,int  dis)

 {

     eage[++num].next=head[from];

     eage[num].to=to;

     eage[num].dis=dis;

     head[from]=num;

 }

割点&割边:

如果删去,那么原来联通的图就会变成2个或2个以上子图

判断割点:开一个low数组来记录i及i的子孙相连的最高的祖先的访问时间戳

low[u]=min(low[u],low[v]);

判断割边:当且仅当low[v]>dfn[u];

强连通分量Tarjan

 void tarjan(int i)//开始搜索...

 {

     int j;

     dfn[i]=low[i]=++times;//记录时间戳

     stak[++stp]=i;//压入栈

     for(j=head[i];j;j=a[j].next)

     {

         int k=a[j].to;

         if(!dfn[j])

         {

             tarjan(j);

             if(low[j]<low[i]) low[i]=low[j];

         }

         else if(instak[j]&&dfn[j]<low[i]) low[i]=dfn[j];

     }

     if(dfn[i]==low[i])//判断改点是否为根节点

     {

         cnt++;//定义在最外面

         do

         {

             j=stak[stop--];

             instak[j]=false;

             belong[j]=cnt;

         }while(i!=j);

     }

 }

 //cnt代表多少个强连通分量

最短路

1.Dijkstra:不含负权

思路:每次找到离源点最近的一个点进行扩展,最终得到源点到其余所有点的最短路径,不含负权

2.Bellman-ford:有负权,不含负权回路

这个就转变成对边的松弛

for(int i=; i<=n; i++)

  　　 {

        　　int mindist = MAXINT;

        　　int u = v0; 　　                            // 找出当前未使用的点j的dist[j]最小值

       　　 for(int j=; j<=n; ++j)

       　　    if((!S[j]) && dist[j]<mindist)

       　　    {

          　　       u = j;                             // u保存当前邻接点中距离最小的点的号码

          　 　      mindist = dist[j];

        　　   }

        　　S[u] = true;

        　　for(int j=; j<=n; j++)

        　　    if((!S[j]) && A[u][j]<MAXINT)

        　　    {

            　    　if(dist[u] + A[u][j] < dist[j])     //在通过新加入的u点路径找到离v0点更短的路径

            　    　{

                    　　dist[j] = dist[u] + A[u][j];    //更新dist

                    　　prev[j] = u;                    //记录前驱顶点

             　　    }

         　    　}

    　　}

3.SPFA:kuai

  while (!Q.empty())

     {

         int u = Q.front();

         Q.pop();

         visited[u] = ;

         for (int v = ; v < vertex_num; v++)

         {

             if (matrix[u][v] != INT_MAX)  //u与v直接邻接

             {

                 if (dist[u] + matrix[u][v] < dist[v])

                 {

                     dist[v] = dist[u] + matrix[u][v];

                     path[v] = u;

                     if (!visited[v])

                     {

                         Q.push(v);

                         enqueue_num[v]++;

                         if (enqueue_num[v] >= vertex_num)

                             return false;

                         visited[v] = ;

                     }

                 }

             }

         }

     }

最小生成树太简单了

巴特西

图论的复习/(ㄒoㄒ)/

图论基本概念

图的储存

割点&割边:

强连通分量Tarjan

最短路

最新文章

热门文章