图的基本概念

定义：

1. 图G由V(G)和E(G)这两个集合组成，即为 G=(V, E),其中V(G)是顶点的非空集，E(G)是边的集合，E(G)可以是空集。
2. E(G)为无向边的集合，图称为无向图，E(G)为有向边的集合，图称为有向图。
3. 所有顶点到其他顶点都有边，则称此图为完全图。
4. 边上带权的图称为带权图或网络。
5. 图中与每个顶点相连的边数称为该顶点的度，入度是以该顶点为终点的入边数目，出度是以该顶点为起点的出边数目。
6. 路径是指顶点序列，路径长度对于无权图来说就指沿此路径上边的数目，对于有权图来说是取沿路径各边的权之和作为此路径的长度。若路径经过的各顶点均不重复，则称为简单路径。若路径起点与终点相同则称为环路。
7. 在无向图中，如果从顶点V1到V2之间有路径，称这两个顶点是连通的。如果图中任意一对顶点都是连通的，则称这两个图是连通的。非连通图中每一个极大连通子图称为连通分量。有向图还有强连通之谈。

图的存储方式

邻接矩阵：邻接矩阵是表示图的数据结构中最简单的一种，对于一个有n个点的图，我们需要一个n*n的矩阵，对于这个图，第i行第j列表示点ai到点aj的距离。
使用邻接矩阵的时候我们需要初始化，map1[i][i]=0，map1[i][j]=∞。每读入一组数据将map1[i][j]赋值为value即可。
对于邻接矩阵，初始化需要O（n^{2）的时间，建图需要O（m）的时间，而且空间复杂度是O（n}2）。
虽然邻接矩阵非常简单，但很少有算法选择时间和空间都如此高的邻接矩阵来存储图。但也有使用邻接矩阵较简单的 如：Floyd

typedef int InfoType;
typedef struct 
{
    int no;//顶点编号
    InfoType info;//其他信息
}VertexType;
typedef struct
{
    int edges[MAXV][MAXV];//邻接矩阵
    int n, e;//顶点个数，边个数
    VertexType vexs[MAXV];//存放顶点信息
}MGraph;

---

邻接表：图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点i的边（对有向图是以顶点i为尾的边）。每个单链表上附设一个表头节点。

typedef struct Edge
{
    int adjvex;
    struct Edge *nextEdge;
}Edge;
//顶点表
typedef struct VNode
{
    int data;
    Edge *firstEdge;
}VNode;
//邻接表
typedef struct AGraph
{
    VNode adjlist[MAXSIZE];
    int n,e;
}AGraph;


图中的这n个节点，我们需要知道哪些边是和它相接的，所以，对应每个节点（VNode），我们需要一个头指针（firstEdge），指向其第一条边，通过这个指针，邻接表中每个节点就具有了向外延伸的能力。延伸的过程就是建立单向链表。类似于“头插法”。
邻接表表示，最直观的就是表示了图中的n个节点，以及和每个节点相邻的边，节点存储在顺序表中，边存储在单向链表中。

创建邻接表

void creategra(AGraph *g,int n,int e)
{
    Edge *s;
    g->n = n;
    g->e = e;
    for(int i=0;i<n;i++)
    {
        g->adjlist[i].data=i;
        g->adjlist[i].firstEdge=NULL;
    }
    printf("input the edge\n");
    int a,b;
    for(int i=0;i<e;i++)
    {
        scanf("%d%d",&a,&b);  //a到b有路径
        s = (Edge *)malloc(sizeof(Edge));
        s->adjvex=b;
        s->nextEdge=g->adjlist[a].firstEdge;
        g->adjlist[a].firstEdge=s;
    }
}

先将所有节点加入到节点数组中
然后每个节点可以延伸出一个单链表用来存储边

邻接表图示：

邻接表与逆向邻接表.png