邻接矩阵存储法
回顾：图G = <V,E>
邻接矩阵存储法的主要思想如下
1、用一个数组存储所有顶点，代表集合V中的元素
2、用一个二维数组存边，代表集合E中的元素
无向图的邻接矩阵存储
我们通过具体的例子来讲解，以下图为例
1、边使用矩阵来构建模型，这使得每一个顶点和其它顶点之间都有边的有无 的 表示的机会。若有边，则他们交点 为1 ，否则为0。
2、无向图的边的矩阵一定是一个对称矩阵，因为无向图只关心边是否存在，而不关心方向，V0和V1有边，那么V1和V0也有边。
3、因为这里不研究有圈图，所以主对角线都是0
先牛刀小试 一下，构建数据类型，写出API。 :)
代码都很好理解，唯一 一个技巧就是create函数中的二重for循环，利用了选择排序中的思想，避免了边信息的重复填充，也就是例如，输入V0和V1边的关系后，就不必输入V1和V0的关系了。
在上一篇文章中提到：
顶点数为n的图，最多有
条边，这里的二重for循环的时间复杂度恰好也是O() = O(n2)
这个技巧后面都会用到。
for (int j = 0; j <MAX_VERTEX; ++j) //填充边关系
{
for (int i = j+1; i < MAX_VERTEX; ++i)
{
printf("若元素%c和%c有边，则输入1，否则输入0\t",pGraph->vertexArr[j],pGraph->vertexArr[i]);
scanf("%d",&( pGraph->edgeArr[j][i]));
pGraph->edgeArr[i][j] = pGraph->edgeArr[j][i]; //对称
}
}
代码：
#include<stdio.h>View Code
#define MAX_VERTEX 4
typedef char DataType; //图中元素的目标数据类型
typedef struct
{
DataType vertexArr[MAX_VERTEX]; //顶点元素数组
int edgeArr[MAX_VERTEX][MAX_VERTEX]; //边矩阵二维数组
}ArrayGraph;
void ArrayGraph_init(ArrayGraph *pGraph);
void ArrayGraph_create(ArrayGraph *pGraph);
void ArrayGraph_show(ArrayGraph *pGraph);
int main()
{
ArrayGraph g;
ArrayGraph_init(&g); //初始化图
ArrayGraph_create(&g); //创建图
ArrayGraph_show(&g); //打印图
return 0;
}
//初始化为一个无圈图 ，也就是边矩阵中，主对角线元素都是0
void ArrayGraph_init(ArrayGraph *pGraph)
{
for (int i = 0; i < MAX_VERTEX; i++)
pGraph->edgeArr[i][i] = 0;
}
void ArrayGraph_create(ArrayGraph *pGraph)
{
for (int i = 0; i < MAX_VERTEX; ++i) //填充顶点数组，也就是输入顶点元素
{
printf("输入第%d个顶点值\n",i+1);
scanf(" %c",&(pGraph->vertexArr[i]));
}
for (int j = 0; j <MAX_VERTEX; ++j) //填充边关系
{
for (int i = j+1; i < MAX_VERTEX; ++i)
{
printf("若元素%c和%c有边，则输入1，否则输入0\t",pGraph->vertexArr[j],pGraph->vertexArr[i]);
scanf("%d",&( pGraph->edgeArr[j][i]));
pGraph->edgeArr[i][j] = pGraph->edgeArr[j][i]; //对称
}
}
}
void ArrayGraph_show(ArrayGraph *pGraph)
{
printf("\n\n顶点元素如下\n");
for (int i = 0; i < MAX_VERTEX; ++i)
{
printf("%-5c", pGraph->vertexArr[i]);
}
printf("\n\n");
puts("边矩阵如下\n\n");
printf("%-2c",' ');
for(int i=0;i<MAX_VERTEX;++i)
printf("%-5c",pGraph->vertexArr[i]);
putchar('\n');
for (int j = 0; j <MAX_VERTEX; ++j)
{
printf("%-2c",pGraph->vertexArr[j]);
for (int i = 0; i < MAX_VERTEX; ++i)
{
printf("%-5d",pGraph->edgeArr[i][j]);
}
putchar('\n');
}
printf("\n\n");
}
有向图的邻接矩阵存储
使用邻接矩阵呢存储时，有向图和无向图的区别在与 边和弧矩阵的差别。因为弧是有方向的，所以我们 以对角线为界，将矩阵划分为2个区域：
左下区域表示出弧标记区域，坐上区域代表入弧标记区域（当然也可以交换，看个人习惯）
如 若代表弧的矩阵为arcArr
arcArr[V2][V3] 为1，且在出弧标记区域，则说明 V3<------V2
arcArr[V3][V2] 为0，且在入弧标记区域，则说明 V2---\--->V3
代码：
#include<stdio.h>View Code
#define MAX_VERTEX 4
typedef char DataType; //图中元素的目标数据类型
typedef struct
{
DataType vertexArr[MAX_VERTEX]; //顶点元素数组
int arcArr[MAX_VERTEX][MAX_VERTEX]; //弧矩阵二维数组
}ArrayGraph;
void ArrayGraph_init(ArrayGraph *pGraph);
void ArrayGraph_create(ArrayGraph *pGraph);
void ArrayGraph_show(ArrayGraph *pGraph);
int main()
{
ArrayGraph g;
ArrayGraph_init(&g);
ArrayGraph_create(&g);
ArrayGraph_show(&g);
return 0;
}
//初始化为一个无圈图 ，也就是弧矩阵中，主对角线元素都是0
void ArrayGraph_init(ArrayGraph *pGraph)
{
for (int i = 0; i < MAX_VERTEX; i++)
pGraph->arcArr[i][i] = 0;
}
void ArrayGraph_create(ArrayGraph *pGraph)
{
for (int i = 0; i < MAX_VERTEX; ++i) //填充顶点数组
{
printf("输入第%d个顶点值\n",i+1);
scanf(" %c",&(pGraph->vertexArr[i]));
}
for (int j = 0; j <MAX_VERTEX; ++j) //填充边关系
{
for (int i = j+1; i < MAX_VERTEX; ++i)
{
printf("若元素%c有指向%c的弧，则输入1，否则输入0\t",pGraph->vertexArr[i],pGraph->vertexArr[j]);
scanf("%d",&( pGraph->arcArr[j][i]));
printf("若元素%c有指向%c的弧，则输入1，否则输入0\t",pGraph->vertexArr[j],pGraph->vertexArr[i]);
scanf("%d",&( pGraph->arcArr[i][j]));
}
}
}
void ArrayGraph_show(ArrayGraph *pGraph)
{
printf("\n\n顶点元素如下\n");
for (int i = 0; i < MAX_VERTEX; ++i)
{
printf("%-5c", pGraph->vertexArr[i]);
}
printf("\n\n");
puts("弧矩阵如下\n\n");
printf("%-2c",' ');
for(int i=0;i<MAX_VERTEX;++i)
printf("%-5c",pGraph->vertexArr[i]);
putchar('\n');
for (int j = 0; j <MAX_VERTEX; ++j)
{
printf("%-2c",pGraph->vertexArr[j]);
for (int i = 0; i < MAX_VERTEX; ++i)
{
printf("%-5d",pGraph->arcArr[i][j]);
}
putchar('\n');
}
putchar('\n');
}
无向网的邻接矩阵存储
无向网的边是有权值的，这个值可以是任何一个合法的值，什么样的值是合法的呢？这需要根据图的具体用途来定。所以，我们不能用简单的0,1来代表边。
如果2个顶点无关联，他们也不能用0表示，因为0也可能是一个合法的wieght值。可有类比一下：如何地球上2个地方之间不可互通，那么他们之间的车程费是不是无穷大呢？
所以，我们来要根据图权值类型定义一个相应类型的最大值，来代表2个顶点之间不关联。
同样用一个例子。
V0 V1之间的权值为12
V0 V2之间的权值为1
V0 V3之间的权值为5
V2 V3之间的权值为7
代码：
#include<stdio.h>View Code
#define MAX_VERTEX 4
#define INFINITY 65535
typedef char DataType; //存储的元素类型
typedef int WeightType; //权值的类型
typedef struct
{
DataType vertexArr[MAX_VERTEX]; //存储顶点的数组
WeightType edgeArr[MAX_VERTEX][MAX_VERTEX]; //存储边的二维数组
}UArrayNet; //数据结构类型：无向网
void UArrayNet_init(UArrayNet*pGraph);
void UArrayNet_create(UArrayNet*pGraph);
void UArrayNet_show(UArrayNet *pGraph);
int main()
{
UArrayNet net;
UArrayNet_init(&net);
UArrayNet_create(&net);
UArrayNet_show(&net);
return 0;
}
void UArrayNet_init(UArrayNet*pGraph)
{
for (int i = 0; i < MAX_VERTEX; ++i)
{
pGraph->edgeArr[i][i] = INFINITY;
}
}
void UArrayNet_create(UArrayNet*pGraph)
{
for (int i = 0; i < MAX_VERTEX; ++i) //填充顶点数组
{
printf("输入第%d个顶点值\n", i + 1);
scanf(" %c", &(pGraph->vertexArr[i]));
}
for (int j = 0; j <MAX_VERTEX; ++j) //填充边关系
{
for (int i = j + 1; i < MAX_VERTEX; ++i)
{
printf("若元素%c和%c有边，则输入权值，否则输入无效值%d\t", pGraph->vertexArr[j], pGraph->vertexArr[i], INFINITY);
scanf("%d", &(pGraph->edgeArr[j][i]));
pGraph->edgeArr[i][j] = pGraph->edgeArr[j][i]; //对称
}
}
}
void UArrayNet_show(UArrayNet *pGraph)
{
printf("\n\n顶点元素如下\n");
for (int i = 0; i < MAX_VERTEX; ++i)
{
printf("%-5c", pGraph->vertexArr[i]);
}
printf("\n\n");
puts("边矩阵如下");
printf("%-2c", ' ');
for (int i = 0; i<MAX_VERTEX; ++i)
printf("%-5c", pGraph->vertexArr[i]);
putchar('\n');
for (int j = 0; j <MAX_VERTEX; ++j)
{
printf("%-2c", pGraph->vertexArr[j]);
for (int i = 0; i < MAX_VERTEX; ++i)
{
if(pGraph->edgeArr[i][j]==INFINITY)
{
printf("%-5c", '#');
}
else
printf("%-5d", pGraph->edgeArr[i][j]);
}
putchar('\n');
}
}
有向网的邻接矩阵存储
有向网和有向图的原理是一样，这里不再扩充。
邻接表储存实现
邻接矩阵存储很好理解，但是，有时候太浪费空间了，特别是对于顶点数多，但是关联关系少的图。
举个极端的栗子。
下图中，5个顶点都是孤立的，然而为了存储边的信息，要分配一个5X5的矩阵。本来一条边都没有，没必要用存储空间来存储边，但还要分配额外的空间。
无向图与邻接表
用邻接表则可以避免这种浪费。邻接表用动态表结构存储边，更加灵活：有一个边就分配一个空间去存储，没有就不分配。
我们仍然用邻接矩阵中那个图的例子来说明邻接表的构建思想。
邻接表只需要一个数组，但是这个数组有点复杂，需要解剖一下。如下图。
可以发现，用邻接表存储时，图中的每一个节点 不仅要存储本顶点的数据data，好要存储一个表，这个表存储了此顶点的所有临接点的索引。2点确定一线，那么就能存储此节点相关的所有的边了。
代码:
注：代码中，我并没有手动编写链表，而是用了C++标准库中的vector模板，它是一个线性表，具体说是在堆中的动态数组。push_back()就是向表中添加新的元素。
这样做的目的是为了让代码更简洁，思路更清晰。我不想把书抄一遍，这样我写这篇随便也就失去了意义。
而且，书上的很多例子中，将多种数据结构的构建混杂在一起，根本不知道降低耦合度，如果我以前学过了链表，而且也自己实现了，为什么不直接拿来用呢？吐槽完毕。
#include<stdio.h>View Code
#include<vector>
#define MAX_VERTEX 4
using std::vector; //使用C++标准库中的vector来作为list，它实质就是一个顺序表
typedef char DataType;
typedef struct node
{
DataType data; //顶点数据
vector<int> indexList; //存储顶点邻接点索引的 表
}Node;
typedef Node* UListGraph;
/********************************/
void UListGraph_init(UListGraph*pGraph);
void UListGraph_create(UListGraph graph);
void UListGraph_show(UListGraph graph);
void UListGraph_destroy(UListGraph*pGraph);
int main(void)
{
UListGraph g;
UListGraph_init(&g);
UListGraph_create(g);
UListGraph_show(g);
UListGraph_destroy(&g);
return 0;
}
void UListGraph_init(UListGraph*pGraph)
{
(*pGraph) = new Node[MAX_VERTEX];
}
void UListGraph_create(UListGraph graph)
{
for (int i = 0; i < MAX_VERTEX; ++i) //填充顶点数组
{
printf("输入第%d个顶点值\n",i+1);
scanf(" %c", &(graph[i].data));
}
for(int i=0;i<MAX_VERTEX;++i)
for(int j=i+1;j<MAX_VERTEX;++j)
{
printf("如果元素%c和%c之间有边，请输入1，否则输入0",graph[i].data,graph[j].data);
int opt;
scanf("%d",&opt);
if(opt==1)
{
graph[i].indexList.push_back(j);
graph[j].indexList.push_back(i);
}
}
}
void UListGraph_show(UListGraph graph)
{
printf("顶点元素如下:\n\n");
for(int i=0;i<MAX_VERTEX;i++)
{
printf("%c\t",graph[i].data);
}
printf("\n\n");
for(int i=0;i<MAX_VERTEX;i++)
{
printf("元素%c的邻接点 :",graph[i].data);
Node tnode = graph[i];
for(int k=0;k<tnode.indexList.size();++k)
{
printf("%c\t",graph[tnode.indexList[k]].data);
}
putchar('\n');
}
}
void UListGraph_destroy(UListGraph*pGraph)
{
delete (*pGraph);
*pGraph = NULL;
}
无向网的邻接表
无向网的邻接表，因为网是带权值的，所以，还要为边附加权值信息。
确切的说，就是IndexList表 中存储的是一个个的结构体，这个结构体不仅保存邻接点的索引，还用一个成员保存了本顶点和他的邻接点之间边的权值。
typedef struct edge
{
int otherVerTex; //本顶点和索引为otherVertex的顶点形成一条边
WeightType weight; //边的权值
}Edge
//使用方法如下：用V0和V1来举例
// Edge edge = {1 , 12};
// V0.IndexList.push_back(edge );
//
有向图和十字链表
邻接表对于无向图来说很适用，但是对于有向图来说就不适用了，因为邻接表中，每一个节点的IndexList只能存储一种状态的弧，出弧或者入弧（逆邻接表），那怎么将一个顶点的出入弧都存储起来呢？
那就是将邻接表和逆邻接表都用起来，也就是一个节点需要存储：①data，②inArcList，入弧记录表，③outArcList，出弧记录表
可以看出，十字表比邻接表更复杂，因为十字表要存储更多的数据。
代码：
#include<stdio.h>View Code
#include<vector>
using std::vector;
#define MAX_VERTEX 4
typedef char DataType;
typedef struct arc{
int headVertex; //此条弧的头尾结点的index
int tailVertex; //此条弧的头尾结点的index
//WeightType weight; //此弧的附加信息，比如权重，这里是有向图，不是网，所以不需要weight
}Arc;
typedef struct node{
DataType data; //顶点数据域
vector<Arc> outArc; //此顶点的所有 出度 弧 表
vector<Arc> inArc; //此顶点的所有 入度 弧 表
}Node;
typedef Node* Graph;
void Graph_init(Graph* pG);
void Graph_create(Graph g);
void Graph_show(Graph g);
void Graph_destroy(Graph*pg);
int main(void)
{
Graph g;
Graph_init(&g);
Graph_create(g);
Graph_show(g);
return 0;
}
void Graph_init(Graph* pG)
{
(*pG) = new Node[MAX_VERTEX];
if(*pG == NULL)
{
exit(-1);
}
}
void Graph_create(Graph g)
{
int opt;
for (int i = 0; i < MAX_VERTEX; ++i) //填充顶点数组
{
printf("输入第%d个顶点值\n",i+1);
scanf(" %c", &(g[i].data));
}
for(int j=0;j<MAX_VERTEX;++j)
for(int i=j+1;i<MAX_VERTEX;++i)
{
printf("若元素%c有指向%c的弧，则输入1，否则输入0\t",g[j].data,g[i].data);
scanf("%d",&opt);
if(opt==1)
{
Arc* parc = new Arc;
parc->headVertex = i;
parc->tailVertex = j;
g[j].outArc.push_back(*parc);
g[i].inArc.push_back(*parc);
}
printf("若元素%c有指向%c的弧，则输入1，否则输入0\t",g[i].data,g[j].data);
scanf("%d",&opt);
if(opt==1)
{
Arc* parc = new Arc;
parc->headVertex = j;
parc->tailVertex = i;
g[i].outArc.push_back(*parc);
g[j].inArc.push_back(*parc);
}
}
}
void Graph_show(Graph g)
{
for (int j = 0; j <MAX_VERTEX; ++j)
{
printf("顶点数据%c\n",g[j].data);
printf("发射:");
for(int i=0;i<g[j].outArc.size();++i)
{
printf("%c\t",g[g[j].outArc[i].headVertex].data);
}
putchar('\n');
printf("接收:");
for(int i=0;i<g[j].inArc.size();++i)
{
printf("%c\t",g[g[j].inArc[i].tailVertex].data);
}
printf("\n\n");
}
}
void Graph_destroy(Graph*pg)
{
//once you use new or malloc in your C/C++ project,you must remember
//to delete or free the memory you allocated
//I have no time to complete this code
//you can try yourself
//:)
}
邻接多重表
没时间了~以后补！
下一篇：图的遍历