图论的存储、遍历，Tarjan算法

图的存储

图的存储可分为顺序存储和链式存储。顺序存储包括邻接矩阵和边集数组，链式存储包括邻接表、链式前向星、十字链表和邻接多重表。

邻接矩阵其实就是用二维数组存边，优点是可以快速判断两节点之间是否有边，并且方便计算各节点的度（O（n）的时间复杂度）；缺点是不利于增删节点，不便于访问所有邻接点。

邻接表是自己创造了两种数据结构：节点和邻接点。每个节点后面跟一串邻接点。有向图的邻接表又可分为出弧和入弧两种。邻接点的优点是便于访问所有邻接点，且空间复杂度低；缺点是不便于判断两个节点之间是否有边，也不便于判断各节点的度。

链式前向星采用了一种静态链表存储方式，将边集数组和邻接表相结合，经常使用。

const int maxn=101;
const int maxe=10001;
struct node
{
    int to,next,w;
}edge[maxe];//边集数组，一般要设置比maxn*maxn大的数，但题目有要求除外
int head[maxn];//头节点数组
int cnt=0;//记录总共有几条边
void add(int u,int v,int w)//添加一条从u到v的权值为w的边
{
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void dfs(int u)//遍历u的所有邻接点
{
    for(int i=head[u];i!=-1;i=edge[i].next)//i!=-1可以写为~i
    {
        int v=edge[i].to;
        int w=edge[i].w;
    }
}
int main()
{
    memset(head,-1,sizeof(head));
}

图的遍历

图的遍历根据搜索方式的不同，分为广度优先遍历和深度优先遍历。

广度优先遍历借助队列实现，深度优先遍历借助递归实现。

图的联通性

基础知识

在无向图中，如果图中任意两个节点都是联通的，则称该图为连通图。

无向图的极大连通子图被称为该图的联通分量。连通图的联通分量就是它本身。

在有向图中，如果图中任意两个节点相互可达，则称该图为强连通图。

有向图的极大强连通子图被称为该图的强联通分量。

如果去掉无向连通图的一条边后，该图分裂为两个不连通的子图，则称该边为该图的桥或割边。

如果去掉无向连通图的一个点后，该图分裂为多个不连通的子图，则称该点为该图的割点。

注意：删除边时，只把该边删除即可；删除点时，要删除该点及其关联的所有边。

割点和桥的关系：有割点不一定有桥，有桥一定有割点；桥一定是割点依附的边。

如果在无向图中不存在桥，则称它为边双连通图

如果在无向图中不存在割点，则称它为点双连通图

有分别依据上述两种图的将图转化为数的方法，称为e-DCC缩点 和 v-DCC缩点。

Tarjan算法

两个概念：

时间戳：dfn[u]表示节点u深度优先遍历的序号

追溯点：low[u]表示节点u或u的子孙能通过非父子边追溯到的dfn最小的节点序号

Tarjan算法有什么作用？

可以通过访问图中的每一个节点，将该图的连通分量中每一个节点的low值赋值为第一次进入这个连通分量的那个点的dfn值

无向图的桥

桥判断法则：无向边x-y是桥，当且仅当在搜索树上存在x的一个子节点y时，满足low[y]>dfn[x].

void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++num;
    for(int i=head[u];~i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa)
            continue;
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])
                cout<<u<<"-"<<v<<"是桥"<<endl;
            
        }
        else
            low[u]=min(low[u],dfn[v]);
    }
}

无向图的割点

割点判定法则：若x不是根节点，则x是割点，当且仅当在搜索树上存在x的一个子节点y，满足low[y]>=dfn[x]；若x是根节点，则x是割点，当且仅当在搜索树上至少存在两个子节点，满足该条件。

void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++num;
    int cnt=0;
    for(int i=head[u];~i;i=e[i].next)
    {
        int v=e[i].to;
        
        if(v==fa)
            continue;
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])
            {
                cnt++;
                if(u!=root || cnt>1)
                    cout<<u<<"是割点"<<endl;
            }
        }
        else
            low[u]=min(low[u],dfn[v]);
    }
}

有向图的强连通分量

void tarjan(int u)
{
    dfn[u]=low[u]=++num;
    ins[u]=true;
    s.push(u);
    for(int i=head[u];~i;i=e[i].next)
    {
        int v=e[i].to;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else
        	if(ins[v])
            	low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])
    {
    	int v;
    	cout<<"强连通分量：";
    	do{
    		v=s.top();
    		s.pop();
    		cout<<v<<" ";
    		ins[v]=false;
    	}while(v!=u);
    	cout<<endl;
    }
}