圖的定義

圖(Graph)是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間的集合組成瘟仿，通常表示為G[V, E]箱锐，其中G表示一個(gè)圖，V是圖G的頂點(diǎn)集合猾骡，E是圖G中邊的集合瑞躺。

圖

圖的存儲(chǔ)

1.鄰接矩陣(順序)

1.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

#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;

1.2 存儲(chǔ)

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;
        //如果無(wú)向圖,矩陣對(duì)稱;
        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");

1.3 測(cè)試

int main(void)
{
    printf("鄰接矩陣實(shí)現(xiàn)圖的存儲(chǔ)\n");
    /*圖的存儲(chǔ)-鄰接矩陣*/
    MGraph G;
    CreateMGraph(&G);
    return 0;
}

2.鄰接表

2.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

#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è)是誰(shuí)嫂便？
}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;

2.2 存儲(chǔ)

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("鄰接表中存儲(chǔ)信息:\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");
    }
}

2.3 測(cè)試

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("鄰接表實(shí)現(xiàn)圖的存儲(chǔ)\n");
    /*
     鄰接表實(shí)現(xiàn)圖的存儲(chǔ)
     輸入頂點(diǎn)數(shù)目,邊數(shù)和有向凸丸？：
     4 5 0
     輸入頂點(diǎn)信息：
     0 1 2 3
     輸入邊信息：
     0 1 0 2 0 3 2 1 2 3
     鄰接表中存儲(chǔ)信息:
     0->3 0->2 0->1
     1->2 1->0
     2->3 2->1 2->0
     3->2 3->0
    */
    /*
     鄰接表實(shí)現(xiàn)圖的存儲(chǔ)
     輸入頂點(diǎn)數(shù)目,邊數(shù)和有向？：
     4 5 1
     輸入頂點(diǎn)信息：
     0 1 2 3
     輸入邊信息：
     1 0 1 2 2 1 2 0 0 3
     鄰接表中存儲(chǔ)信息:
     0->3
     1->2 1->0
     2->0 2->1
     */
    GraphLink g = (Graph *)malloc(sizeof(Graph));
    creatGraph(&g);
    putGraph(g);
    return 0;
}