文章目录

数字节点的存储邻接矩阵邻接链表邻接链表的动态实现邻接链表的静态实现(前向星) 邻接数组 节点值为非数字的存储

数字节点的存储

假定我们的图的节点是给定的数字$1、2、\dots \dots 、n$,节点与节点之间的数字为边权，当然边权可以不止有一个。 下面就来解决图的存储问题。 我们约定顶点的数目为$n$,边的数目为$m$。 如下图，$n=5,m=6$。

邻接矩阵

$$graph[i][j]\{\begin{array}{l}0,i=j\\ w(i,j),(i,j)\in E\\ +\infty ,(i,j)\notin E\end{array}$$

如上图： $$\left[\begin{array}{ccccc}0& 2& inf& inf& inf\\ inf& 0& 5& inf& 3\\ inf& inf& 0& inf& 4\\ inf& inf& inf& 0& inf\\ 3& inf& inf& 1& 0\end{array}\right]$$

const int SIZE = 10000; const int INF = 0x3f3f3f3f; int n,m; int graph[SIZE][SIZE]; memset(graph,INF,sizeof(graph)); cin>>n>>m; // for(int i=1;i<=n;i++){ // graph[i][i] = 0; // } for(int i=0;i<m;i++){ int from,to,weight; cin>>from>>to>>weight; graph[from][to] = weight; } //依次访问n个节点的所有出边 for(int x=1;x<=n;x++){ for(int y=1;y<=n;y++){ if(graph[x][y]!=INF){ //…………………… } } }

空间复杂度:$O(n^2)$ 优点：实现简单 缺点：耗空间、遍历耗时长。

邻接链表

邻接链表的存储思路： 对于每一个节点，存储以它为起点的所有的边，也就是所有的出边。

如上图： $1:2$ $2:3、5$ $3:4$ $4:$ $5:1、4$

很明显需要的存储空间变小了。 空间复杂度:$O(n+m)$ 适合一般的图的存储，尤其是稀疏图的存储。

下面给出两种实现方式，一种是动态分配内存，指针实现； 一种是用数组加下标来模拟指针，静态实现。

邻接链表的动态实现

底层的数据结构为数组加链表，也是哈希表的内部结构。

//图的存储 struct Edge{ int to,val; Edge* next = nullptr; Edge(int to,int val):to(to),val(val){} }; vector<Edge*> graph; //建图 int n,m; scanf("%d%d",&n,&m); graph.resize(n+1); for(int i=0;i<m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); Edge* head = new Edge(y,z); head->next = graph[x]; graph[x] = head; } //遍历 for(int x=1;x<=n;x++){ cout<<x<<" : "; for(Edge* p=graph[x];p;p=p->next){ cout<<p->to<<" "; } cout<<endl; }

这里运用了一个小技巧，就是每次新加一条边都是加到头部，而后将新的头部和原来的连接起来，这样就避免了每次都要通过遍历到链表的尾部。这个小技巧在下面也会使用到。

邻接链表的静态实现(前向星)

解释一下各个变量的含义，以及注意点。tot变量模拟指针，自然增长；head[]是头表，每次访问一个节点从它开始；Next[]模拟指针的移动，记录的是一条边存储的下一条边的编号。weight[]记录边权。

注意,to[]、weight[]、Next[]的脚标都是边的编号，其中next[]、head[]存储的也是边的编号。 如果边的编号为0,表示指空。（如果确实有0，那可以初始化为-1，用-1之中）。

const int N = 100010, M = 1000010; int n,m,tot,head[N],to[M],weight[M],Next[M]; void add(int x,int y,int z){ to[++tot] = y; weight[tot] = z; Next[tot] = head[x]; head[x] = tot; //从头部插入 } //访问节点x的所有出边 void visit(int x){ for(int i = head[x];i;i=Next[i]){ int y = to[i]; int z = weight[i]; } }

此实现方法比较复杂，我并不常用。

邻接数组

又不想动态分配内存，又不想使用前向星，那么vector<int>就是最佳选择了。 其中edges<Edge>存储的真实的边的信息。 而vector<int> graph[]存储是每个节点的出边的标号。 当然也可以暴力一点直接存储边,用vector<Edge> graph[]。

struct Edge{ int from,to,weight; Edge(int from,int to,int weight):from(from),to(to),weight(weight){} }; const int N = 100010; vector<int> graph[N]; vector<Edge> edges; void addEdge(int x,int y,int z){ edges.push_back(Edge(x,y,z)); graph[x].push_back(edges.size()-1); } void visit(int x){ for(int idx:graph[x]){ int y = edges[idx].to; int z = edges[idx].weight; } } 简易版本 如果并不想存储边的信息，仅仅想记录点点之间的联系关系，可以直接s使用vector<int> graph[]来记录一下每个点的出点，也就是每个点的出边对应的点。

节点值为非数字的存储

在力扣上做图论题的时候，经常遇到需要将字符串作为节点的情况。 当然我们可以将字符串映射为数字，然后就像上面那样去处理就可以了。 但是这样做并不清晰，而且有时候还有点麻烦。 换一种思路，其实之前用节点的值从数字换成字符串之后，无非就是不能直接把数字作为数组的脚标了，其余的没啥区别，这个时候我们可以借助STL的map的记录非数字的映射关系。 比如字符串之间邻接矩阵表示为，map<string,map<stirng,int>>, 当然也可以使用unordered_map<string,unordered_map<string,int>>。 同样vector<Edge> graph[]就对应着map<string,vector<Edge>>。 类似的就不赘述了