图的存储

定义：图形结构是一种比树形结构更复杂的非线性结构。在树形结构中，结点间具有分支层次关系，每一层上的结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。而在图形结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的 。

图的结构有无向图，有向图，网图

无向图.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
*/