邻接矩阵转换成邻接表

#include<bits/stdc++.h>
using namespace std;
const int N = 510,M = 100010,INF = 0x3f3f3f3f;
int n,m;
int g[N][N];
struct Node
{
    int id;
    int w;
    Node* next;
    Node(int id,int w):id(id),w(w),next(NULL){}
}*head[N];
void add(int a,int b,int w)
{
    auto p=new Node(b,w);
    p->next=head[a];
    head[a]=p;
}
void convert()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(g[i][j]<INF/2)
                add(i,j,g[i][j]);
}
int main()
{
    cin>>n>>m;
    memset(g,INF,sizeof g);
    while(m--)
    {
        int a,b,val;
        cin>>a>>b>>val;
        g[a][b]=g[b][a]=min(g[a][b],val);
    }
    cout<<"邻接矩阵表示法:"<<endl;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(g[i][j]>INF/2)cout<<"_"<<' ';
            else cout<<g[i][j]<<' ';
        }
        cout<<endl;
    }
    convert();
    cout<<"邻接表表示法(括号内表示权值):"<<endl;
    for(int i=1;i<=n;i++)
    {
        for(auto p=head[i];p;p=p->next)
            printf("%d(%d) ",p->id,p->w);
        cout<<endl;
    }
    return 0;
}

邻接表转换成邻接矩阵

假设没有重边

#include<bits/stdc++.h>
using namespace std;
const int N = 510,M = 100010,INF = 0x3f3f3f3f;
int n,m;
int g[N][N];
struct Node
{
    int id;
    int w;
    Node* next;
    Node(int id,int w):id(id),w(w),next(NULL){}
}*head[N];
void add(int a,int b,int w)
{
    auto p=new Node(b,w);
    p->next=head[a];
    head[a]=p;
}
void convert()
{
    for(int i=1;i<=n;i++)
    {
        for(auto p=head[i];p;p=p->next)
            g[i][p->id]=g[p->id][i]=p->w;
    }
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b,val;
        cin>>a>>b>>val;
        add(a,b,val);
        add(b,a,val);
    }
    cout<<"邻接表表示法(括号内表示权值):"<<endl;
    for(int i=1;i<=n;i++)
    {
        for(auto p=head[i];p;p=p->next)
            printf("%d(%d) ",p->id,p->w);
        cout<<endl;
    }
    memset(g,INF,sizeof g);
    convert();
    cout<<"邻接矩阵表示法:"<<endl;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(g[i][j]>INF/2)cout<<"_"<<' ';
            else cout<<g[i][j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}

带权值的用邻接表存的有向图的dfs

#include<bits/stdc++.h>
using namespace std;
const int N = 510,M = 100010,INF = 0x3f3f3f3f;
int n,m;
int g[N][N];
bool used[N];
struct Node
{
    int id;
    int w;
    Node* next;
    Node(int id,int w):id(id),w(w),next(NULL){}
}*head[N];
void add(int a,int b,int w)
{
    auto p=new Node(b,w);
    p->next=head[a];
    head[a]=p;
}
void dfs(int u)
{
    used[u]=true;
    cout<<u<<' ';
    for(auto p=head[u];p;p=p->next)
    {
        if(!used[p->id])
            dfs(p->id);
    }
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b,w;
        cin>>a>>b>>w;
        add(a,b,w);
    }
    for(int i=1;i<=n;i++)
        if(!used[i])
            dfs(i);
    return 0;
}

DFS邻接表(无权值)

#include<bits/stdc++.h>
using namespace std;
const int N = 510,M = 100010,INF = 0x3f3f3f3f;
int n,m;
int g[N][N];
bool used[N];
struct Node
{
    int id;
    Node* next;
    Node(int id):id(id),next(NULL){}
}*head[N];
void add(int a,int b)
{
    auto p=new Node(b);
    p->next=head[a];
    head[a]=p;
}
void dfs(int u)
{
    used[u]=true;
    cout<<u<<' ';
    for(auto p=head[u];p;p=p->next)
    {
        if(!used[p->id])
            dfs(p->id);
    }
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    for(int i=1;i<=n;i++)
    {
        cout<<i<<": ";
        for(auto p=head[i];p;p=p->next)
            cout<<p->id<<" -> ";
        cout<<"NULL"<<endl;
    }
    cout<<"----------------"<<endl;
    for(int i=1;i<=n;i++)
        if(!used[i])
            dfs(i);
    return 0;
}

DFS邻接矩阵(无权值)

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n,m;
int g[N][N];
bool used[N];
void dfs(int u)
{
    used[u]=true;
    cout<<u<<' ';
    for(int i=1;i<=n;i++)
    {
        if(g[u][i]&&!used[i])
            dfs(i);
    }
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        g[a][b]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            cout<<g[i][j]<<' ';
        cout<<endl;
    }
    cout<<"----------------"<<endl;
    for(int i=1;i<=n;i++)
        if(!used[i])
            dfs(i);
    return 0;
}

DFS非递归

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
bool used[N];
int n,m;
struct Node
{
    int id;
    Node* next;
    Node(int id):id(id),next(NULL){}
}*head[N];
void add(int a,int b)
{
    auto p=new Node(b);
    p->next=head[a];
    head[a]=p;
}
void dfs(int u)
{
    stack<int>s;
    s.push(u);
    while(s.size())
    {
        int t=s.top();
        s.pop();
        cout<<t<<' ';
        used[u]=true;
        for(auto p=head[t];p;p=p->next)
            if(!used[p->id])
                s.push(p->id);
    }
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    for(int i=1;i<=n;i++)
        if(!used[i])
            dfs(i);
    return 0;
}

BFS

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
bool used[N];
int n,m;
struct Node
{
    int id;
    Node* next;
    Node(int id):id(id),next(NULL){}
}*head[N];
void add(int a,int b)
{
    auto p=new Node(b);
    p->next=head[a];
    head[a]=p;
}
void bfs(int u)
{
    used[u]=true;
    queue<int>q;
    q.push(u);
    while(q.size())
    {
        int t=q.front();
        q.pop();
        cout<<t<<' ';
        for(auto p=head[t];p;p=p->next)
            if(!used[p->id])
                q.push(p->id),used[p->id]=true;
    }
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    for(int i=1;i<=n;i++)
        if(!used[i])
            bfs(i);
    return 0;
}

BFS拓扑排序

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n,m,q[N],d[N];
struct Node
{
    int id;
    Node* next;
    Node(int id):id(id),next(NULL){}
}*head[N];
void add(int a,int b)
{
    auto p=new Node(b);
    p->next=head[a];
    head[a]=p;
}
void topsort()
{
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++)
        if(d[i]==0)
            q[++tt]=i;
    while(hh<=tt)
    {
        int i=q[hh++];
        for(auto p=head[i];p;p=p->next)
        {
            int j=p->id;
            d[j]--;
            if(d[j]==0)
                q[++tt]=j;
        }
    }
    if(tt==n-1)
    {
        for(int i=0;i<n;i++)
            cout<<q[i]<<' ';
    }
    else
        cout<<-1;
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        d[b]++;
        add(a,b);
    }
    topsort();
    return 0;
}

DFS拓扑排序

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n,m,top,q[N];
bool used[N];//0未被访问,1访问中,2访问完毕
struct Node
{
    int id;
    Node* next;
    Node(int id):id(id),next(NULL){}
}*head[N];
void add(int a,int b)
{
    auto p=new Node(b);
    p->next=head[a];
    head[a]=p;
}
bool dfs(int u)
{
    used[u]=1;
    for(auto p=head[u];p;p=p->next)
    {
        int j=p->id;
        if(!used[j])
        {
            if(!dfs(j))return false;
        }
        else if(used[j]==1)
            return false;
    }
    q[top++]=u;
    used[u]=2;
    return true;
}
bool topsort()
{
    for(int i=1;i<=n;i++)
    {
        if(!used[i]&&!dfs(i))return false;
    }
    return true;
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    if(topsort())
    {
        for(int i=n-1;i>=0;i--)
        cout<<q[i]<<' ';
    }
    return 0;
}

BFS 两点之间是否存在路径

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n,m;
int ss=1,tt=2;
bool used[N];
struct Node
{
    int id;
    Node* next;
    Node(int id):id(id),next(NULL){}
}*head[N];
void add(int a,int b)
{
    auto p=new Node(b);
    p->next=head[a];
    head[a]=p;
}
bool bfs(int u)
{
    queue<int>q;
    q.push(u);
    used[u]=true;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        if(t==tt)printf("%d %d之间存在路径",ss,tt);
        for(auto p=head[t];p;p=p->next)
        {
            int j=p->id;
            if(!used[j])
                used[j]=true,q.push(j);
        }
    }
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    bfs(ss);
    return 0;
}

DFS 两点之间是否存在路径

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n,m;
int ss=1,tt=2;
bool used[N];
struct Node
{
    int id;
    Node* next;
    Node(int id):id(id),next(NULL){}
}*head[N];
void add(int a,int b)
{
    auto p=new Node(b);
    p->next=head[a];
    head[a]=p;
}
bool dfs(int u)
{
    used[u]=true;
    if(u==tt)printf("%d %d之间存在路径",ss,tt);
    for(auto t=head[u];t;t=t->next)
    {
        int j=t->id;
        if(!used[j])
            dfs(j);
    }
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    dfs(ss);
    return 0;
}

BFS求具体路径

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
bool used[N];
int pre[N];
int ss=1,tt=6;
struct Node
{
    int id;
    Node* next;
    Node(int id):id(id),next(NULL){}
}*head[N];
void add(int a,int b)
{
    auto p=new Node(b);
    p->next=head[a];
    head[a]=p;
}
void bfs(int u)
{
    pre[u]=-1;
    used[u]=true;
    queue<int>q;
    q.push(u);
    while(q.size())
    {
        int t=q.front();
        q.pop();
        if(t==tt)
        {
            printf("%d到%d存在路径:\n",ss,tt);
            vector<int>path;
            for(int i=tt;i!=-1;i=pre[i])
            {
                path.push_back(i);
            }
            reverse(path.begin(),path.end());
            for(int i=0;i<path.size();i++)
            {
                cout<<path[i];
                if(i!=(path.size()-1))cout<<" -> ";
            }
            return;
        }
        for(auto p=head[t];p;p=p->next)
        {
            int j=p->id;
            if(!used[j])
            {
                used[j]=true;
                pre[j]=t;
                q.push(j);
            }
        }
    }
    printf("%d到%d不存在路径!\n",ss,tt);
    return;
}
int main()
{
    int n,m;
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    bfs(ss);
    return 0;
}

DFS——退出递归时输出对应树的后序遍历(联想上节课树中找m到n的路径后续遍历的写法)

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
bool used[N];
int ss=1,tt=6;
struct Node
{
    int id;
    Node* next;
    Node(int id):id(id),next(NULL){}
}*head[N];
void add(int a,int b)
{
    auto p=new Node(b);
    p->next=head[a];
    head[a]=p;
}
bool dfs(int u)
{
    used[u]=true;
    if(u==tt)
    {
        cout<<u;
        return true;
    }
    for(auto p=head[u];p;p=p->next)
    {
        if(!used[p->id])
        {
            if(dfs(p->id))
            {
                cout<<" <- "<<u;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int n,m;
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    if(!dfs(ss))
        printf("%d之间%d不存在路径\n",ss,tt);
    return 0;
}

DFS——（全排列）回溯 对应 树的先序遍历的改写

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n,m;
int ss=1,tt=6;
vector<int>path;
bool used[N];
struct Node
{
    int id;
    Node* next;
    Node(int id):id(id),next(NULL){}
}*head[N];
void add(int a,int b)
{
    auto p=new Node(b);
    p->next=head[a];
    head[a]=p;
}
bool dfs(int u)
{
    used[u]=true;
    path.push_back(u);
    if(u==tt)
    {
        printf("%d %d之间存在路径:",ss,tt);
        for(int i=0;i<path.size();i++)
            cout<<path[i]<<' ';
        return true;
    }
    for(auto t=head[u];t;t=t->next)
    {
        int j=t->id;
        if(!used[j])
        {
            if(dfs(j))
                return true;
        }
    }
    path.pop_back();
    return false;
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    if(!dfs(ss))
    {
        printf("%d %d之间不存在路径",ss,tt);
    }
    return 0;
}

改写树的先序遍历，求 m 到 n 的路径

#include<bits/stdc++.h>
using namespace std;
vector<int>path;
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val):val(val),left(NULL),right(NULL){}
};
void preorder(TreeNode* root,TreeNode* n)
{
    if(!root)return;
    path.push_back(root->val);
    if(root==n)
    {
        for(int x : path)
            cout<<x<<' ';
        return;
    }
    preorder(root->left,n);
    preorder(root->right,n);
    path.pop_back();
}
int main() 
{
    TreeNode* root = new TreeNode(1);     
    root->left = new TreeNode(2);         
    root->right = new TreeNode(3);        
    root->left->left = new TreeNode(4);   
    root->left->right = new TreeNode(5);  
    root->right->left = new TreeNode(6);  
    root->right->right = new TreeNode(7); 
    TreeNode* m = root;                   
    TreeNode* n = root->right->left;      
    preorder(m, n);                       
    return 0;
}

假设图用邻接表表示,设计一个算法,输出从顶点s到顶点t的所有简单路径

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
bool used[N];
int n,m,k;
vector<int>path;
struct Node
{
    int id;
    Node* next;
    Node(int id):id(id),next(NULL){}
}*head[N];
void add(int a,int b)
{
    auto p=new Node(b);
    p->next=head[a];
    head[a]=p;
}
void dfs(int s,int t)
{
    if(s==t)
    {
        for(int x : path)
            cout<<x<<' ';
            cout<<endl;
        return;
    }
    for(auto p=head[s];p;p=p->next)
    {
        int j=p->id;
        if(!used[j])
        {
            path.push_back(j);
            used[j]=true;
            dfs(j,t);
            used[j]=false;
            path.pop_back();
        }
    }
}
int main()
{
    cin>>n>>m>>k;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    while(k--)
    {
        int s,t;
        cin>>s>>t;
        printf("%d之间%d所有的路径为:\n",s,t);
        used[s]=true;
        path.push_back(s);
        dfs(s,t);
        used[s]=false;
        path.pop_back();
        cout<<endl;
    }
    return 0;
}

朴素版Prim算法

#include<bits/stdc++.h>
using namespace std;
const int N = 510,M = 100010;
int g[N][N],dist[N];
bool used[N];
int n,m;
int prim()
{
    int res=0;
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!used[j]&&(t==-1||dist[j]<dist[t]))
                t=j;
        if(dist[t]==0x3f3f3f3f)return 0x3f3f3f3f;
        used[t]=true;
        res+=dist[t];
        for(int j=1;j<=n;j++)
            if(!used[j])
                dist[j]=min(dist[j],g[t][j]);
    }
    return res;
}
int main()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    while(m--)
    {
        int a,b,w;
        cin>>a>>b>>w;
        g[a][b]=g[b][a]=min(w,g[a][b]);
    }
    int t=prim();
    if(t==0x3f3f3f3f)cout<<"impossible";
    else cout<<t;
    return 0;
}

Kruskal算法

#include<bits/stdc++.h>
using namespace std;
const int N = 510, M = 100010, INF = 0x3f3f3f3f;
int n,m,p[N];
struct edge
{
    int a;
    int b;
    int w;
    bool operator < (const edge& t)const{
        return w<t.w;
    }
}e[M];
int find(int x)
{
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        p[i]=i;
    for(int i=0;i<m;i++)
        cin>>e[i].a>>e[i].b>>e[i].w;
    sort(e,e+m);
    int res=0,cnt=0;
    for(int i=0;i<m;i++)
    {
        int a=e[i].a,b=e[i].b;
        if(find(a)!=find(b))
        {
            res+=e[i].w;
            cnt++;
            p[find(a)]=find(b);
        }
    }
    if(cnt==n-1)
        cout<<res;
    else
        cout<<"impossible";
    return 0;
}

朴素版dijkstra

#include<bits/stdc++.h>
using namespace std;
const int N = 510,M = 100010,INF=0x3f3f3f3f;
int g[N][N],dist[N];
bool st[N];
int n,m;
void dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    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]))
                t=j;
        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        st[t]=true;
    }
    if(dist[n]==0x3f3f3f3f) cout<<-1;
    else cout<<dist[n];
}
int main()
{
    cin>>n>>m;
    memset(g,0X3f,sizeof g);
    while(m--)
    {
        int a,b,w;
        cin>>a>>b>>w;
        g[a][b]=min(g[a][b],w);
    }
    dijkstra();
    return 0;
}

堆优化版dijkstra

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int e[N],ne[N],h[N],w[N],idx;
int n,m;
int dist[N];
bool used[N];
typedef pair<int,int> PII;
void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>>heap;
    heap.push({0,1});
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int ver=t.second,distance=t.first;
        if(used[ver])continue;
        used[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()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<dijkstra();
    return 0;
}

floyd

#include<bits/stdc++.h>
using namespace std;
const int N = 210,INF = 0x3f3f3f3f;
int d[N][N];
int n,m,k;
void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(i==j)d[i][j]=0;
            else d[i][j]=INF;
        }
    while(m--)
    {
        int a,b,w;
        cin>>a>>b>>w;
        d[a][b]=min(d[a][b],w);
    }
    floyd();
    while(k--)
    {
        int a,b;
        cin>>a>>b;
        if(d[a][b]<INF/2)cout<<d[a][b]<<endl;
        else cout<<"impossible"<<endl;
    }
    return 0;
}

bellman-ford

#include<bits/stdc++.h>
using namespace std;
const int M = 10010,N = 510,INF=0x3f3f3f3f;
int n,m,k;
int back[N],dist[N];
struct Edge
{
    int a,b,w;
}edge[M];
void bellman_ford()
{
    memset(dist,INF,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++)
    {
        memcpy(back,dist,sizeof dist);
        for(int j=0;j<m;j++)
        {
            Edge e=edge[j];
            dist[e.b]=min(dist[e.b],back[e.a]+e.w);
        }
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        edge[i]={x,y,z};
    }
    bellman_ford();
    if(dist[n]>INF/2)cout<<"impossible";
    else cout<<dist[n];
    return 0;
}