图之基础

图之基础

我们这里不再啰嗦图的基本概念了，关于图的基本概念在很多数据结构的树上都有，我们先讨论图的存储，毕竟是先有了存储了图才能对图做处理呢，当然有些高手也可以忽略图的存储来做，呵呵，图的存储一般有两种方式，即邻接矩阵和邻接表，邻接矩阵实际上就是一个二维数组，使用邻接矩阵很方便且很容易懂，但是在图为稀疏图的时候就有点浪费存储空间了，你想一下嘛，如果有3000个顶点，那么我们就要开辟3000*3000的空间，但是实际上图中很多点没有关联，造成了资源的浪费；邻接表是链表的使用，使用过链表的我们肯定都知道，链表是需要空间的时候才动态分配空间的，对于邻接表可以有效的节约空间，但是使用起来较邻接矩阵麻烦。

1.图的邻接矩阵存储

我们这里直接举一个例子来说明，邻接矩阵的用法，示例如下：

邻接矩阵比较简单不用多说，具体就是相应边得权值赋上就行了，注意初始化邻接矩阵。如果邻接矩阵的值都为非负整数的话，我们可以利用memset()函数来进行初始化，注意memset()函数的应用方法就行了。

2.图的邻接表存储

图的邻接表的用法示例如下：

使用临界表必须先为每个节点建立一个头结点，用于连接与他相连通的节点，如果图为有向图，如V1->V2而V2不到V1，那么在以V1为头结点的链表中出现V2，而以V2为头结点的链表中不出现V1。下图为有向图的临界表示例。

临界表程序：

#include 

#include 

#include 

#define Gnumber 10

typedef struct node

{

int weight;

int dest;

struct node *next;

}GNode;

GNode G[Gnumber];

void GInerst(GNode G[Gnumber], int sour, int dest, int weight)

{

GNode *p = G+sour;

while(p->next)

{

p = p->next;

}

p->next = (GNode*)malloc(sizeof(GNode));

p->next->weight = weight;

p->next->dest = dest;

p->next->next = NULL;//注意这个一定要赋值 

}

int main(int argc, char **argv)

{

memset(G, 0, sizeof(G));

GInerst(G, 0,1,1);

GInerst(G, 0,3,1);

GInerst(G, 1,4,1);

GInerst(G, 2,1,1);

GInerst(G, 3,2,1);

GInerst(G, 4,2,1);

system("pause");

return 0;

}

在编写该程序的时候注意一下几个问题：

（1）初始化链表数组，由于我们再插入新节点的时候采用的是查找next值为NULL来结束查找的，所有我们必须初始化next为NULL；

（2）在编写插入函数的时候我曾犯过下面的错误：下面的程序咋一看还看不出什么问题，但是我们在运行的时候可以发现没有一个值插入到链表中，这是为什么呢？那我们用断点调试可以知道，由于我们定义的节点指针p是在函数内部定义的，为局部变量，在函数作用结束的时候会自动消亡，我们这里在p = (GNode*)malloc(sizeof(GNode));这里为其动态分配了空间，但在在函数结束后，这块区域就成为一个不可再用的区域了，我们这里的想法是把将链表最后一个元素指向next的动态分配，但是实际上我们程序不是这样做的，当我们使用上诉正确的插入函数时候，p指向的是当前最后一个有用节点，然后为p->next 分配空间，这个为什么可以这样做，我的理解是因为p->next 相当于(*p).next，这样就是将该地址里面存储的内容改变了，而不是改变的指针本身，所以可以改变指针指向的值。

void GInerst(GNode G[Gnumber], int sour, int dest, int weight)

{

GNode *p = G+sour;

while(p)

{

p = p->next;

}

p = (GNode*)malloc(sizeof(GNode));

p->weight = weight;

p->dest = dest;

p->next = NULL;//注意这个一定要赋值 

}

（3）新创建了节点，一定要给新建立的节点初始化，因为分配空间后里面的值是不确定的，我们编程的时候必须避免这种情况，而且我们要用到新建节点的next指针为NULL来标志链表结束，所有必须要初始化。

方式1：p->next->next = NULL;//注意这个一定要赋值 

方式2：memset(p->next, 0 , sizeof(GNode));  推荐