首页 > 其他分享 >搜索与图论

搜索与图论

时间：2024-09-05 10:40:02浏览次数：2  
标签：图论 dist idx int ++ 搜索 include 节点

这部分内容要用到树的数据结构，我们有以下几种方式来存储节点
邻接表

邻接表就是用类似链表的结构来存储数据，先创建一个数组h，每一个位置都有一个表头。然后e数组和ne数组分别表示节点的值是多少，节点的下一个节点的编号是多少，这种方式一般用在稠密图中，也就是节点数跟边数相差很大。

邻接矩阵

邻接矩阵就是用一个二位数组g[a][b]来表示从a到b的距离是多少，当然，a和b是相邻的节点，这种方式一般用在稀疏图中，也就是节点数跟边数相差不大。

结构体

用结构体来存储边

树与图的优先遍历

深度优先遍历

这个算法就是深搜结合数据结构中的树，不过，具体实现要看题目的不同。

846. 树的重心 - AcWing题库

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;

const int N = 200010;

int h[N],e[N],ne[N],idx,ans = N; //用邻接表的存储方式
int n;
bool st[N];

void add(int a,int b) //增加节点的模板函数
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

int dfs(int u) //深搜
{
    st[u] = true; //标记一个位置是否被计算过
    int sum = 1,res = 0; //sum表示当前节点加上接上的节点总数，res是最大的分块的节点数
    for(int i = h[u];i != -1;i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            int s = dfs(j); //用递归来算分块节点数
            
            sum +=s; 跟新sum
            res = max(res,s);更新res
        }
        
    }
    res = max(res,n - sum);
    ans = min(ans,res); //更新答案
    
    return sum;
    
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    int a,b;
    for(int i = 0;i < n - 1;i ++)
    {
        cin>>a>>b;
        add(a,b),add(b,a); //加入无向边
    }
    
    dfs(1);
    
    cout<<ans<<endl;
    
}

这道题目的大致思路是：
首先树的重心是删除这个数后连通块里面的最大连通块的节点数最小的那个点，我们可以遍历所有的节点，把每个节点删除的情况求一遍，然后记录最小答案就行。

而求某一个点的连通块的节点就要用到dfs来深度遍历了

宽度优先遍历

同样也是宽搜和树的结合

847. 图中点的层次 - AcWing题库

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <string>
#include <cstring>
#include <queue>
using namespace std;

const int N = 200010;
int n,m;
int h[N],e[N],ne[N],idx; //用邻接表来存储数据
int d[N],q[N]; // 宽搜用到的队列q

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

int bfs()
{
    memset(d,-1,sizeof(d));
    d[1] = 0;
    int hh = 0,tt = 0;
    q[0] = 1;
    
    while(hh <= tt)
    {
        int x = q[hh ++];
        
        for(int i = h[x];i != -1;i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1)
            {
                d[j] = d[x] + 1; //当j点没到过时更新原点到节点的距离，是上一个节点加一
                q[++ tt] = j;
            }
            
        }
    }
    
    return d[n];
}


int main()
{
    memset(h,-1,sizeof(h));
    
    cin>>n>>m;
    int a,b;
    
    for(int i = 0;i < m;i ++)
    {
        cin>>a>>b;
        add(a,b);
        
    }
    
    cout<<bfs()<<endl;

    return 0;
}

宽度搜索终点的最短距离可以保证第一个到达的就是最短的,也就是我们宽度遍历所有点，可以保证到达终点的路径长度是最短的。

拓扑排序

首先我们得明白什么是拓扑序列。拓扑序列就是图中的边都指向后面的元素比如我们有一个图，里面的节点指向分别是1 -> 2,2 -> 3,1 -> 3，里面的拓扑序列就是1 2 3

image
可以看见，1 和 2的出边都指向后面的3，所以是拓扑序列。
再来看题目

848. 有向图的拓扑序列 - AcWing题库

#include<iostream>
#include<cstring>

using namespace std;

const int N = 200100;

int h[N],e[N],ne[N],d[N],idx,q[N],n,m; //由于是稀疏图就用邻接表来存
bool st[N];

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

bool topsort()
{
    int hh = 0,tt = -1;
    
    for(int i = 1;i <= n;i ++) //检验入边为0的节点，就是起点，可能有多个起点
    {
        if(!d[i])
        {
            q[++tt] = i; //放入队列
        }
    }
    
    
    while(hh <= tt)
    {
        int t = q[hh ++]; //获取队头的同时出列
        
        for(int i = h[t];i != -1;i = ne[i])
        {
            int j = e[i];
            d[j] --; //减去了一个节点，那么入边减一
            if(d[j] == 0) //如果没有入边了说明这个点不需要了，可以入队列了，入了队列接下来就是对它指向的节点进行判断了
            {
                q[ ++ tt] = j;
            }
        }
    }
    
    return tt == n - 1; // 当tt == n - 1的时候，说明所有的元素都已经入队列了，就是把图中的所有节点排列成了拓扑序列
    
}


int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    int a,b;
    for(int i = 0;i < m;i ++)
    {
        cin>>a>>b;
        add(a,b);
        d[b]++;
    }
    
    if(topsort())
    {
        for(int i = 0;i < n;i ++) //入队列的顺序正好就是拓扑序列的顺序
        {
            cout<<q[i]<<" ";
        }
        cout<<endl;
    }else
    {
        cout<<-1<<endl;
    }
    
}

Dijkstra 算法(戴克斯特拉算法)

朴素版dijkstra

这种版本一般适用于稠密图的求最短路径中，并且要求没有权值为负的边。
根据相应的要求，我们用邻接矩阵来存储数据

朴素版的算法基本步骤是从所有已经到达的节点中找到距离最短也就是的那个值，也就是dist[t]最小，并且这个点没有被标记，可以理解为没有进入答案集合，然后，遍历所有的节点，看能不能用dist[t]来更新距离的最小值

849. Dijkstra求最短路 I - AcWing题库

#include<iostream>
#include<cstring>

using namespace std;

const int N = 510;

int g[N][N],dist[N],n,m; //邻接矩阵
bool st[N]; //标记答案集合

int dijkstra()
{
    dist[1] = 0;
    for(int i = 0;i < n;i ++)
    {
        int t = -1;
        for(int j = 1;j <= n;j ++)
        {
            if(!st[j] &&(t == -1 || dist[t] >dist[j])) //如果不在答案集合里面，或者没有初始值，或者能更新最小dist值
            {
                t = j;
            }
        }
        st[t] =true;
        
        for(int j = 1;j <= n;j ++)
        {
            dist[j] = min(dist[j],dist[t] + g[t][j]);
        }
        
    }
    
    if(dist[n] == 0x3f3f3f3f) //如果dist[n]不等于无穷大
    {
        return -1;
        
    }else return dist[n];
    
}

int main()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    memset(dist,0x3f,sizeof dist);
    int a,b,c;
    for(int i = 0;i < m;i ++)
    {
        cin>>a>>b>>c;
        g[a][b] = min(g[a][b],c);
    }
    int t = dijkstra();
    
    cout<<t<<endl;
    
}

堆优化版dijkstra

在朴素版的代码中，有一部分特别笨重，就是更新的时候我们需要遍历所有节点去寻找最小dist，但是数据结构中的优先队列可以在短时间内给出最小的节点。下面是题目和代码。

AcWing 850. Dijkstra求最短路 II - AcWing

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>

using namespace std;

typedef pair<int,int> PII; //后续我们会用pair来存数据，首位是距离 ，末尾是节点值，就是节点编号


const int N = 1000100;

int h[N],w[N],e[N],ne[N],idx,n,m,dist[N]; //题目给的稀疏图所以我们用邻接表
bool st[N];

void add(int a,int b,int c)
{
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++;
    
}


int dijkstra()
{
    priority_queue<PII,vector<PII>,greater<PII>> heap; //优先队列
    memset(dist,0x3f,sizeof dist); //初始化dist
    
    dist[1] = 0; 
    heap.push({0,1});//初始化，1号节点入列
    
    while(heap.size())
    {
        auto t = heap.top(); //获取并弹出第一个节点
        heap.pop();
        
        int ver = t.second,distance = t.first;
        
        if(st[ver]) continue; //如果这个节点进入了答案集合就跳过
        
        st[ver] = true;
        
        for(int i = h[ver];i != -1;i = ne[i])
        {
            int j = e[i];
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j],j});
            }
            
        }
        
    }
    
    if(dist[n] == 0x3f3f3f3f)
    {
        return -1;
    }else 
    {
        return dist[n];
    }
    
    
}

int main()
{
    cin>>n>>m;
    
    memset(h,-1,sizeof h);
    
    int a,b,c;
    
    for(int i = 0;i < m;i ++)
    {
        cin>>a>>b>>c;
        
        add(a,b,c);
    }
    
    int t = dijkstra();
    
    cout<<t<<endl;
    
}

bellman_ford算法

AcWing 853. 有边数限制的最短路 - AcWing

这个算法一般用在有负边但是限制了最多经过的边的最短路问题。这个算法的思路是进行k次循环，k就是限制最多的边数，在k次循环下遍历所有的边更新dist。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = 510;
int dist[M], n, m, k, backup[M];

struct edge //用结构体来表示边
{
    int a, b, w; //a到b的边，权重是w
} points[N];

bool bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < k; i++)
    {
        memcpy(backup, dist, sizeof dist); //备份，从上一次的情况开始更新，backup是备份dist的数组。
        for (int j = 0; j < m; j++) //循环所有节点，看能不能更新最短长度
        {
            int a = points[j].a, b = points[j].b, w = points[j].w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) //如果dist[n]是一个很大的值，那么就是到不了n可能1到不了n和节点p但是节点p到的了n，            
    {                            //这时dist[n]和dist[p]都是无穷，如果n到p是负权边就会比0x3f3f3f3f小
        return false;
    }
    return true;
}

int main()
{

    cin >> n >> m >> k;
    int a, b, c;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        points[i] = {a, b, c};
    }
    bool t = bellman_ford();
    if (t == false)
    {
        cout << "impossible" << endl;
    }
    else
    {
        cout << dist[n] << endl;
    }
}

因为边数有限所以我们不用考虑负权回路也就是负环的问题

SPFA算法

这个算法一般用于没有负环也没有边数限制的最短路径问题。

首先是这个算法的思路：

我们用队列来存下所有到点1的距离变化的点t，类似于蝴蝶效应，点t的所有子节点都有可能会被更新到1的值，然后子节点的所有子节点也可能会被更新，但是如果，子节点的子节点已经在队列里面了，就不用入队了，因为迟早会轮到它来更新其他点。就用这种方式来遍历所有的点直到没有新的更新操作为止

AcWing 851. spfa求最短路 - AcWing

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int N = 100010;

int e[N],ne[N],h[N],dist[N],idx,n,m,w[N];
bool st[N];

void add(int a,int b,int c)//邻接表
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}

bool spfa()
{
    queue<int> q; //用队列来存需要发生改变的点，这个点的所有子节点都有可能会给更行最短距离
    memset(dist,0x3f,sizeof dist);
    
    dist[1] = 0;//初始化，先让点1入队，点1后买面的点都有可能改变
    q.push(1);
    st[1] = true;
    while(q.size())
    {
        int t = q.front();//获取需要改变的节点然后把它抛出
        q.pop();
        st[t] = false;
        for(int i = h[t];i != -1;i = ne[i]) //遍历所有子节点
        {
            int j = e[i]; //获取子节点的代表的数字
            if(dist[j] > dist[t] + w[i]) //如果从1到j的距离大于从1到t再到j的距离就更i新j的dist
            {
                dist[j] = dist[t] + w[i];
                if(!st[j]) //如果j点已经在队列里了，就迟早会对它的子节点进行更新操作，所以不用放进去
                {
                    q.push(j);//如果没有，那就入队
                    st[j] = true;
                }
            }
        }
        
    }
    
    if(dist[n] == 0x3f3f3f3f)//n的dist还是无穷大说明到不了这个点，返回false
    {
        return false;
    }else
    {
        return true;
    }
    
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    int a,b,c;
    for(int i = 0;i < m;i ++)
    {
        cin>>a>>b>>c;
        add(a,b,c);
    }
    
    bool t = spfa();
    
    if(!t)
    {
        cout<<"impossible"<<endl;
    }else
    {
        cout<<dist[n]<<endl;
    }
    
    
}

spfa的另外一种用法是求是否有i负环

我们可以维护每个点到1的最短距离的边数，在求最短距离的同时就可以做到，如果有个点的边数大于n - 1，那么说明图种有负环

Floyd求最短路

这个算法用于求解多元汇最短路

这个算法的时间复杂度是n^3，所以一般用在点数少，边数多的情况。

大致思路是，我们迭代n次也就是k层，循环两层，i层 和 j层，所有dist[ i ] [ j ]都尝试用k来更新一遍

AcWing 854. Floyd求最短路 - AcWing

#include<iostream>
#include<cstring>

using namespace std;

const int N = 210;
int INF = 0x3f3f3f3f;
int d[N][N];
int n,m,Q;

void floyd()
{
    for(int k = 1;k <= n;k ++) //k层
    {
        for(int i = 1;i <= n;i ++)//i层
        {
            for(int j = 1;j <=n;j ++)//j层
            {
                d[i][j] = min(d[i][j],d[i][k] + d[k][j]); //尝试更新
            }
        }
    }
}

int main()
{
    cin>>n>>m>>Q;
    
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= n;j ++) //初始化所有点，让自环距离等于0
        {
            if(i == j)d[i][j] = 0;
            else d[i][j] = INF;
        }
    }
    int a,b,c;
    for(int i = 1;i <= m;i ++) //读入边长
    {
        cin>>a>>b>>c;
        d[a][b] = min(d[a][b],c); //保留最短边
    }
    floyd();
    
    for(int i =0;i < Q;i ++)
    {
        cin>>a>>b;
        if(d[a][b] > INF / 2) cout<<"impossible"<<endl; //如果到达不了某个点就false掉
        else cout<<d[a][b]<<endl;
    }
}

最短生成树问题

生成树就是给的图，n个点用n - 1条边连接起来，最短生成树就是这些边的总权重最小

Prim算法

这个问题可以抽象成一个最短路问题，点t到1的最短距离所走过的边数是唯一的，所以我们在求最短路的同时维护走过的路径数组就行

Prim算法的思路大致是这样，我们定义一个答案集合，就是所有已经确定是最短路的节点，我们用st来标记，然后，找到所有节点中距离答案集合最近的节点，用这个节点来更新其他所有节点到答案集合的距离，然后让它进入答案集合，一共进行n次入集合操作。

AcWing 858. Prim算法求最小生成树 - AcWing

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510,INF = 0x3f3f3f3f;

int g[N][N],dist[N],n,m;
bool st[N];

int prim()
{
    memset(dist,0x3f,sizeof dist); //初始化
    int res = 0; //存答案
    for(int i = 0;i < n;i ++) //n层迭代
    {
        int t = -1;
        for(int j = 1;j <= n;j ++) //找距离答案集合的最小边长
        {
            if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j; //如果点j没有进入答案集合，并且距离答案集合更小或者t==-1时（就是刚循环）
        }
        
        if(i && dist[t] == INF) return INF; //如果这层迭代不是第第一次也就是i == 0时，t距离集合没有变，还是无穷大那么就是题目给的节点不是联通的
        if(i) res += dist[t];
        
        for(int j = 1;j <= n;j ++) //以节点t更新其余没有进入答案集合的点到答案集合的最短距离
        {
            dist[j] = min(dist[j],g[t][j]);
        }
        st[t] = true;
        
    }
    
    return res;
}

int main()
{
    cin>>n>>m;
    
    memset(g,0x3f,sizeof g);
    int a,b,c;
    for(int i = 0;i < m;i ++)
    {
        cin>>a>>b>>c;
        g[a][b] = g[b][a] = min(g[a][b],c);
    }
    
    int t = prim();
    
    if(t == 0x3f3f3f3f) cout<<"impossible"<<endl;
    else
    {
        cout<<t<<endl;
    }
    
}

kruskal 算法

这个算法和Prim算法不同，这个算法是通过边长来做的，是求最小生成树的比较优秀的算法

这个算法的大致思路是，首先对所有的边进行排序，然后选取最小的边，如果，这个边的两个节点不在同一个连通块中，那么就可以加进去，如果不行，就往下一个边找，直到n - 1条边都到位为止

这个算法在询问是否在同一个连通块中还要用到并查集的知识。

AcWing 859. Kruskal算法求最小生成树 - AcWing

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 200010;
struct edge //用结构体来存边
{
    int a,b,w;
    
    bool operator<(const edge &W)const  //运算符重载
    {
        return w < W.w;
    }
}edges[N];
int p[N]; //并查集数组，用来询问两个点的祖宗节点是否是同一个，也就是两个点是否在同一个连通块

int find(int a) //查询函数，一直找到祖宗节点为止
{
    if(p[a] != a) p[a] = find(p[a]);
    else return p[a];
}



int main()
{
    int n,m;
    cin>>n>>m;
    int a,b,c;
    for(int i = 0;i < m;i ++)
    {
        cin>>a>>b>>c;
        edges[i] = {a,b,c};
    }
    
    for(int i = 1;i <= n;i ++)
    {
        p[i] = i;
    }
    
    
    sort(edges,edges + m); //给边排序，保证对边询问的顺序
    int res = 0,cnt = 0; //res记录边长之和，cnt记录计入答案集合边数个数
    for(int i = 0;i < m;i ++)
    {
        a = edges[i].a,b = edges[i].b,c = edges[i].w;
        a = find(a),b = find(b); //查询两节点是否在同一个连通块
        if(a != b) //如果不是，先把两个节点连通，更行答案和计数变量cnt
        {
            p[a] = b;
            res +=c;
            cnt ++;
        }
    }
    if(cnt < n - 1) cout<<"impossible"<<endl; //如果cnt，也就是边数小于n - 1，说明有一个点没有进去，图不能组成生成树
    else cout<<res<<endl;
    
}

二分图

二分图就是，左右连个集合，集合之间有边链接两个点，集合之内没有的图就叫二分图

染色法

这个算法的大致思路是：

我们需要对所有节点染色，所有颜色为1的节点是一边，为2的是一边，如果我们有一个未被染色的节点，我们把它初始化为1，然后对它的所有子节点进行染色，当然了，子节点染成不同的颜色，为2，染色完成后对下一个没有染色的点进行染色，在过程中如果遇到一个子节点被染色了但是颜色与上一个节点一样的话就不能组成二分图image

上面演示的是染色过后的图。

AcWing 860. 染色法判定二分图 - AcWing

#include<iostream>
#include<cstring>
using namespace std;

const int N = 100010,M = 200020;

int n,m;
int h[N],e[M],ne[M],idx;
int color[N];

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

bool dfs(int u,int c) //dfs遍历子节点
{
    color[u] = c; //首先对u进行染色
    
    for(int i = h[u];i != -1;i = ne[i]) //遍历子节点
    {
        int j = e[i];
        if(!color[j])
        {
            if(!dfs(j,3 - c)) //如果子节点的子节点染色的时候有冲突返回false
            {
                return false;
            }
        }else if(color[j] == c) return false; //如果节点的颜色等于上一个节点颜色返回false
        
        
    }
    
    return true;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    int a,b;
    for(int i = 0;i < m;i ++)
    {
        cin>>a>>b;
        add(a,b),add(b,a); //无向边，加两遍
    }
    
    for(int i = 1;i <= n;i ++)
    {
        if(!color[i]) //如果没有被染色
        {
            if(!dfs(i,1)) 
            {
                cout<<"No"<<endl;
                return 0;
            }
        }
    }
    
    cout<<"Yes"<<endl;
    return 0;
    
}

匈牙利算法

这个算法是在处理二分图的两部分之间的两个节点间只有一条边，我们要让边的总和最大

大致思路：

首先遇到一个没有配对的左节点，在它所有右节点中的子节点中寻找，找到没有被右节点配对的子节点，就算匹配成功，如果这没有配对的左节点，只有一个右节点能配对，恰巧这个右节点有左节点了，那么看这个已经配对的左节点能否换个节点，如果可以就换，不行，就返回false，答案不计入这个点

AcWing 861. 二分图的最大匹配 - AcWing

#include<iostream>
#include<cstring>

using namespace std;

const int N = 100100;

int h[N],e[N],ne[N],idx;
int n1,n2,m;
int match[N];
bool st[N];


int add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

bool find(int t) //查询函数
{
    for(int i = h[t];i != -1;i = ne[i]) //遍历所有子节点
    {
        int j = e[i];
        if(!st[j])
        {
            st[j] = true;
            if(match[j] == 0|| find(match[j])) //如果右节点没有配对或者右节点配对的子节点能换一个
            {
                match[j] = t; //j节点就配对t
                return true;
            }
        }
    }
    return false;//如果没有配对上就返回false
}


int main()
{
    cin>>n1>>n2>>m;
    memset(h,-1,sizeof h);
    int a,b;
    for(int i = 0;i < m;i ++)
    {
        cin>>a>>b;
        add(a,b);
    }
    int res = 0;
    for(int i = 1;i <= n1;i ++)
    {
        memset(st,0,sizeof st);
        if(find(i))  //配对上了就答案加一
        {
           res++;
        }
    }
    cout<<res<<endl;
    
}

标签：图论,dist,idx,int,++,搜索,include,节点
From： https://www.cnblogs.com/chhh31/p/18397885

相关文章

  • 图论连通性相关
    并查集普通并查集：路径压缩写法：structUnion_Find_Set{ intf[N]; inlinevoidinit(){ for(inti=1;i<=n;++i) f[i]=i; } inlineintfind(intx){ if(x!=f[x])f[x]=find(f[x]); returnf[x]; } inlinevoidmerge(inta,intb){ intx......
  • Java毕业设计 基于Springboot+Vue的文献搜索系统
    文末获取资源，收藏关注不迷路文章目录项目介绍技术介绍项目界面关键代码目录项目介绍文献搜索系统采用B/S架构,数据库是MySQL。网站的搭建与开发采用了先进的java进行编写,使用了springboot框架。该系统从两个对象：由管理员和用户来对系统进行设计构建。主要功能包括：......
  • Python | 爬虫实战——亚马逊搜索页监控（附详细源码）
    背景做亚马逊店铺，如果你的品卖爆了，免不得遇到被人跟品、广告关键词竞争甚至是恶意投诉等事情。如果靠人去检查产品是否正常，存在不及时的问题。所以，基本都会想要有一个自动检测的工具。一般是自动根据关键词，设置邮编，查看对应市场下的搜索结果页是否，然后进一步判断搜索结构页......
  • 代码随想录训练营 Day50打卡 图论part01 理论基础 98. 所有可达路径
    代码随想录训练营Day50打卡图论part01一、理论基础DFS（深度优先搜索）和BFS（广度优先搜索）在图搜索中的核心区别主要体现在搜索策略上：1、搜索方向：DFS：深度优先，一条路走到黑。DFS从起点开始，选择一个方向深入到底，遇到死胡同再回溯，换一个方向继续探索。这种方式适合解决路径......
  • [Python图论]在用图nx.shortest_path求解最短路径时，节点之间有多条边edge，会如何处理？
    问：在使用图求最短路径时，如果节点之间有多条路径，shortest_route=nx.shortest_path(G,source=start_node,target=end_node,weight='length')会如何处理，会自动选择最短那条吗？#输出图G各节点之间有多少条边edge,并给出其长度Edgesbetween103928and25508583:共2条Edge......
  • 每日搜索论坛总结：2024年8月30日
    以下是今天在搜索论坛上发生的事件回顾，通过搜索引擎圆桌会议和其他网络搜索论坛的视角。Yelp起诉了Google，搜索营销行业对此感到好笑。Google为GoogleAds推出了新标签诊断和同意管理设置。Google表示不会在页面上计数文字或链接。Google正在统一Google商务资料和Google本地服......
  • 算法与数据结构——AVL树（平衡二叉搜索树）
    AVL树在“二叉搜索树”章节提到，在多次插入和删除操作后，二叉搜索树可能退化为链表。在这种情况下，所有操作的时间复杂度将从O(logn)劣化为O(n)。如下图，经过两次删除节点操作，这棵二叉搜索树便会退化为链表再例如，下图所示的完美二叉树中插入两个节点后，树将严重向左倾斜，查找操作的......
  • 如何利用 API 中的用户行为数据进行商品搜索关键词优化？
    以下是一些根据API返回值优化商品搜索关键词的步骤：分析返回数据中的搜索流量分布：查看API提供的关于不同关键词搜索频次的数据。对于搜索频次高且与商品相关的关键词，重点考虑将其纳入或优化到商品关键词中。例如，如果API显示“智能手表”这个关键词在一周内有1000次......
  • vue3 地图（天地图，百度地图，腾讯地图，高德地图）封装组件调用 带地图搜索功能common_tencent
    废话不多说直接上组件代码：<template><!--地图--><divclass="containerw"><divid="map"class="mapradius-md":style="{width:width,height:height}"></div></div><......
  • Monocle：一款基于LLM的二进制文件自然语言搜索工具
    关于MonocleMonocle是一款基于LLM的二进制文件自然语言搜索工具，该工具由LLM驱动，用于对已编译的目标二进制文件执行自然语言搜索，并查找加密代码、密码字符串和安全缺陷漏等。功能介绍Monocle是一款由大型语言模型支持的工具，用于对已编译的目标二进制文件执行自然语言搜索......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99