数据结构与算法 图以及图的存储

认识图：

图状结构是一种比树形结构更复杂的非线性结构。在树形结构中，结点间具有分支层次关系，每一层上的结点只能和上一层的至多一个结点相关，但可能和下一层的多个结点相关。而在图状结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。因此，图是 比树更一般、更复杂的非线性结构，常被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。

图的定语

图（Graph）是由非空的顶点集合和一个描述顶点之间的关系——边（或者弧）的集合组成的，其形式化定义为：G=(V,E)、V={v1|v1包含data object}、E={(v1,vj)|(vi,vj 包含V^P(vj,vj)。其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，集合E中P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(v1,vj）表示一条边。如：G2=(V2,E2)、V2={v1,v2,v3,v4}、E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。

基本术语

1、无向图：在一个图中，如果任意两个顶点构成的偶对(vi,vj）包含E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。

无向图.png

2、有向图：在一个图中，如果任意两个顶点构成的偶对<vj,vj>包含E是有序的（有序对常常用尖括号“<>”表示），即顶点之间的连线是有方向的，则称该图为有向图。

有向图

3、顶点、边、弧、弧头、弧尾：在图中，数据元素vi称为顶点（Vertex）；（vj，vj）表示在顶点vi和顶点vj之间有一条直接连线。如果是在无向图中，则称这条连线为边；如果是在有向图中，一般称这条连线为弧。边用顶点的无序偶对（vi，vj）来表示，称顶点vi和vj互为邻接点，边<vi,vj>依附于顶点vi与顶点vj；弧用顶点的有序偶对<vi,vj>来表示，有序偶对的第一个节点vi被称为始点(或弧尾），在图中就是不带箭头的一端；有序偶对的第二个节点vj被称为终点(或弧头），在图中就是带箭头的一端。

4、无向完全图：在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以证明，在一个含有n个顶点的无向完全图中，有n（n-1）/2条边。

无向图完全图

5、有向完全图：在有一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条边。

有向图完全图

6、顶点的度、入度、出度：顶点的度（Degree）是指依附于某顶点v的边数，通常记为TD(v)。顶点v的入度是指以顶点v为终点的弧的数目，记为ID(V)；出度是指以顶点v为始点的弧的数目，记为OD(V)。有TD(V)=ID(v)+OD(v)。

7、边的权、网：与边有关的数据信息称为权(Weight)。在实际应用中，权值可以有某种含义。例如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间或其他代价等。边上带权的图称为网或网络（network）。

8、路径、路径长度：顶点vp到顶点vq之间的路径（path）是指顶点序列vp、vi1、vi2、···、vim、vq。其中，（vp，vi1）、（vi1，vi2）、···、（vim，vq）分别为图中的边。路径上边的数目称为路径长度。

9、简单路径、回路、简单回路：序列中顶点不重复出现的路径称为简单路径。路径中第一个顶点与最后一个顶点相同的 路径称为回路或环（Cycle）。除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。

10、子图：对于图G=（V，E），G'=（V',E'），若存在 V'是V的子集， E'是E的子集，则称图 G'是G的的一个子图。

11、连通、连通图、连通分量：在无向图中，如果从一个顶点vi到另一个顶点vj(i=!j)存在路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。无向图的极大连通子图称为连通分量，极大连通子图是指在保证连通与子图的条件下，包含原图中所有的顶点与边。 如下图：

12、强连通图、强连通分量：对于有向图来说，若图中任意一对顶点vi和vj（i=!j）均存在从一个顶点vi到另一个顶点vj和从vj到vi的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量，极大强连通子图的含义同上。

13、生成树：所谓连通图G的生成树，是G的包含其全部n个顶点的一个极小连通子图，所谓极小连通子图是指在包含所有顶点且保证连通的前提下尽可能少地包含原图中的边。生成树必定包含且仅包含连通图G的n-1条边。在生成树中添加任意一条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中减少任意一条边，则必然成为非连通的。

14、生成森林：在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。

图的存储

1.顺序存储结构，又称邻接矩阵

#include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100 /* 最大顶点数，应由用户定义 */
#define INFINITYC 0

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char VertexType; /* 顶点类型应由用户定义  */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
typedef struct
{
    VertexType vexs[MAXVEX]; /* 顶点表 */
    EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
    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 (int i = 0; i < G->numNodes; i++) {
        printf("\n");
        for (int j = 0; j < G->numNodes; j++) {
            printf("%d ",G->arc[i][j]);
        }
    }
    printf("\n");
}

int main(void)
{
    printf("邻接矩阵实现图的存储\n");
    /*图的存储-邻接矩阵*/
    MGraph G;
    CreateMGraph(&G);
    return 0;
}

2.链式存储结构，又称邻接表

#include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"


#define M 100
#define true 1
#define false 0

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 creatGraph(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);
        
        //①新建一个节点
        p = (EdgeNode *)malloc(sizeof(EdgeNode));
        //②弧头的下标
        p->adj_vex_index = j;
        //③头插法插进去，插的时候要找到弧尾，那就是顶点数组的下标i
        p->next = (*g)->adjlist[i].firstedge;
        //④将顶点数组[i].firstedge 设置为p
        (*g)->adjlist[i].firstedge = p;
        
        //j->i
        if(!(*g)->is_directed)
        {
            // j -----> i
            //①新建一个节点
            p = (EdgeNode *)malloc(sizeof(EdgeNode));
            //②弧头的下标i
            p->adj_vex_index = i;
            //③头插法插进去，插的时候要找到弧尾，那就是顶点数组的下标i
            p->next = (*g)->adjlist[j].firstedge;
            //④将顶点数组[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[]) {
    // insert code here...
    printf("邻接表实现图的存储\n");
    /*
     邻接表实现图的存储
     输入顶点数目,边数和有向？：
     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
    */
    /*
     邻接表实现图的存储
     输入顶点数目,边数和有向？：
     4 5 1
     输入顶点信息：
     0 1 2 3
     输入边信息：
     1 0 1 2 2 1 2 0 0 3
     邻接表中存储信息:
     0->3
     1->2 1->0
     2->0 2->1
     */
    GraphLink g = (Graph *)malloc(sizeof(Graph));
    creatGraph(&g);
    putGraph(g);
    return 0;
}