数据结构与算法——图论

简介: 题型1:拓扑排序 1)使用一个入度数组indegree来记录每个顶点的入度数,并使用一个变量来记录已经访问的顶点数 2)将入度为0的顶点压入栈中 3)将栈顶的元素删除。访问的顶点数加1.并将入该顶点相邻的所有顶点的入度数减1,如果减1之后的入度数为0,则将其压入栈中; 4)重复上面的过程,直到栈中的元素为空。

题型1:拓扑排序

1)使用一个入度数组indegree来记录每个顶点的入度数,并使用一个变量来记录已经访问的顶点数

2)将入度为0的顶点压入栈中

3)将栈顶的元素删除。访问的顶点数加1.并将入该顶点相邻的所有顶点的入度数减1,如果减1之后的入度数为0,则将其压入栈中;

4)重复上面的过程,直到栈中的元素为空。

5)判读访问的顶点数是否等于图的顶点数,看拓扑排序是否成功

实现代码:

status TopoLogicalSort(ALGraph G)
{
    //有向图G采用邻接表存储结构
    //若G无回路,则返回G的顶点的一个拓扑序列并返回OK,否则返回error
    finddegree(G,indegree);
    initstack(s);
    for(i=0;i<G.vexnum;++i)
        if(!indegree[i]) push(s,i);
    count=0;
    while(!stackempty(s))
    {
        pop(s,i);
        cout<<s<<' ';
        ++count;
        for(p=G.vetices[i].furstarc;p;p=p->next)
        {
            k=p->adjvex; 
            if(!(--indegree[k])) push(s,k);
        }
    }
    if(count<G.vexnum)
        cout<<error<<endl;
    else
        cout<<success<<endl;
}

2 深度优先遍历

int visited[N];
void DFS(Graph G,int v)
{
    visited[v]=1;
    cout<<v<<' ';
    for(w=firstAdjVex(G,v),w>=0;w=NextAdjVex(G,v,w))
    {
        if(!visited[w])
            DFS(G,w);
    }
}

void DFSsearch(Graph G)
{
    for(v=0;v<G.vexnum;++v)
        vistied[v]=0;
    for(v=0;v<G.vexnum;++v)
        DFS(G,v);
}

3 广度优先遍历

int visited[N];
void BFSsearch(Graph G)
{
    for(v=0;v<G.vexnum;++v)
        visited[v]=0;
    Initqueue(Q);
    for(v=0;v<G.vexnum;v++)
    {
        if(!visited[v])
        {
            visited[v]=1;
            cout<<v<<' ';
            Enqueue(Q,v);
            while(!QueueEmpty(Q))
            {
                DeQueue(Q,u);
                for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
                {
                    if(!visited[w])
                    {
                        visited[w]=1;
                        cout<<w<<' ';
                        EnQueue(Q,w);
                    }
                }
            }
        }
    }
}

 

 

 

相关文章
|
10天前
|
算法 编译器 C++
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
|
10月前
|
机器学习/深度学习 安全 算法
【图论】【割点】【C++算法】928. 尽量减少恶意软件的传播 II
【图论】【割点】【C++算法】928. 尽量减少恶意软件的传播 II
|
10月前
|
算法 测试技术 C++
【动态规划】【图论】【C++算法】1575统计所有可行路径
【动态规划】【图论】【C++算法】1575统计所有可行路径
|
10月前
|
算法 测试技术 C++
【动态规划】【图论】【C++算法】1928规定时间内到达终点的最小花费
【动态规划】【图论】【C++算法】1928规定时间内到达终点的最小花费
|
10天前
|
存储 算法 iOS开发
【狂热算法篇】并查集:探秘图论中的 “连通神器”,解锁动态连通性的神秘力量(通俗易懂版)
【狂热算法篇】并查集:探秘图论中的 “连通神器”,解锁动态连通性的神秘力量(通俗易懂版)
|
10天前
|
存储 算法 测试技术
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
|
4月前
|
JSON 算法 数据挖掘
基于图论算法有向图PageRank与无向图Louvain算法构建指令的方式方法 用于支撑qwen agent中的统计相关组件
利用图序列进行数据解读,主要包括节点序列分析、边序列分析以及结合节点和边序列的综合分析。节点序列分析涉及节点度分析(如入度、出度、度中心性)、节点属性分析(如品牌、价格等属性的分布与聚类)、节点标签分析(如不同标签的分布及标签间的关联)。边序列分析则关注边的权重分析(如关联强度)、边的类型分析(如管理、协作等关系)及路径分析(如最短路径计算)。结合节点和边序列的分析,如子图挖掘和图的动态分析,可以帮助深入理解图的结构和功能。例如,通过子图挖掘可以发现具有特定结构的子图,而图的动态分析则能揭示图随时间的变化趋势。这些分析方法结合使用,能够从多个角度全面解读图谱数据,为决策提供有力支持。
159 0
|
算法 存储 内存技术
【AcWing算法基础课】第三章 搜索与图论(2)
特点:尽可能先向纵深方向搜索。使用stack实现。所需空间O(h)(h为深度)。不具有“最短性”。
100 0
【AcWing算法基础课】第三章 搜索与图论(2)
|
10月前
|
算法 Python
Python中实现图论算法
Python中实现图论算法 “【5月更文挑战第20天】”
69 3
|
9月前
|
算法 数据挖掘 定位技术
算法必备数学基础:图论方法由浅入深实践与应用
算法必备数学基础:图论方法由浅入深实践与应用