图

图（Graph）通常表示为： G(V,E)。其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。
- 在图中，不允许没有顶点。若 V 是图的顶点的集合，那么，V 是非空
  有穷集合。
- 图的任意两个顶点之间都可能有关系，它们的关系用边来表示。边集可
  以是空的。
无向边用小括号 “（）”表示，有向边用尖括号“<>”表示。

无向图

邻接矩阵存储结构

typedef char VertexType;
typedef int EdgeType;
#define MAXVEX 100;     // 最大顶点数
#define INFINITY 65535;  
typedef struct
{
    VertexType vexs[MAXVEX];    // 顶点表
    EdgeType arc[MAXVEX][MAXVEX];   // 邻接矩阵，可看作边表
    int numVertexes, numEdges;  // 图中当前顶点数和边数
}MGraph;

void CreateGraph(MGraph *G)
{
    int i, j, k, w;
    printf("%s", "输入顶点数和边数:\n");
    scanf("%d, %d", &G->numVertexes, &G->numEdges);     // 输入顶点数和边数
    for(i = 0; i < G->numVertexes; i++){
        scanf(&G->vexs[i]);
    }
    for(i = 0; i < G->numVertexes; i++){
        for(j = 0; j < G->numVertexes; j++){
            G->arc[i][j] = INFINITY;    // 邻接矩阵初始化
        }
    }
    for(k = 0; k < G->numEdges; k++){   // 读入numEdges条边，建立邻接矩阵
        printf("输入边(vi,vj)上的下标i、下标j和权w:\n");
        scanf("%d, %d, %d", &i, &j, &w);    // 输入边（vi,vj）上的权w
        G->arc[i][j] = w;
        G->arc[j][i] = G->arc[i][j];    // 因为是无向图，矩阵对称
    }
}

邻接表结构

当图为无向图的时候，这个线性表叫做顶点 $v_i$ 的边表。

typedef char VertexType;
typedef int EdgeType;

typedef struct EdgeNode     // 边表结点
{
    int adjvex;     // 邻接点域，存储该顶点对应的下标
    EdgeType weight;    // 权值
    struct EdgeNode *next;  // 链域，指向下一个连接点
}EdgeNode;

typedef struct VertexNode   // 顶点表结点
{
    VertexType data;    // 顶点域，存储顶点信息
    EdgeNode *firstEdge;    // 边表头指针
}VertexNode, AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;
    int numVertexes, numEdges;      // 图中当前顶点数和边数
}GraphAdjList;

无向图的邻接表创建代码

void CreateALGraph(GraphAdjList *G)
{
    int i, j, k;
    EdgeNode *e;
    printf("输入顶点数和边数：\n");
    scanf("%d, %d", &G->numVertexes, &G->numEdges);     // 输入顶点数和边数 
    
    for(i = 0; i < G->numVertexes; i++){
        scanf(&G->adjList[i].data);     // 输入顶点信息。
        G->adjList[i].firstEdge = NULL;     // 将边表置为空表。
    }
    
    for(k = 0; k < G->numVertexes; i++){    // 建立边表
        printf("输入边(Vi,Vj)上的顶点序号：\n");
        scanf("%d, %d", &i, &j);    // 输入边(Vi,Vj)上的顶点序号
        e = (EdgeNode *)malloc(sizeof(EdgeNode));       // 申请内存空间，创建边表结点
        e->adjvex = j;      // 邻接序号为j
        e->next = G->adjList[i].firstEdge;  // 将e指针指向当前顶点指向的结点
        G->adjList[i].firstEdge = e;    // 将当前顶点的指针指向e
        e = (EdgeNode *)malloc(sizeof(EdgeNode));   // 申请内存空间，创建边表结点
        e->adjvex = i;  // 邻接序号为i
        e->next = G->adjList[j].firstEdge;  // 将e指针指向当前顶点指向的结点
        G->adjList[j].firstEdge = e;    // 将当前顶点的指针指向e
    }
}

有向图

邻接表结构
- 当图为有向图的时候，这个线性表叫做顶点 $v_i$ 作为弧尾的出边表。

网

邻接表结构