定义：图形结构是一种比树形结构更复杂的非线性结构。在树形结构中，结点间具有分支层次关系，每一层上的结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。而在图形结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的 。
图的结构有无向图，有向图，网图
无向图.png
有向图.png
网图.png
上面三张图分别是不同的结构图像
而实现图的存储结构有两种：
一、邻接矩阵
二、邻接表
下面通过分别通过两种方式去实现图的结构
一、邻接矩阵：
邻接矩阵使用而为数组来描述图的结构，如果是无向图，邻接矩阵与主对角对称。
截屏2020-04-30 上午11.32.06.png
typedef int Status; //函数状态值
typedef char VertexType; //顶点类型
typedef int EdgeType; //边上的权值
typedef struct {
VertexType vexs[MAXVEX];//顶点表
EdgeType arc[MAXVEX][MAXVEX];//w q图中当前的顶点数和边数
int numNodes,numEdges;//图中当钱的顶点数和边数
}MGraph;
void CreateMGraph(MGraph *G){
int i,j,k,w;
printf("输入顶点数和边数:\n");
//1、输入顶点数/边数
scanf("%d,%d",&G->numNodes,&G->numEdges);
printf("顶点数:%d,边数:%d\n",G->numNodes,G->numEdges);
//2、输入顶点信息/顶点表
for (i = 0; i<=G->numNodes; i++) {
scanf("%c",&G->vexs[i]);
}
//3、初始化邻接矩阵
for (i = 0; i<G->numNodes; i++) {
for (j = 0; j<G->numNodes; j++) {
G->arc[i][j] = INFINITYC;
}
}
//4、输入边表信息
for (k = 0; k<G->numEdges; k++) {
printf("输入边（vi,vj）上的下标i，下标j，权值w\n");
scanf("%d,%d,%d",&i,&j,&w);
G->arc[i][j] = w;
//如果无向图，矩阵对称（可以自己对是否为有向图或无向图进行设置判断）
G->arc[j][i] = G->arc[i][j];
}
//5、打印邻接矩阵
for (i = 0; i<G->numNodes; i++) {
printf("\n");
for (j = 0; j<G->numNodes; j++) {
printf("%d ",G->arc[i][j]);
}
}
printf("\n");
}
打印输出
int main(int argc, const char * argv[]) {
@autoreleasepool {
// insert code here...
NSLog(@"邻接矩阵实现图的存储!");
MGraph G;
CreateMGraph(&G);
}
return 0;
}
/*
2020-04-30 11:22:01.704420+0800 图的存储[1483:78312] 邻接矩阵实现图的存储!
输入顶点数和边数:
5,6
顶点数:5,边数:6
abcde
输入边（vi,vj）上的下标i，下标j，权值w
0,4,6
输入边（vi,vj）上的下标i，下标j，权值w
1,0,9
输入边（vi,vj）上的下标i，下标j，权值w
1,2,3
输入边（vi,vj）上的下标i，下标j，权值w
2,0,2
输入边（vi,vj）上的下标i，下标j，权值w
2,3,5
输入边（vi,vj）上的下标i，下标j，权值w
3,4,1
0 9 2 0 6
9 0 3 0 0
2 3 0 5 0
0 0 5 0 1
6 0 0 1 0
*/
二、邻接表
[图片上传失败...(image-bee723-1588218029752)]
看上图中的结构，我们可以创建n个链表，（n为节点的数量），然后将所有链表添加进去数组当中，然后对数组中的每一个链表的下一个值插入该节点连接的节点，进行遍历，将他们连接起来
#define M 100
#define FALSE 0
#define TRUE 1
typedef char Element;
typedef int BOOl;
typedef struct Node{
int adj_vex_index;//弧头的下标，也就是被指向的下标
Element data;//权重值
struct Node *next; //边指针
}EdgeNode;
//顶点节点表
typedef struct VNode{
Element data;//顶点的权值
EdgeNode *firstedge;//顶点的下一个是谁
}VertexNode,Adjlist[M];
//总图的一些信息
typedef struct Graph{
Adjlist adjlist;//顶点表
int arc_num;//边的个数
int node_num;//节点个数
BOOl is_directed;//是不是有向图
}Graph,*GraphLink;
void CreateGraph(GraphLink *g){
int i,j,k;
EdgeNode *p;
//1、顶点，边，是否有向
printf("输入顶点数目,边数和有向:\n");
scanf("%d,%d,%d",&(*g)->node_num,&(*g)->arc_num,&(*g)->is_directed);
//2、顶点表
printf("输入顶点信息:\n");
for (i = 0; i<(*g)->node_num; i++) {
getchar();
scanf("%c",&(*g)->adjlist[i].data);
(*g)->adjlist[i].firstedge = NULL;
}
//3、输入边的信息
printf("输入边的信息:\n");
for (k = 0; k<(*g)->arc_num; k++) {
getchar();
scanf("%d,%d",&i,&j);
//1、新建一个节点
p = (EdgeNode *)malloc(sizeof(EdgeNode));
//2、弧头的下标
p->adj_vex_index = j;
//3、头插法插进去，插的时候要找弧尾，那就是顶点数组的下标i
p->next = (*g)->adjlist[i].firstedge;
//4、将顶点数组[i].firstedge设置为p
(*g)->adjlist[i].firstedge = p;
//j->i
if(!(*g)->is_directed){
//1、新建一个节点
p = (EdgeNode *)malloc(sizeof(EdgeNode));
//2、弧头的下标i
p->adj_vex_index = i;
//3、头插法插进去，插的时候找到弧尾，那就是顶点数组的下标i
p->next = (*g)->adjlist[j].firstedge;
//4、将顶点数组[i].firstedge设置为p
(*g)->adjlist[j].firstedge = p;
}
}
}
//打印输出
void putGraph(GraphLink g){
int i;
printf("邻接表中存储信息\n");
//遍历一遍顶点坐标，每个再进去走一次
for (i = 0; i<g->node_num; i++) {
EdgeNode *p = g->adjlist[i].firstedge;
while (p) {
printf("%c->%c ",g->adjlist[i].data,g->adjlist[p->adj_vex_index].data);
p = p->next;
}
printf("\n");
}
}
打印结果
int main(int argc, const char * argv[]) {
@autoreleasepool {
// insert code here...
NSLog(@"邻接表实现图的存储!");
GraphLink g = (Graph *)malloc(sizeof(Graph));
CreateGraph(&g);
putGraph(g);
}
return 0;
}
/*
打印结果
2020-04-30 11:24:44.034591+0800 邻接表[1490:80421] 邻接表实现图的存储!
输入顶点数目,边数和有向:
4,5,0
输入顶点信息:
0 1 2 3
输入边的信息:
0,1
0,2
0,3
2,1
2,3
邻接表中存储信息
0->3 0->2 0->1
1->2 1->0
2->3 2->1 2->0
3->2 3->0
Program ended with exit code: 0
*/
网友评论