数据结构研究之九 图

时间：2022-08-09 10:30:45
1.图的种类：
a.有向图，无向图，加权有向图，加权无向图
b.连接两个顶点u,v的边记作e=(u,v)
c.不存在环的有向图称为DAG

2.图的邻接矩阵：
a.优点：可以通过M[u][v]直接引用边(u,v)，因此只需要常数时间(O(1))即可确定顶点u和顶点v的关系；只要更改M[u][v]只就能完成边的添加与删除，简单且高效
b.缺点：消耗的内存空间等于顶点数的平方。如果图的边数较少，就会浪费较大量的内存；在同一个邻接矩阵中，只能记录顶点u到顶点v的一个关系

c.代码：

//
// Created by 叶子 on 2018/2/5.
// 邻接矩阵的表示
//

#include "iostream"
using namespace std;
static const int N = 100;

int main(){
    int M[N][N];
    int n,u,k,v;

    cin >> n;

    for ( int i = 0 ; i < n ; i ++){
        for ( int j = 0 ; j < n ; j ++ ) M[i][j] = 0 ;
    }

    for ( int i = 0 ; i < n ; i ++){
        cin >> u >> k;
        u --;
        for ( int j = 0 ; j < k ; j ++){
            cin >> v;
            v --;
            M[u][v] = 1;
        }
    }

    for ( int i = 0 ; i < n ; i ++){
        for ( int j = 0 ; j < n ; j ++){
            if ( j ) cout << " ";
            cout << M[i][j];
        }
        cout << endl;
    }
}

3.图的深度优先搜索：
a.定义：在图的搜索算法中，深度优先搜索采取的思路是尽可能地访问相邻顶点。设仍存在未搜索邻接边的顶点中最后一个被发现的顶点为v，那么深度优先搜索就是对此顶点的的邻接递归地进行搜索。当v的边全部搜索完毕后，程序沿发现v时所经过的边回溯，继续搜索前一顶点。搜索一直持续到发现当前起点可到达的所有顶点为止。如果仍有顶点未被发现，则选择其中编号最小的一个作为新起来继续探索。
深度优先搜索中需要记录：
d[v]:记录第一次访问v的时刻
f[v]:记录调查完v的邻接表的时刻
b.过程：
1)将最初访问的顶点压入栈
2)如果栈中仍有顶点，则循环进行下述操作：先访问栈顶部的顶点u,然后从当前的顶点u移动至顶点v时，将v入栈。如果当前顶点u不存在未访问的顶点，则将u从栈中删除
c.代码： 
#include "iostream"
#include "stack"
using namespace std;

static const int N = 100;
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n,M[N][N];
int color[N],d[N],f[N],tt;
int nt[N];

int next(int u){
    for ( int v = nt[u]; v < n ; v++){
        nt[u] = v + 1;
        if ( M[u][v] ) return v;
    }
    return -1;
}

void dfs_visit(int r){
    for ( int i = 0 ; i < n ; i ++) nt[i] = 0 ;

    stack<int> S;
    S.push(r);
    color[r] = GRAY;
    d[r] = ++tt;

    while( !S.empty() ){
        int u = S.top();
        int v = next(u);
        if ( v != -1){
            if ( color[v] == WHITE) {
                color[v] = GRAY;
                d[v] = ++tt;
                S.push(v);
            }
        } else {
            S.pop();
            color[u] = BLACK;
            f[u] = ++tt;
        }
    }
}

void dfs(){
    for ( int i = 0 ; i < n ; i ++){
        color[i] = WHITE;
        nt[i] = 0;
    }
    tt = 0 ;

    for ( int u = 0 ; u < n ; u ++){
        if ( color[u] == WHITE ) dfs_visit(u);
    }
    for ( int i = 0 ; i < n ; i ++){
        cout << i + 1 << " " << d[i] << " " << f[i] << endl;
    }
}

int main(){
    int u,k,v;

    cin >> n;
    for ( int i = 0 ; i < n ; i ++){
        for ( int j = 0 ; j < n ; j ++) M[i][j] = 0;
    }

    for ( int i = 0 ; i < n ; i ++){
        cin >> u >> k;
        u--;
        for ( int j = 0 ; j < k ; j ++){
            cin >> v;
            v --;
            M[u][v] = 1;
        }
    }

    dfs();

    return 0;
}

4.图的广度优先搜索：
a.定义：在广度优先搜索中，要想发现与起点s距离为k+1的顶点，首先要发现所有距离为k的顶点，因此可以求出起点到各顶点的最短矩离
b.要点：使用邻接矩阵实现的广度优先搜索中，由于要调查每个顶点是否与其他点相邻，所以不适用于规模较大的图

c.代码：

//
// Created by 叶子 on 2018/2/5.
// 广度优先搜索
//

#include "iostream"
#include "queue"

using namespace std;
static const int N = 100;
static const int INFTY = ( 1 << 2);

int n,M[N][N];
int d[N];

void bfs(int s ){
    queue<int> q;
    q.push(s);
    for ( int i = 0 ; i < n ; i ++) d[i] = INFTY;
    d[s] = 0 ;
    int u ;
    while ( !q.empty()){
        u = q.front();
        q.pop();
        for ( int v = 0 ; v < n ; v ++){
            if ( M[u][v] == 0 ) continue;
            if ( d[v] != INFTY ) continue;
            d[v] = d[u] + 1;
            q.push(v);
        }
    }
    for ( int i = 0 ; i < n ; i ++){
        cout << i +1 << " " << ( d[i] == INFTY ? ( -1) : d[i] ) << endl;
    }
}

int main(){
    int u,k,v;

    cin >> n;
    for ( int i = 0 ; i < n ; i ++){
        for ( int j = 0 ; j < n ; j ++) M[i][j] = 0;
    }

    for ( int i = 0 ; i < n ; i ++){
        cin >> u >> k;
        u --;
        for ( int j = 0 ; j < k ; j ++){
            cin >> v;
            v--;
            M[u][v] = 1;
        }
    }

    bfs(0);

    return 0;
}

5.连通分量：
a.题目：输入SNS的朋友关系，判断从指定人物出发能否通过双向朋友链抵达指定人物
b.要点：使用邻接且来表示图，其优点是只需与边数成正比的内存空间，其缺点难以有效的删除边
c.代码： 
//
// Created by 叶子 on 2018/2/5.
// 连通分量
//

#include "iostream"
#include "vector"
#include "stack"
using namespace std;
static const int MAX = 100000;
static const int NIL = -1;

int n ;
vector<int> G[MAX];
int color[MAX];

void dfs(int r,int c){
    stack<int> S;
    S.push(r);
    color[r] = c;
    while ( !S.empty()){
        int u = S.top();
        S.pop();
        for ( int i = 0 ; i < G[u].size() ; i ++){
            int v = G[u][i];
            if ( color[v] == NIL){
                color[v] = c;
                S.push(v);
            }
        }
    }
}

void assignColor(){
    int id = 1;
    for ( int i = 0 ; i < n ; i ++) color[i] = NIL;
    for ( int u = 0 ; u < n ; u ++){
        if ( color[u] == NIL) dfs(u,id++);
    }
}

int main(){
    int s,t,m,q;

    cin >> n >> m;

    for ( int i = 0 ; i < m ; i ++){
        cin >> s >> t;
        G[s].push_back(t);
        G[t].push_back(s);
    }

    assignColor();

    cin >> q;

    for ( int i = 0 ; i < q ; i ++){
        cin >> s >> t;
        if ( color[s] == color[t] ){
            cout << "yes" << endl;
        }else{
            cout << "no" << endl;
        }
    }

    return 0;
}




标签：

相关文章