一、圖的一些定義

圖：頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為G=(V,E),其中G表示一個(gè)圖，V是圖G中的頂點(diǎn)的非空集合，E是圖G的邊的集合。

• 無向圖 & ?無向邊

  
  
  無向圖@2x.png

• 有向圖 &有向邊

  
  
  有向圖@2x.png

• 無向完全圖

  
  
  無向完全圖@2x.png

• 有向完全圖

  
  
  有向完全圖@2x.png

• 網(wǎng)

  
  
  網(wǎng)@2x.png

• 非聯(lián)通圖

  
  
  非聯(lián)通圖@2x.png

二、圖的存儲

圖可以通過鄰接矩陣和鄰接表進(jìn)行存儲

鄰接矩陣存儲

• 無向圖的鄰接矩陣示例

  
  
  無向圖的鄰接矩陣@2x.png

• 有向圖的鄰接矩陣示例

  
  
  有向圖的鄰接矩陣@2x.png

• 網(wǎng)的鄰接矩陣示例

  
  
  網(wǎng)的鄰接矩陣@2x.png
  
  

  代碼實(shí)現(xiàn)

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100 /* 最大頂點(diǎn)數(shù)，應(yīng)由用戶定義 */
#define INFINITYC 0

typedef int Status;    /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
typedef char VertexType; /* 頂點(diǎn)類型應(yīng)由用戶定義  */
typedef int EdgeType; /* 邊上的權(quán)值類型應(yīng)由用戶定義 */
typedef struct
{
    VertexType vexs[MAXVEX]; /* 頂點(diǎn)表 */
    EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣，可看作邊表 */
    int numNodes, numEdges; /* 圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù)  */
}MGraph;

void CreateMGraph(MGraph *G){
    
    int i,j,k,w;
    printf("輸入頂點(diǎn)數(shù)和邊數(shù):\n");
    //1. 輸入頂點(diǎn)數(shù)/邊數(shù)
    scanf("%d,%d",&G->numNodes,&G->numEdges);
    printf("頂點(diǎn)數(shù):%d,邊數(shù):%d\n",G->numNodes,G->numEdges);
    
    //2.輸入頂點(diǎn)信息/頂點(diǎn)表
    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)上的下標(biāo)i,下標(biāo)j,權(quán)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");
}

鄰接表存儲

• 無向圖鄰接表

  
  
  無向圖鄰接表@2x.png

• 有向圖鄰接表

  
  
  有向圖鄰接表-1@2x.png

有向圖鄰接表-2@2x.png

代碼實(shí)現(xiàn)：

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

typedef char Element;
typedef int BOOL;
//鄰接表的節(jié)點(diǎn)
typedef struct Node{
    int adj_vex_index;  //弧頭的下標(biāo)，也就是被指向的下標(biāo)
    Element data;       //權(quán)重值
    struct Node * next; //邊指針
}EdgeNode;

//頂點(diǎn)節(jié)點(diǎn)表
typedef struct vNode{
    Element data;          //頂點(diǎn)的權(quán)值
    EdgeNode * firstedge;  //頂點(diǎn)下一個(gè)是誰？
}VertexNode, Adjlist[M];

//總圖的一些信息
typedef struct Graph{
    Adjlist adjlist;       //頂點(diǎn)表
    int arc_num;           //邊的個(gè)數(shù)
    int node_num;          //節(jié)點(diǎn)個(gè)數(shù)
    BOOL is_directed;      //是不是有向圖
}Graph, *GraphLink;

void creatGraph(GraphLink *g){
    int i,j,k;
    EdgeNode *p;
    
    //1. 頂點(diǎn),邊,是否有向
    printf("輸入頂點(diǎn)數(shù)目,邊數(shù)和有向？：\n");
    scanf("%d %d %d", &(*g)->node_num, &(*g)->arc_num, &(*g)->is_directed);
    
    //2.頂點(diǎn)表
     printf("輸入頂點(diǎn)信息：\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);
        
        //①新建一個(gè)節(jié)點(diǎn)
        p = (EdgeNode *)malloc(sizeof(EdgeNode));
        //②弧頭的下標(biāo)
        p->adj_vex_index = j;
        //③頭插法插進(jìn)去，插的時(shí)候要找到弧尾，那就是頂點(diǎn)數(shù)組的下標(biāo)i
        p->next = (*g)->adjlist[i].firstedge;
        //④將頂點(diǎn)數(shù)組[i].firstedge 設(shè)置為p
        (*g)->adjlist[i].firstedge = p;
        
        //j->i
        if(!(*g)->is_directed)
        {
            // j -----> i
            //①新建一個(gè)節(jié)點(diǎn)
            p = (EdgeNode *)malloc(sizeof(EdgeNode));
            //②弧頭的下標(biāo)i
            p->adj_vex_index = i;
            //③頭插法插進(jìn)去，插的時(shí)候要找到弧尾，那就是頂點(diǎn)數(shù)組的下標(biāo)i
            p->next = (*g)->adjlist[j].firstedge;
            //④將頂點(diǎn)數(shù)組[i].firstedge 設(shè)置為p
            (*g)->adjlist[j].firstedge = p;
        }
    }
}

void putGraph(GraphLink g){
    int i;
    printf("鄰接表中存儲信息:\n");
    //遍歷一遍頂點(diǎn)坐標(biāo)，每個(gè)再進(jì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");
    }
}