1、稀疏矩阵
10年积累的做网站、
成都网站建设经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先
网站制作后付款的网站建设流程，更有
罗定免费网站建设让你可以放心的选择与我们合作。
有一个稀疏因子，这是节省空间的一种存储方式。
2、邻接表
以邻接矩阵存储图结构的话，当实际边数远远小于图的大边数时，将会存储很多0，势必造成存储空间的巨大浪费；这时，就必须将邻接矩阵该用为邻接表；将邻接矩阵各行组织为一个单链表，类哈希的存储结构。
存储结构(控制头)：
int maxVertices; //大顶点数
int curVertices; //当前顶点数
int curEdges; //当前边数
template
class Edge{ //边的存储结构
public:
Edge(int num) : dest(num), link(NULL){}
public:
int dest; //是另一个顶点的下标
Edge *link;
};
template
class Vertex{ //顶点的存储结构
public:
Type data; //存放的顶点
Edge *adj;
};
Vertex *vertexTable; //指向顶点的指针，是申请数组用的
存储模型：
3、核心方法
均由C++实现，无向图的邻接表；
(1)、删除边(是链表的删除操作，相对简单)：
bool removeEdge(const Type &v1, const Type &v2){ //删除边
int i = getVertexIndex(v1);
int j = getVertexIndex(v2);
if(i==-1 || j==-1){ //保证顶点的保存在
return false;
}
//v1-->v2
Edge *p = vertexTable[i].adj;
if(p == NULL){ //判断有没有边
return false;
}
if(p->link == NULL && p->dest == j){ //删除的是第一个边，其后没有边了；
vertexTable[i].adj = NULL;
delete p;
}else if(p->dest == j){ //删除的是第一个边,并且其后还有边
vertexTable[i].adj = p->link;
delete p;
}else{
while(p->link != NULL){
if(p->link->dest == j){
Edge *q = p->link;
p->link = q->link;
delete q;
}
p = p->link;
}
}
//v2-->v1
Edge *s = vertexTable[j].adj;
if(s == NULL){ //判断有没有边
return false;
}
if(s->link == NULL && s->dest == i){ //删除的是第一个边，其后没有边了；
vertexTable[j].adj = NULL;
delete s;
curEdges--;
return false;
}else if(s->dest == i){ //删除的是第一个边,并且其后还有边
vertexTable[j].adj = s->link;
delete s;
curEdges--;
return true;
}else{
while(s->link != NULL){
if(s->link->dest == i){
Edge *q = s->link;
s->link = q->link;
delete q;
curEdges--;
return true;
}
s = s->link;
}
}
return true;
} (2)、删除顶点：
这个算法相对复杂，但是思路比较清晰：
i>、首先找到要删除的顶点，将其后上的边所对应的边和这个边都得删除；
ii>、将最后一个顶点的data和adj都覆盖到这个地方；
iii>、找到其后边上的dest,更改为当下位置的下标；
大致模型如下：
bool removeVertex(const Type &v){ //删除顶点
int i = getVertexIndex(v);
if(i == -1){
return false;
}
Edge *p = vertexTable[i].adj; //先删除边上的dest和此边
while(p != NULL){
vertexTable[i].adj = p->link;
int k = p->dest;
Edge *q = vertexTable[k].adj;
if(q->dest == i){
vertexTable[k].adj = q->link;
delete q;
}else{
while(q->link != NULL && q->link->dest != i){
q = q->link;
}
Edge *t = q->link;
q->link = t->link;
delete t;
}
delete p;
p = vertexTable[i].adj;
curEdges--;
}
curVertices--; //下面实行覆盖，指针和最后的那个顶点的adj相等;
vertexTable[i].data = vertexTable[curVertices].data;
vertexTable[i].adj = vertexTable[curVertices].adj;
vertexTable[curVertices].adj = NULL;
int k = curVertices;
p = vertexTable[i].adj;
while(p != NULL){ //修改其它顶点的dest.
Edge *s = vertexTable[p->dest].adj;
while(s != NULL){
if(s->dest == k){
s->dest = i;
break;
}
s = s->link;
}
p = p->link;
}
return true;
}4、邻接表完整代码、测试代码、测试结果
(1)完整代码(用的是继承，方便写其它的存储结构代码)：
#ifndef _GRAPH_H_
#define _GRAPH_H_
#include
using namespace std;
#define VERTEX_DEFAULT_SIZE 10
template
class Graph{
public:
bool isEmpty()const{
return curVertices == 0;
}
bool isFull()const{
if(curVertices >= maxVertices || curEdges >= curVertices*(curVertices-1)/2)
return true; //图满有2种情况：(1)、当前顶点数超过了大顶点数，存放顶点的空间已满
return false; //(2)、当前顶点数并没有满，但是当前顶点所能达到的边数已满
}
int getCurVertex()const{
return curVertices;
}
int getCurEdge()const{
return curEdges;
}
public:
virtual bool insertVertex(const Type &v) = 0; //插入顶点
virtual bool insertEdge(const Type &v1, const Type &v2) = 0; //插入边
virtual bool removeVertex(const Type &v) = 0; //删除顶点
virtual bool removeEdge(const Type &v1, const Type &v2) = 0; //删除边
virtual int getFirstNeighbor(const Type &v) = 0; //得到第一个相邻顶点
virtual int getNextNeighbor(const Type &v, const Type &w) = 0; //得到下一个相邻顶点
public:
virtual int getVertexIndex(const Type &v)const = 0; //得到顶点下标
virtual void showGraph()const = 0; //显示图
protected:
int maxVertices; //大顶点数
int curVertices; //当前顶点数
int curEdges; //当前边数
};
template
class Edge{ //边的存储结构
public:
Edge(int num) : dest(num), link(NULL){}
public:
int dest;
Edge *link;
};
template
class Vertex{ //顶点的存储结构
public:
Type data;
Edge *adj;
};
template
class GraphLnk : public Graph{
#define maxVertices Graph::maxVertices //因为是模板，所以用父类的数据或方法都得加上作用域限定符
#define curVertices Graph::curVertices
#define curEdges Graph::curEdges
public:
GraphLnk(int sz = VERTEX_DEFAULT_SIZE){
maxVertices = sz > VERTEX_DEFAULT_SIZE ? sz : VERTEX_DEFAULT_SIZE;
vertexTable = new Vertex[maxVertices];
for(int i = 0; i < maxVertices; i++){
vertexTable[i].data = 0;
vertexTable[i].adj = NULL;
}
curVertices = curEdges = 0;
}
public:
bool insertVertex(const Type &v){
if(curVertices >= maxVertices){
return false;
}
vertexTable[curVertices++].data = v;
return true;
}
bool insertEdge(const Type &v1, const Type &v2){
int v = getVertexIndex(v1);
int w = getVertexIndex(v2);
if(v==-1 || w==-1){
return false;
}
Edge *p = vertexTable[v].adj;
while(p != NULL){ //这里主要判断边是否已经存在
if(p->dest == w){ //无向图，判断一边即可;
return false;
}
p = p->link;
}
//v1-->v2 //采用头插
Edge *s = new Edge(w);
s->link = vertexTable[v].adj;
vertexTable[v].adj = s;
//v2-->v1 //采用头插
Edge *q = new Edge(v);
q->link = vertexTable[w].adj;
vertexTable[w].adj = q;
curEdges++;
return true;
}
bool removeVertex(const Type &v){
int i = getVertexIndex(v);
if(i == -1){
return false;
}
Edge *p = vertexTable[i].adj;
while(p != NULL){
vertexTable[i].adj = p->link;
int k = p->dest;
Edge *q = vertexTable[k].adj;
if(q->dest == i){
vertexTable[k].adj = q->link;
delete q;
}else{
while(q->link != NULL && q->link->dest != i){
q = q->link;
}
Edge *t = q->link;
q->link = t->link;
delete t;
}
delete p;
p = vertexTable[i].adj;
curEdges--;
}
curVertices--; //下面实行覆盖
vertexTable[i].data = vertexTable[curVertices].data;
vertexTable[i].adj = vertexTable[curVertices].adj;
vertexTable[curVertices].adj = NULL;
int k = curVertices;
p = vertexTable[i].adj;
while(p != NULL){
Edge *s = vertexTable[p->dest].adj;
while(s != NULL){
if(s->dest == k){
s->dest = i;
break;
}
s = s->link;
}
p = p->link;
}
return true;
}
bool removeEdge(const Type &v1, const Type &v2){
int i = getVertexIndex(v1);
int j = getVertexIndex(v2);
if(i==-1 || j==-1){ //保证顶点的保存在
return false;
}
//v1-->v2
Edge *p = vertexTable[i].adj;
if(p == NULL){ //判断有没有边
return false;
}
if(p->link == NULL && p->dest == j){ //删除的是第一个边，其后没有边了；
vertexTable[i].adj = NULL;
delete p;
}else if(p->dest == j){ //删除的是第一个边,并且其后还有边
vertexTable[i].adj = p->link;
delete p;
}else{
while(p->link != NULL){
if(p->link->dest == j){
Edge *q = p->link;
p->link = q->link;
delete q;
}
p = p->link;
}
}
//v2-->v1
Edge *s = vertexTable[j].adj;
if(s == NULL){ //判断有没有边
return false;
}
if(s->link == NULL && s->dest == i){ //删除的是第一个边，其后没有边了；
vertexTable[j].adj = NULL;
delete s;
curEdges--;
return false;
}else if(s->dest == i){ //删除的是第一个边,并且其后还有边
vertexTable[j].adj = s->link;
delete s;
curEdges--;
return true;
}else{
while(s->link != NULL){
if(s->link->dest == i){
Edge *q = s->link;
s->link = q->link;
delete q;
curEdges--;
return true;
}
s = s->link;
}
}
return true;
}
int getFirstNeighbor(const Type &v){
int i = getVertexIndex(v);
if(i != -1){
Edge *p = vertexTable[i].adj;
if(p != NULL){
return p->dest;
}
}
return -1;
}
int getNextNeighbor(const Type &v, const Type &w){
int i = getVertexIndex(v);
int j = getVertexIndex(w);
if(i==-1 || j==-1){
return -1;
}
Edge *p = vertexTable[i].adj;
while(p != NULL){
if(p->dest == j && p->link != NULL){
return p->link->dest;
}
p = p->link;
}
return -1;
}
public:
int getVertexIndex(const Type &v)const{
for(int i = 0; i < curVertices; i++){
if(vertexTable[i].data == v){
return i;
}
}
return -1;
}
void showGraph()const{
for(int i = 0; i < curVertices; i++){
cout<";
Edge *p = vertexTable[i].adj;
while(p != NULL){
cout<dest<<"-->";
p = p->link;
}
cout<<"Nul. "< *vertexTable; //指向顶点的指针，是申请数组用的
};
#endif
(2)、测试代码：
#include"Graph.h"
int main(void){
GraphLnk gl;
gl.insertVertex('A');
gl.insertVertex('B');
gl.insertVertex('C');
gl.insertVertex('D');
gl.insertEdge('A','B');
gl.insertEdge('A','D');
gl.insertEdge('B','C');
gl.insertEdge('C','D');
gl.showGraph();
cout< (3)、测试结果：
测试的图：
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
网站名称：图的存储之邻接表-创新互联
浏览地址：http://cdxtjz.cn/article/dgdieo.html
