标签：存储 int head next vector maxn 指针

图的存储  

1. 邻接矩阵

　　它是利用矩阵的二维结构，使其中的一维代表其中一个端点，另一维代表另一个端点。

 

 

scanf("%d",&m);
memset(G,0,sizeof(G));
for(int i=1;i<=m;++i)
{
    scanf("%d%d",&x,&y);
    G[x][y]=G[y][x]=1;//无向图
}

 

　　缺点：空间占用太大，空间利用率不高，容易内存爆    

2. 权矩阵

　　若边有权，则用A(i,j)存储边的权；若没有边，则默认为无穷大。  

3. 邻接表

　　对于图中的每个顶点，邻接表把与其相连的所有边依次连成一条链。并建立一个新的元素在顶点与这条链的开端建立一个联系。 　　在二维数组vector中，两个维度可以满足上面的需求； 　　链式前向星需要一个结构体，用来赋值同时规定好next指针来连接好一条链表，同时还需要一个head数组来代表那条链表的开端，即头指针。  

 

　　vector：G[ u ][ v ]第一个维度表示某个顶点可以连接到的所有其他点（代表边），第二个维度枚举所有点

vector<int> G[maxn];
for (int i = 1; i <= m; i ++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }

 

  　　链式前向星

int head[maxn];//每个顶点(从i出发)的第一条边(相当于头指针,指向首元结点)
struct px
{
    int next;//指针
    int to;
    int w;
}T[maxm*3];//注意T存的是所有边数(边的连接信息,终点,权值,下条边都在这里),无向图是2倍

void Add(int x,int y,int z)//插在前面
{
    T[++cnt].next=head[x];//相当于链表前插法,新结点指向了头指针指的结点
    T[cnt].to=y;
    T[cnt].w=z;
    head[x]=cnt;//前插完成,头指针已经指向了新结点
}

for(int i=head[x];i;i=T[i].next)//遍历(与某个点x连接的所有边和点)
{
    cout<<x<<' '<<T[i].to<<endl;//输出这条边的两个端点(x一直是一端,存的就是所有与它连接的点)
    cout<<T[i].w<<endl;//输出这条边的权值

}

 

 

例题引入： 图的遍历

题意：给出 N 个点，M 条边的有向图，对于每个点 v，求 A(v) 表示从点 v  出发，能到达的编号最大的点。

1. vector存图

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 20;
vector<int> G[maxn];
int A[maxn];
int n, m;

void dfs(int x, int d) {
    if (A[x]) return ;
    A[x] = d;
    for (int i = 0; i < G[x].size(); i ++) {
        dfs(G[x][i], d);
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        int u, v;
        cin >> u >> v;// reverse
        G[v].push_back(u);
    }
    for (int i = n; i >= 1; i --) {
        dfs(i, i);
    }
    for (int i = 1; i <= n; i ++) {
        cout << A[i] << " ";
    }

    return 0;
}

 

　　2.链式前向星  

标签：存储,int,head,next,vector,maxn,指针
From： https://www.cnblogs.com/coding-inspirations/p/16606920.html