图论·图的存储

图论的存储

• 邻接表
• 邻接矩阵(一般不用)

邻接表

结构体数组实现

• 缺点：如果使用结构体的话，node结构体初始化很慢。

// common onevector<list<int>>g;// another typetypedefstructnode{intval;intdist;// 如果需要节点到某点的距离的话}vector<list<node>>g;

• 插入操作

q.push_back(item)

链表前向星

• 邻接表定义：
• h代表链表头指针，指向v,nxt数组中的每一个节点
• v代表某一个边终点节点的具体值，nxt代表指向的边。注意这两个数组其实都是代表边，可能会出现1->3,2->3，3号节点对应v和nxt中不同的位置的情况！
• v和nxt的大小等于边数！
• len代表总共有多少边。

inth[100009],v[100009],nxt[100009],len=0;

• 插入操作

voidinsert(intx,inty){len++;v[len]=y;nxt[len]=h[x];h[x]=len;d[y]++;}

• 容易出错的操作：搜索时我们假定得到的是节点编号，但是我们nxt和h指向的是该节点的实际存储位置。

for(inti=h[cur];i!=-1;i=nxt[i]){intnode=v[i];d[node]--;if(!d[node]){q.push(node);}}