图的系列算法

单源最短路Dij

单源最短路,不包括负权

int d[maxn];//表示到达该点的最短距离
bool vis[maxn];//表示该点是否访问
int mp[maxn][maxn];//表示两个点之间的距离 初始化为INF
void Dij(int s)
{
	d[s] = 0;
	for (int i = 0;i<n;i++)
	{
		int u = -1;mn = 1e9;
		//找到最小的那个点
		for(int j = 0;j<n;j++)
		{
			if(vis[j]==false && d[j]<mn)
			{
				mn = d[j];
				u = j;
			}
		}
		//每次mp
		if(u==-1) return;
		vis[u] = true;
		//以u为中介更优的走法 也就是可以通过u到达其他的地点 而且更近
		for(int v = 0;v<n;v++)
		{
			if(vis[v]==false && mp[u][v]!=INF && d[u]+mp[u][v]<d[v])
			{
				d[v] = d[u] + mp[u][v];
			}
		}
	}
}

新增边权

用\(cost[u][v]\)来代表\(u\to v\)的花费,需要增加一个数组\(c[]\),代表从起点\(s\)到达顶点\(u\)的最小花费\(c[u]\),第一条件

for(int v = 0; v<n ; v++)
{
    //如果未访问 且存在通路
    if(vis[v]==false && mp[u][v]!=INF)
    {
        if(d[v]>d[u]+mp[u][v])
        {
            d[v] = d[u] + mp[u][v];
      	  	c[v] = c[u] + cost[u][v];
        }else if(d[v]==d[u]+mp[u][v] && cost[u][v] + c[u]<c[v])
        {
            //距离同为最短的情况下 花费更少 
            c[v] = cost[u][v] + c[u];
        }
        
    }
}

计算最短路径条数

//需要增加数组num[],令从起点s到顶点u的最短路径条数为num[u]
//初始化num[s]为1 其他都为0
for(int v = 0; v<n ; v++)
{
    //如果未访问 且存在通路
    if(vis[v]==false && mp[u][v]!=INF)
    {
        if(d[v]>d[u]+mp[u][v])
        {
            d[v] = d[u] + mp[u][v];
      	  	num[v] = num[u];
        }else if(d[v]==d[u]+mp[u][v])
        {
            //相当于最短路径相同
            num[v] += num[u];
        }
        
    }
}

全源最短路Folyd

void Floyd()
{
    for(int k = 0;k<n;k++)
    {
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<n;j++)
            {
                if(dis[i][k]!=INF && dis[k][j]!=INF && dis[i][k]+dis[k][j]<dis[i][j])
                {
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }
}

最小生成树 krustal

// 算法的主要思路为 结构体排序
// 然后根据权值从小到大取边 同时每次将两个端点放入集合 直到取出n-1个边
const int maxn = 1e5;
struct edge{
    int u,v;//端点
	int cost;//该边的权值
}e[maxn];

bool cmp(edge a,edge b)
{
    return a.cost<b.cost;
}
//并查集
int fa[maxn];
int find(int x)
{
    if(fa[x]==x) return x;
    else {
        fa[x] = find(fa[x]);
        return fa[x];
    }
}

void Union(int x,int y)
{
    int a = find(x);
    int b = find(y);
    if(a!=b)
    {
        fa[a] = b;
    }
}

//返回最小生成树的边权之和 n为顶点个数 m为边数
int kru(int n,int m)
{
    sort(e,e+m,cmp);
    int sum = 0;
    //并查集初始化
    for(int i = 0;i<n;i++)
    {
        fa[i] = i;
    }
    int es = 0;
    for(int i = 0;i<m;i++)
    {
        int a = find(e.u);
        int b = find(e.v);
        if(a!=b)
        {
            es++;
            Union(a,b);
            sum += e.cost;
        }
        //这是边的个数
        if(es==n-1){
            return sum;
        }
    }
    
    return -1;
}

BFS广搜

一定一定要注意初始化!!! 如果多次调用的话

邻接矩阵

// 给定一个起点和终点 求出他们之间的最小路
int maxn = 1e5 + 6;
int mp[maxn][maxn];
int vis[maxn];
int n;
// 这个可以构建单源最短路 dist[i]表示从起点到i的最短距离
int[] bfs(int a,int b,int dist[maxn])
{
    for(int i = 1;i<=n;i++)
    {
        vis[i] = 0;
        dist[i] = 0;
    }
    queue<int>q;
    q.push(a);
    while (!q.empty())
    {
        int front = q.front();
        q.pop();
        for(int i = 1;i<=n;i++)
        {
            if(vis[i]!=0 && mp[front][i] != INF)
            {
                q.push(i);
                vis[i] = 1;
                dist[i] = dist[front] + 1;
            }
        }
    }
    return dist;
}

邻接矩阵

// 给定一个起点和终点 求出他们之间的最小路
const int maxn = 1e4 + 6;
const int INF = 1e8;
int mp[maxn][maxn];
int vis[maxn],dist[maxn];
int n,m;

// 这个可以构建单源最短路 dist[i]表示从起点到i的最短距离
void bfs(int a,int b)
{
    for(int i = 1;i<=n;i++)
    {
        vis[i] = 0;
        dist[i] = -1;
    }
    queue<int>q;
    q.push(a);
    dist[a] = 0;
    vis[a] = 1;
    while (!q.empty())
    {
        int front = q.front();
        // cout << front<<"\n";
        q.pop();
        for(int i = 1;i<=n;i++)
        {
            if(vis[i]==0 && mp[front][i] != INF)
            {
                cout << front <<" " << i <<" " <<mp[front][i] <<"\n";
                q.push(i);
                vis[i] = 1;
                dist[i] = dist[front] + 1;
            }
        }
    }
}

//需要将mp初始化 将无关元素 

邻接表的处理方法

在n个结点的图里,输入n-1个边,构成一棵树,广搜可构成基环树(最小的环要不小于4)的方法数

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+6;
// 给定一棵树 找到新增加回路数量小于4的个数
// 算一个点三层之内的点数 然后其他都可以
// bfs
map<int,vector<int> > mp;
int vis[maxn];
int d[maxn];//这个数组表示从该点到起点的距离
int n;
int bfs(int x)
{
    // 这个初始化一定要处理好
    for(int i = 0;i<=n;i++)
    {
        d[i] = 0;
        vis[i] = 0;
    }
    queue<int>q;
    q.push(x);
    d[x] = 0;
    vis[x] = 1;
    int sum = 1;
    while(!q.empty())
    {
        int top = q.front();
        q.pop();
        for(int i = 0;i<mp[top].size();i++)
        {
            int nw = mp[top][i];
            if(vis[nw]==0)
            {
                vis[nw] = 1;
                d[nw] = d[top]+1;
                q.push(nw);
                if(d[nw]>=3) return sum;
                sum++;
            }
        }
    }
    return sum;
}
int main()
{
    cin >> n;
    for(int i = 0;i<n-1;i++)
    {
        int u,v;
        cin >> u >> v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    
    int sum = 0;
    for(int i = 1;i<=n;i++)
    {
        sum += (n-bfs(i));
    }
    cout << sum/2;
    return 0;
}