图论代码

邻接表、邻接矩阵转化

//邻接矩阵
int n,m;
int g[N][N];

//邻接表，每个节点存一张表
struct Node
{
    int id;//编号
    int w;//权值
    Node* next;
    Node (int _id) : id(_id), next(NULL){};
}*head[N];

void convert()//邻接矩阵转化成邻接表
{
    for(int i = 1; i <= n; i++)
        for(auto p = head[u]; p; p = p->next)
        {
            int j = p->id;
            g[i][j] = g[j][i] = p->w;
        }
}

void convert()//邻接表转化成邻接矩阵
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        if(g[i][j] <= N/2) add(i,j,g[i][j]);
}

dfs邻接表

//dfs
#include <iostream>
#include <cstring>

using namespace std;

const int N = 510;

bool st[N];

//邻接表，每个节点存一张表
struct Node
{
    int id;//编号
    int w;//权值
    Node* next;
    Node (int _id) : id(_id), next(NULL){};
}*head[N];

void add(int a,int b)
{
    Node* p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

void dfs(int u)
{
    st[u] = 1;

    cout<<u<<' ';
    for(auto p = head[u]; p; p = p->next)
    {
        int j = p->id;

        if(!st[j]) dfs[j];
    }
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);

    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    for(int i = 1; i <= n; i++)
    {
        printf("%d: ",i);
        for(auto p = head[i]; p; p = p->next)
        printf("%d -> ",p->id);
        puts("NULL");
    }
    puts("-------------------");

    for(int i = 1; i <= n; i++)
    if(!st[i]) dfs[i];

}

//dfs 邻接矩阵

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510;

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

void dfs(int u)
{
    st[u] = true;
    cout<<u<<' ';

    for(int i = 1; i <= n; i++)
    if(g[u][i] && !st[i]) dfs(i);
}

int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        scanf("%d%d",&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;
    }

    puts("-------------------");

    for(int i = 1; i < n; i++)
    if(!st[i]) dfs(i);

    return 0;
}

dfs 非递归——借助栈

#include <iostream>
#include <cstring>
#include <stack>

using namespace std;

const int N = 100010, M = 100010;
int n,m;
int a,b;

struct Node
{
    int id;
    int w;
    Node* next;
    Node (int _id) : id(_id),next(NULL){};
}*head[N];

bool st[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);
    st[u] = true;

    while(s.size())
    {
        int t = s.top();
        s.pop();

        cout<<t<<' ';
        for(auto p = head[u]; p; p = p->next)
        {
            int j = p->id;
            if(!st[j])
            {
                st[j] = true;
                s.push(j);
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);

    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }

    for(int i = 1; i <= n; i++)
        if(!st[i]) dfs(i);

    return 0;
}

bfs 邻接表——借助队列

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

// include <bits/stdc++.h>

using namespace std;

const int N = 510;

int n,m;
bool st[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 bfs(int u)
{
    queue<int> q;
    q.push(u);
    st[u] = true;

    while(q.size())
    {
        int t = q.front();
        q.pop();

        cout<<t<<' ';
        for(auto p = head[t]; p; p = p->next)
        {
            int j = p->id;
            if(!st[j])
            {
                st[j] = true;    
                q.push(j);
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);

    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }

    for(int i = 1; i <= n; i++)
    if(!st[i]) bfs(i);

    return 0;
}