图的存储与遍历

图

图的存储我们可以想象成哈希中的拉链法，也是同样的道理，在每一个点上延伸出一条链表，从该点出发可到达并且距离为1的点

初始化临界表

h[N]用来对每一个点的头结点进行存储

ne[N]用来指向链表中的下一个结点

e[N]用来存值

每一结点在没有指向的时候，我们将该结点的头结点初始化为-1

存储模版

void add(int a,int b) {
    e[idx] = b; //e[b的编号] = b的值(b在图中的位置)
    ne[idx] = h[a]; //将b这个结点连接到a这条链上
    h[a] = idx++; //将a链表的头结点设置为新插入的b的idx
}

树和图的深度优先遍历

void dfs(int u) {
    st[u] = 1; //代表u这个点已经遍历过了
    for(int i = h[u];i != -1;i = ne[i]) { 
      //遍历u链表的同时，遍历链表上元素下的元素
        int j = e[i];
        if(!st[j]) dfs(j);
    }
}

树和图宽度优先遍历

void bfs() {
    q.push(1);
    memset(d,-1,sizeof(d));
    d[1] = 0;
    while(q.size()) {
        int fr = q.front();
        q.pop();
        for(int i = h[fr];i != -1;i = ne[i]) {
            int j = e[i];
            if(d[j] == -1) {
                d[j] = d[fr] + 1;
                q.push(j);
            }
        }
    }


}

图存储多形态模版

第一种：邻接表

邻接表也分为两种形式

• 数组
• 集合

数组形式

const int N = 10010,M = N * 2;
int ne[M],e[M],h[N],w[M],idx;
void add(int a,int b,int c) {
    w[idx] = c;
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
int main(){
  	memset(h,-1,sizeof(h));
    int n,m;
    cin >> n >> m;
    while(m--) {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c),add(b,a,c);
    }
    return 0;
}

集合形式

const int N = 10010;
struct edge{
    int to,w;
};
vector<edge> v[N];
int main(){
    int n,m;
    cin >> n >> m;
    while(m--) {
        int a,b,c;
        cin >> a >> b >> c;
        v[a].push_back((edge){b,c});
        v[b].push_back((edge){a,c});
    }
    return 0;
}

第二种：链式前向星

const int N = 210;
struct edge{
    int to,ne,w;
}e[N];

int h[N],tot;
void add(int a,int b,int c) {
    e[++tot].to = b;
    e[tot].w = c;
    e[tot].ne = h[a];
    h[a] = tot;
}