定義：

圖是由由頂點的有窮非空集合和頂點之間邊的集合組成，可以定義為：
G=(V, E)
其中，
V = {x|x∈某個數(shù)據(jù)元素集合}
E ={(x，y)|x，y∈V} 或
E = {＜x， y＞|x，y∈V并且Path(x， y)}
其中，（x，y）表示從 x到 y的一條雙向通路，即（x，y）是無方向的；Path（x，y）表示從 x到 y的一條單向通路，即Path（x，y）是有方向的。
簡單來說：G是圖，V是圖中頂點的集合，E是圖中邊的集合

特點：

在線性表中，每個元素之間只有一個直接前驅(qū)和一個直接后繼，
在樹形結(jié)構(gòu)中，數(shù)據(jù)結(jié)構(gòu)是層次關(guān)系，并且每一層上的數(shù)據(jù)可能和下一層中多個元素相關(guān)，但只能和上一層中一個元素相關(guān)
非線性結(jié)構(gòu)，是研究數(shù)據(jù)元素之間的多對多的關(guān)系。在這種結(jié)構(gòu)中，任意兩個元素之間可能存在關(guān)系。即結(jié)點之間的關(guān)系可以是任意的，圖中任意元素之間都可能相關(guān)

基本術(shù)語

在圖中的數(shù)據(jù)元素，我們稱之為頂點（Vertex）
頂點之間的邏輯關(guān)系用邊來表示，邊集可以是空的
若頂點之間的邊沒有方向，則稱這條邊為無向邊,用無序偶（）來表示
圖中的每一條邊都是沒有方向的
若頂點之間的邊有方向，則稱這條邊為有向邊，也稱為弧（Arc），用有序偶<>來表示,稱為弧尾，稱為弧頭
圖中的每一條邊都是有方向的
在圖結(jié)構(gòu)中，若不存在頂點到其自身的邊，且同一條邊不重復(fù)出現(xiàn)，則稱這樣的圖為簡單圖
在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。含有n個頂點的無向完全圖有n(n-1)/2條邊。
在有向圖中，如果任意兩個頂點之間都存在互為相反的兩條弧，則稱該圖為有向完全圖。含有n個頂點的無向完全圖有n(n-1)條邊。
通常認(rèn)為邊或弧數(shù)小魚n*logn（n是頂點的個數(shù)）的圖稱為稀疏圖，反之稱為稠密圖。
有些邊或弧帶有與他相關(guān)的數(shù)字，這種與圖的邊或弧相關(guān)的數(shù)字，稱為權(quán)
帶權(quán)的圖稱為網(wǎng)
假設(shè)有兩個圖,G1=(V1, E1) 和 G2=(V2, E2)。如果V2∈V1 且 E2∈E1,則稱G2為G1的子圖

鄰接矩陣

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include <stdlib.h>
#define isLetter(a)  ((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z')))
#define LENGTH(a)  (sizeof(a)/sizeof(a[0]))
typedef char vertexType;
typedef int edgeType;
typedef struct _GraphMatrix{
    int vertexNumber;// 頂點數(shù)
    int edgeNumber; // 邊數(shù)
    vertexType *vertex;// 頂點集合
    edgeType **edge;// 鄰接矩陣
}GraphMatrix;

void Printf_G(GraphMatrix *g){
    for(int i=0;i<g->vertexNumber;i++){
        for(int j=0;j<g->vertexNumber;j++){
            printf("%d\t",g->edge[i][j]);
        }
        printf("\n");
    }
}
void Printf_All(GraphMatrix *g){
    int flag=1;
    for(int i=0;i<g->vertexNumber;i++){
        if(flag){
            printf(" \t");
            flag=0;
        }
        printf("%c\t",g->vertex[i]);
    }
    printf("\n");
    for(int i=0;i<g->vertexNumber;i++){
        printf("%c\t",g->vertex[i]);
        for(int j=0;j<g->vertexNumber;j++){
            printf("%d\t",g->edge[i][j]);
        }
        printf("\n");
    }
}
/*
 * 返回ch在matrix矩陣中的位置
 */
int Get_Position(GraphMatrix g, char ch){
    int i;
    for(i=0; i<g.vertexNumber; i++){
        if(g.vertex[i]==ch)
            return i;
    }
    return -1;
}
/*
 * 讀取一個輸入字符
 */
char Read_Char(){
    char ch;
    do {
        ch = getchar();
    } while(!isLetter(ch));
    return ch;
}
void Init_GraphMatrix(GraphMatrix *g){
      //初始化圖
    int v,e;
    printf("請輸入頂點數(shù)量：");
    scanf("%d",&v);
    printf("請輸入邊數(shù)量：");
    scanf("%d",&e);
    if ( v < 1 || e < 1 || (e > (v * (v-1)))){
        printf("輸入?yún)?shù)有誤!\n");
        exit(0);
    }
    g->vertexNumber=v;
    g->edgeNumber=e;
    //分配空間
    g->vertex=(vertexType*)malloc(g->vertexNumber*sizeof(vertexType));
    // 初始化"邊"
    g->edge=(edgeType**)malloc(g->vertexNumber*sizeof(edgeType));
    for(int i=0;i<g->vertexNumber;i++){
        g->edge[i]=(edgeType*)malloc(g->vertexNumber*sizeof(edgeType));
        for(int j=0;j<g->vertexNumber;j++){
            g->edge[i][j]=0;
        }
    }
    printf("初始化完畢\n");
    Printf_G(g);
}


GraphMatrix* Create_GraphMatrix(){
    char c1, c2;
    int p1, p2;
    GraphMatrix *g;
    if ((g=(GraphMatrix*)malloc(sizeof(GraphMatrix))) == NULL )
    return NULL;
    memset(g, 0, sizeof(GraphMatrix));
    Init_GraphMatrix(g);
    for (int i = 0; i < g->vertexNumber; i++){
        printf("請輸入頂點(%d)的值: ", i);
        g->vertex[i] = Read_Char();
    }
    for (int i = 0; i < g->edgeNumber; i++){
        // 讀取邊的起始頂點和結(jié)束頂點
        printf("請輸入邊(%d)起始頂點和結(jié)束頂點:", i);
        c1 = Read_Char();
        c2 = Read_Char();
        p1=Get_Position(*g, c1);
        p2=Get_Position(*g, c2 );
        if (p1==-1 || p2==-1){
            printf("輸入有誤: 無效的邊!\n");
            free(g);
            exit(0);
        }
        g->edge[p1][p2]=1;
        g->edge[p2][p1]=1;
    }
    Printf_All(g);
    return g;
}


int main()
{
    GraphMatrix *gm=Create_GraphMatrix();

    return 0;
}

鄰接表

#include <stdio.h>
#include <stdlib.h>
typedef char vertexType;
typedef struct ListEdgeNode{
    int index;                  // 邊的下標(biāo)
    struct ListEdgeNode *next;          // 指向下一個節(jié)點的指針
}ListEdgeNode;

typedef struct ListVertexNode {
    vertexType vertex;          // 頂點
     ListEdgeNode *fistEdge;        // 指向第一條邊
} ListVertexNode;

typedef struct GraphList{
    int vertexNumber;           // 頂點的數(shù)量
    int edgeNumber;             // 邊的數(shù)量
    ListVertexNode *vertex;     // 頂點集合，動態(tài)數(shù)組
}GraphList;
void GraphList_create(GraphList *g){
    printf("請分別輸入圖的頂點數(shù)量和邊的數(shù)量，用空格隔開：");
    scanf("%d %d", &g->vertexNumber, &g->edgeNumber);       //將頂點數(shù)量和邊的數(shù)量存儲在結(jié)構(gòu)體g中相應(yīng)的變量
    //為動態(tài)數(shù)組申請空間
    g->vertex = (ListVertexNode*)malloc(g->vertexNumber * sizeof(ListVertexNode));
    //初始化頂點指的第一條邊
    for (int i = 0; i < g->edgeNumber; i++){
        g->vertex[i].fistEdge = NULL;
    }

    //輸入圖的信息
    ListEdgeNode *listEdgeNode;
    for (int k = 0; k < g->edgeNumber; k++){
        int i, j;
        printf("請輸入邊(vi,vj)的下標(biāo), i和j，用空格隔開:");
        scanf("%d%d", &i, &j);
        //始終將插入的節(jié)點放在頂點所指的地一條邊
        listEdgeNode = (ListEdgeNode *)malloc(sizeof(ListEdgeNode));
        listEdgeNode->index = j;
        listEdgeNode->next = g->vertex[i].fistEdge;
        g->vertex[i].fistEdge = listEdgeNode;

        listEdgeNode = (ListEdgeNode*)malloc(sizeof(ListEdgeNode));
        listEdgeNode->index = i;
        listEdgeNode->next = g->vertex[j].fistEdge;
        g->vertex[j].fistEdge = listEdgeNode;

    }

    //輸出圖的信息
    ListEdgeNode * len = NULL;
    for (int i = 0; i < g->vertexNumber; i++){
        
        if (g->vertex[i].fistEdge != NULL)
            len = g->vertex[i].fistEdge;
        while (len!= NULL){
            printf("%d --- %d\t", i,len->index);
            len = len->next;
        }
        printf("\n");
    }