图
如何理解图？
前面我们学习了线性表，链表，树等基础数据结构，图这种数据结构就是它们的综合利用。我们都知道，图有边和顶点组成，图的知识点比较多，我这里只是简单从数据结构简要分析。
1.图的种类
- 根据方向:无向图和有向图
- 根据权值：无权图和有权图
2.图的术语
-
度：度的概念是针对图的顶点而言的，在无向图中，度表示某个顶点周围有几个顶点与其相连接，在有向图中，分为入度和出度的概念，入度表示该顶点周围多少个点指向自己，出度表示该顶点指向几个点
-
带权图：就是图中边上面的数据，描述边的附加信息。
-
联系qq软件的例子，入度就是全服有多少人加你好友，出度就是你加了多少人好友，当然这个是矛盾的，qq软件设计的图是双向的，你加了它必然它也加了你，真正体现出度和入度的经典软件就是微博，你关注别人，别人不一定关注你，哈哈，是不是很sao.带权图就是qq软件里面的亲密度，每两个人之间的权值不一样，亲密度就不同。
3.图的存储
- 邻接矩阵
- 邻接表
邻接矩阵
我来演示邻接矩阵是如何存储无向图，有向图，无向带权图，有项带权图这四类图的。邻接矩阵本质就是二维数组
无向图的存储
1.准备一个无向图
2.用数组把顶点都保存起来,如下所示。
| A | B | C | D |
|---|---|---|---|
| 0 | 1 | 2 | 3 |
3.根据图的连接，写出邻接矩阵,因为是无向图，如果点A到点B有连接，0在数组就是A，1在数组就是B，因此在邻接矩阵的(0,1)坐标和(1,0)坐标标记1，都标记1因为无向图是双向的。
graph2.jpg
有向图的存储
1.准备一个有向图
graph5.jpg
2.用数组把顶点都保存起来,如下所示。
| A | B | C | D |
|---|---|---|---|
| 0 | 1 | 2 | 3 |
3.根据图的连接，写出邻接矩阵,因为是有向图，如果点A到点B有连接，0在数组就是A，1在数组就是B，因此在邻接矩阵的(0,1)标记1，此时因为是有向图，单向的指向只能是(0,1)坐标是1。
graph6.jpg
无向带权图的存储
1.准备一个无向带权图
graph7.jpg
2.用数组把顶点都保存起来,如下所示。
| A | B | C | D |
|---|---|---|---|
| 0 | 1 | 2 | 3 |
3.根据图的连接，写出邻接矩阵,因为是无向向图，如果点A到点B有连接，0在数组就是A，1在数组就是B，就在邻接矩阵的(0,1)和(1,0)坐标标记AB边的权值。如下图所示。
有
有向带权图的存储
1.准备一个有向带权图
graph9.jpg
2.用数组把顶点都保存起来,如下所示。
| A | B | C | D |
|---|---|---|---|
| 0 | 1 | 2 | 3 |
3.根据图的连接，写出邻接矩阵,因为是有向带权图，如果点A到点B有连接，0在数组就是A，1在数组就是B，就在邻接矩阵的(0,1)坐标标记AB边的权值。如下图所示。
graph10.jpg
总结
我们发现，当用邻接矩阵存储无向图图时，矩阵是左对角线对称的，数据只保存一半就行，其余一半和上半部分是一样的，也就是说，我们白白浪费空间去存储。当去存储有向图时，当边十分少时，空间也大量浪费掉。但是这种存储方式优点也十分明显，我们要查询两个点的信息和关联时，十分快速，直接看他们的数字关系就ok了。
无向图代码
void creat_Graph_Matrix(struct MGraph *g)
{
int x1, x2;
printf("请输入图的顶点个数和边的个数: ");
scanf_s("%d%d", &g->numVretexes, &g->numEdges);
g->vetex = (char*)malloc(sizeof(char)*g->numVretexes);
g->data = (int**)malloc(sizeof(int*)*g->numVretexes);
for (int i = 0; i < g->numVretexes; i++)
{
g->data[i] = (int*)malloc(sizeof(int)*g->numVretexes);
}
for (int i = 0; i < g->numVretexes; i++)
{
for (int j = 0; j < g->numVretexes; j++)
{
g->data[i][j] = 0;//初始化为无连接
}
}
for (int i = 0; i < g->numEdges; i++)
{
getchar();//吸收空格
printf("请输入第%d个顶点信息: ", i + 1);
scanf_s("%c", &g->vetex[i]);
}
for (int i = 0; i < g->numEdges; i++)
{
printf("请输入第%d条边两个端点的下标 ",i+1);
scanf_s("%d%d", &x1, &x2);
g->data[x1][x2] = 1;//代表两点相连接构成边
g->data[x2][x1] = 1;
}
}
邻接表
讲完邻接矩阵，我们在来看看邻接表，邻接表是不同于邻接矩阵的另一种存储结构，它是邻接表和数组的合体。下面我将演示邻接表如何存储无向图
无向图的存储
1.准备一个无向图
graph1.jpg
2.用数组把顶点都保存起来,如下所示。
| A | B | C | D |
|---|---|---|---|
| 0 | 1 | 2 | 3 |
3.根据图的边连接，生成邻接表,边表的头节点保存每个节点的信息，后面的节点链接的是它们的相连接点的下标，例如点A，它链接了B和C，因此边表A的后面节点分别是1和2对应B和C
graph11.jpg
有向图就是只存储一边就行了。至于带权的无向图和有向图，只是在每个节点域后面多添加一个权值域。
总结
邻接表弥补了邻接矩阵造成空间浪费的情况，我们有多少边，就连接多少次，但是我们都知道数据结构的一大特性，就是时间和空间不可兼得，要求空间小，时间复杂度就会高，当我们需要知道某个点的连接信息时，需要逐个遍历才可以。
邻接表代码
void creat_Graph_List(struct LGraph_List *g)
{
int x1, x2;
printf("请输入图的顶点个数和边个数 ");
scanf_s("%d%d", &g->numVretexes, &g->numEdges);
g->list = (struct LGraph*)malloc(sizeof(struct LGraph)*g->numVretexes);
printf("请输入图的顶点信息 ");
for (int i = 0; i < g->numVretexes; i++)
{
getchar();
scanf_s("%c", &g->list[i].data);
printf("%c", g->list[i].data);
g->list[i].head = NULL;
}
printf("请输入图的边信息\n ");
for (int i = 0; i < g->numEdges; i++)
{
printf("请输入第%d条边的端点下标: ", i + 1);
scanf_s("%d%d", &x1, &x2);
struct Node *s1, *s2;
s1 = (struct Node*)malloc(sizeof(struct Node));
s2 = (struct Node*)malloc(sizeof(struct Node));
s1->index = x1;
s2->index = x2;
s1->next = g->list[x2].head;
g->list[x2].head = s1;
s2->next = g->list[x1].head;
g->list[x1].head = s2;
}
}
获取完整代码
我分别用C，C++，JAVA三种主流语言编写了完整代码，请大家指导批正，一起学习。
网友评论