投稿
  1. 高性能架构探索首页
  2. C/C++

图的一些应用

admin • • C/C++ • 阅读 130

打击薄弱板块，将算法进行到底

大致路线

一、图的概念和建立

定义

表示了一种“多对多”的关系

常见的分类有无向图和有向图

图的存储

1、邻接矩阵表示

将图的联通关系体现在一个方阵上

若是中的边否则

特征

对角线元素全 0 关于对角线对称

优点：

  • 直观、简单、好理解 方便检查任意一对顶点间是否存在边 方便找任一顶点的所有邻接点 方便计算任一顶点的度 无向图：对应行（或列）非 0 元素的个数 有向图：对应行非 0 元素的个数是出度；对应列非 0 元素的个数是入度

缺点：

  • 浪费空间——存稀疏图 浪费时间——统计稀疏图的边

实现代码

#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
int G[MAXN][MAXN],Nv,Ne;
​
void BuildGraph(){
    int i,j,v1,v2,w;
    scanf("%d",&Nv);
    // 初始化图 
    for(i=0;i<Nv;i++) 
        for(j=0;j<Nv;j++)
            G[i][j] = 0;
    scanf("%d",&Ne);
    // 插入边 
    for(i=0;i<Ne;i++){
        scanf("%d %d %d",&v1,&v2,&w);
        G[v1][v2] = w;
        G[v2][v1] = w;
    }
}
// 遍历图
void print(){
    int i,j;
    for(i=0;i<Nv;i++){
        for(j=0;j<Nv;j++)
            printf("%d ",G[i][j]);
        printf("n");
    }
} 
​
int main(){
    BuildGraph();
    print();
    return 0;
}

2、邻接表表示

用一个指针数组储存每一条路 1-->2-->NULL

特征

  • 方便找任一顶点的所有邻接顶点
  • 节省稀疏图的空间

需要 N 个头指针 + 2*E 个结点（每个结点至少 2 个域）

  • 对于是否方便计算任一顶点的度

无向图：方便

有向图：只能计算出度

  • 不方便检查任意一对顶点间是否存在边

实现代码

#include<stdio.h>
#include<stdlib.h>
#define MaxVertexNum 100
typedef struct AdjVNode *AdjList;
struct AdjVNode{
    int weight;  // 权值 
    int adjv;   // 下标 
    AdjList next;  // 其后一个 
};
AdjList Graph[MaxVertexNum];
int Ne,Nv;
​
// 建图
void BuildGraph(){
    int i;
    int v1,v2,w;
    AdjList NewNode;
    scanf("%d",&Nv);
    for(i=0;i<Nv;i++){
        Graph[i] = (AdjList)malloc(sizeof(struct AdjVNode));
        Graph[i]->adjv = i;
        Graph[i]->next = NULL;
    }
    scanf("%d",&Ne);
    for(i=0;i<Ne;i++){
        scanf("%d %d %d",&v1,&v2,&w);
        NewNode = (AdjList)malloc(sizeof(struct AdjVNode));
        NewNode->adjv = v1;
        NewNode->weight = w;

        NewNode->next = Graph[v2]->next;
        Graph[v2]->next = NewNode;

        NewNode = (AdjList)malloc(sizeof(struct AdjVNode));
        NewNode->adjv = v2;
        NewNode->weight = w;

        NewNode->next = Graph[v1]->next;
        Graph[v1]->next = NewNode;
    }
} 
​
void print(){
    AdjList tmp;
    int i;
    for(i=0;i<Nv;i++){
        tmp = Graph[i];
        while(tmp){
            printf("%d ",tmp->adjv);
            tmp = tmp->next;
        }
        printf("n");
    }
}
​
int main(){

    BuildGraph();
    print();
    return 0;
}

 

二、图的遍历

1、DFS

类似于图的先序遍历，首先访问该顶点，然后依次从V0的各个未被访问过的邻接点出发进行深度优先搜索遍历。 时间复杂度：若有N个顶点，E条边 邻接表存储图O(N+E) 邻接矩阵存储图O(N^2)

/* 邻接表存储的图 - DFS */
void Visit( Vertex V ){
    printf("正在访问顶点%dn", V);
}
/* Visited[]为全局变量，已经初始化为false */
void DFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) ){   
    /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */
    PtrToAdjVNode W;
    Visit( V ); /* 访问第V个顶点 */
    Visited[V] = true; /* 标记V已访问 */

    for( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
        if ( !Visited[W->AdjV] )    /* 若W->AdjV未被访问 */
            DFS( Graph, W->AdjV, Visit );    /* 则递归访问之 */
}

 

看到这可以回去看看以前写的八皇后问题...

2、BFS

广度优先搜索（Breadth First Search） 把自己的孩子遍历完，再轮着自己的兄弟（这就是有了孩子忘了兄弟） 时间复杂度（和dfs一样）：若有N个顶点，E条边 邻接表存储图O(N+E) 邻接矩阵存储图O(N^2)

/* 邻接矩阵存储的图 - BFS */
/* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边，即W是否V的邻接点。  */
/* 此函数根据图的不同类型要做不同的实现，关键取决于对不存在的边的表示方法。*/
/* 例如对有权图, 如果不存在的边被初始化为INFINITY, 则函数实现如下:         */
bool IsEdge( MGraph Graph, Vertex V, Vertex W {
    return Graph->G[V][W]<INFINITY ? true : false;
}
/* Visited[]为全局变量，已经初始化为false */
void BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) ){  
     /* 以S为出发点对邻接矩阵存储的图Graph进行BFS搜索 */
    Queue Q;     
    Vertex V, W;

    Q = CreateQueue( MaxSize ); /* 创建空队列, MaxSize为外部定义的常数 */
    /* 访问顶点S：此处可根据具体访问需要改写 */
    Visit( S );
    Visited[S] = true; /* 标记S已访问 */
    AddQ(Q, S); /* S入队列 */

    while ( !IsEmpty(Q) ) {
        V = DeleteQ(Q);  /* 弹出V */
        for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            /* 若W是V的邻接点并且未访问过 */
            if ( !Visited[W] && IsEdge(Graph, V, W) ) {
                /* 访问顶点W */
                Visit( W );
                Visited[W] = true; /* 标记W已访问 */
                AddQ(Q, W); /* W入队列 */
            }
    } /* while结束*/
}

 

三、DAG和拓扑排序

2、拓扑排序

拓扑排序主要用来解决有向无环图，常用来描述一个工程或系统的进行过程。

有向无环图分类

①AOV网：用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网(Activity On Vertex network). ②AOE网：以弧表示活动，以顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称为AOE网(Activity On Edge).

拓扑序

如果图中从v到w有一条有向路径，则v一定排在w之前。满足此条件的顶点序列称为一个拓扑序 获得一个拓扑序的过程就是拓扑排序 注意！！能进行拓扑序的一定是DAG.

实现思路： //用一个队列Q盛放没有前驱结点的点，每次从中取出一个 1.在有向图中选择一个没有前驱的顶点并输出（Indegree[V]==0） 2.从图中删除该顶点和所有以它为尾的弧（后驱的indegree--） 重复这两步，直到Q为空

//此种算法的复杂度为T=O(|V|+|E|)
bool TopSort( LGraph Graph, Vertex TopOrder[] )
{ /* 对Graph进行拓扑排序,  TopOrder[]顺序存储排序后的顶点下标 */
    int Indegree[MaxVertexNum], cnt;
    Vertex V;
    PtrToAdjVNode W;
       Queue Q = CreateQueue( Graph->Nv );

    /* 初始化Indegree[] */ 
    for (V=0; V<Graph->Nv; V++)
        Indegree[V] = 0;

    /* 遍历图，得到Indegree[] */
    for (V=0; V<Graph->Nv; V++)
        for (W=Graph->G[V].FirstEdge; W; W=W->Next)
            Indegree[W->AdjV]++; /* 对有向边<V, W->AdjV>累计终点的入度 */

    /* 将所有入度为0的顶点入列 */
    for (V=0; V<Graph->Nv; V++)
        if ( Indegree[V]==0 )
            AddQ(Q, V);      
    /* 准备工作完成下面进入拓扑排序 */ 
    cnt = 0; 
    while( !IsEmpty(Q) ){
        V = DeleteQ(Q); /* 弹出一个入度为0的顶点 */
        TopOrder[cnt++] = V; /* 将之存为结果序列的下一个元素 */
        /* 对V的每个邻接点W->AdjV */
        for ( W=Graph->G[V].FirstEdge; W; W=W->Next )
            if ( --Indegree[W->AdjV] == 0 )/* 若删除V使得W->AdjV入度为0 */
                AddQ(Q, W->AdjV); /* 则该顶点入列 */ 
    } /* while结束*/
​
    if ( cnt != Graph->Nv )
        return false; /* 说明图中有回路, 返回不成功标志 */ 
    else
        return true;
}

 

拓扑排序练习

http://hihocoder.com/problemset/problem/1174

//拓扑排序判断所在图是否有环路
bool topsort(){
    while(!q.empty()) q.pop();
    num=0;
    for(int i=1;i<=n;i++) if(!InDeg[i]) q.push(i);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        num++;
        for(int i=0;i<vec[now].size();i++){
            if(--InDeg[vec[now][i]]==0) q.push(vec[now][i]);
        }
    }
    if(num==n) return true;
    else return false;
}

四、本周习题

P1347 图的遍历

完成时间 2020/4/21

题解

第一次看到这个题的时候就在思考能不能从后往前遍历，最后再从前往后输出，因为小的数是一定会往大的数，如果记忆化了大点的最终位置 用一个vis[i]表示改点，当小点走到这个点时直接输出vis即可，0分...

后来参考了一下洛谷的题解发现只需要反向建边dfs就可以了 ，循环从N到1，则每个点i能访问到的结点的A值都是i，每个点访问一次，这个A值就是最优的，因为之后如果再访问到这个结点那么答案肯定没当前大了

中心思想：dfs+记忆化搜索

第一遍提交：

看错了数据范围，规定数组为1001X1001，拿到了60分

第二遍提交：

将数组改为10001X10001 ，导致结果 "size of array is too large"，提交洛谷显示Compile Error

第三遍提交：

用vector代替数组...100分

AC代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>a[100001];
int vis[100001];
void dfs(int x,int y){
    if(vis[x]){
        return;
    }
    vis[x]=y;
    for(int i=0;i<a[x].size();i++){
        dfs(a[x][i],y);
    }
}
​
int main(){
    cin>>n>>m;
    while(m--){
        int x,y;
        cin>>x>>y;
        a[y].push_back(x);
    }
    for(int i=n;i>0;i--){
        dfs(i,i);
    }
    for(int i=1;i<=n;i++){
        cout<<vis[i]<<" ";
    }
    return 0;
}
另解

https://www.luogu.com.cn/blog/hongzy/solution-p3916

P1347 排序

完成时间 2020/4/24

题解

对拓扑排序的变形...提交了两遍才通过

分为4种情况

  1. 图无环且最终输出的环的节点个数但节点数不等于n

  2. 图无环且最终输出的环的节点个数且节点数等于n

  3. 图有环

  4. 无法根据这些关系确定元素的顺序

题解都在酒（代码）里

AC代码
#include<bits/stdc++.h> 
using namespace std;
const int maxn=261;
​
int n,m,u,v,num;
int InDeg[maxn];//保存每次加边后的图
int Deg[maxn];//本次加边后的图
vector<int>vec[maxn];//存边的数组
queue<int>q;//存拓扑序的队列
char que[maxn]; //存每次拓扑序的元素排序
char quee[maxn];//存符合排序的最终排序
int qq[maxn];//一个用来已经输入了多少个点的工具人
int flag1,flag2;//条件判断你的flag
​
int topsort(){
    while(!q.empty()) q.pop(); //清空队列
    num=0;//清空拓扑排序的num
    memset(que,0,sizeof(que));//清空存放元素的数组
    for(int i=1;i<=n;i++){//初始化
        Deg[i]=InDeg[i];
    }
    for(int i=1;i<=n;i++){//将入度为0的元素压入队列
        if(!Deg[i]){
            q.push(i);  
        }
    }
    while(!q.empty()){//出队过程
        int now=q.front();
        q.pop();
        num++;
        que[num]=now+'A'-1;
        for(int i=0;i<vec[now].size();i++){
            if(--Deg[vec[now][i]]==0) q.push(vec[now][i]);
        }
    }
    if(num==n){//完美
        return 1;
    }else if(num<n){//有环了，错了 
        return 2;
    }else{//还不够
        return 3;
    }   
}
​
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        string a;
        cin>>a;
        u=a[0]-'A'+1;
        v=a[2]-'A'+1;
        qq[u]++;
        qq[v]++;
        vec[u].push_back(v);
        InDeg[v]++;
        int e=1;
        for(e=1;e<=n;e++){
            if(!qq[e]){
                break;
            }
        }
        if(topsort()==3){
            continue;
        }else if(topsort()==2){
            if(!flag1){
                flag1=i;
            }
            continue;
        }else{
            if(e==n+1){//必须要让全部的边包含才可以算是正确结果
                if(!flag2){
                    flag2=i;
                }
                for(int i=1;i<=num;i++){
                    quee[i]=que[i];
                }
                continue;
            }   
        }
    }
if(flag1){
cout<<"Inconsistency found after "<<flag1<<" relations.";
    }else if(flag2){
cout<<"Sorted sequence determined after "<<flag2<<" relations: ";
for(int i=1;i<=n;i++){
printf("%c",quee[i]);
    }
cout<<".";
    }else{
cout<<"Sorted sequence cannot be determined.";
    }
return 0;
}

 

另解

https://www.luogu.com.cn/blog/rated/solution-p1347

P1347 词链

题解

将字符串进行字典序排序，用dfs进行深搜，第一个得到的就是答案。和上一题有点像...

AC代码
#include<iostream>
#include<map>
#include<string>
#include<algorithm>
using namespace std;
const int MAXN=100001;
map<char,int>s1,s2;//存每个字符串的第一位和最后一位出现的次数
int n,sum;
string a[MAXN];//存字符串
string ans[MAXN];//最终答案的顺序
string now[MAXN];//当前遍历的数组的顺序
int vis[MAXN];//是否已经走过
int flag=0;
​
void dfs(int x,int y){
    if(flag==1) return;//找到答案了就返回，莫回头
    if(y==n){//标记现场
        flag=1;
        for(int i=1;i<=sum;i++){
            ans[i]=now[i];
        }
        return;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        if(a[x][a[x].length()-1]==a[i][0]){//如果可以拼接
            now[++sum]=a[i];
            vis[i]=1;
            dfs(i,y+1);
            sum--;
            vis[i]=0;
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s1[a[i][0]]++;
        s2[a[i][a[i].length()-1]]++;
    }
    sort(a+1,a+n+1);//字典序排序
    int start=1;
    for(int i=1;i<=n;i++){
        if(s1[a[i][0]]-s2[a[i][0]]==1){
            start=i;
            break;
        }
    }
    vis[start]=1;
    now[++sum]=a[start];
    dfs(start,1);
    if(flag==0){
        cout<<"***";
        return 0;
    }
    for(int i=1;i<n;i++){
        cout<<ans[i]<<".";
    }
    cout<<ans[n];
    return 0;
}

 

 

原文链接: https://www.cnblogs.com/chaos1203/p/13306982.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    图的一些应用

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/366721

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 下午4:56
下一篇 2023年3月2日 下午4:56

相关推荐