圖由有窮、非空點(diǎn)集和邊集合組成，簡寫成G(V,E0)

圖的創(chuàng)建有多種方法（鄰接矩陣、鄰接表、十字鏈表）

圖的遍歷方法（深度優(yōu)先遍歷、廣度優(yōu)先遍歷）

此篇博客為一道算法題，博中代碼實(shí)現(xiàn)了鄰接矩陣創(chuàng)建有向圖，分別使用深度優(yōu)先和廣度優(yōu)先遍歷圖，并且計(jì)算圖中每個(gè)節(jié)點(diǎn)的出度與入度。

題目：

從鍵盤接收圖的頂點(diǎn)集，關(guān)系集，創(chuàng)建有向圖。
第一行依次輸入圖的頂點(diǎn)個(gè)數(shù)n，關(guān)系個(gè)數(shù)k，以空格隔開。頂點(diǎn)個(gè)數(shù)<=20
第二行依次輸入頂點(diǎn)值，類型為字符。
接下去有k行，每行為兩個(gè)字符 u 和 v，表示節(jié)點(diǎn)u 和 v 連通。格式為【uv】,中間不用空格間隔。
計(jì)算結(jié)點(diǎn)的出度和入度，并輸出，共n行。格式為【頂點(diǎn)w 出度值 入度值】，三者用空格間隔。
接下去的一行，從A頂點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先遍歷，并輸出，結(jié)點(diǎn)不間隔。
最后一行，從A頂點(diǎn)出發(fā)，進(jìn)行廣度優(yōu)先遍歷，并輸出，結(jié)點(diǎn)不間隔。

代碼：

/*
圖的鄰接矩陣
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 20

int visited[MAX] = {0};

typedef struct {
    char vex[MAX];
    int arcs[MAX][MAX];
    int vexnum , arcnum ;
}Chart ,* ChartNode;

typedef struct qnode{
    int node;
    struct qnode * pNext;
}Qnode;

typedef struct linkq{
    Qnode * front;
    Qnode * rear;
}LinkQ;


//初始化隊(duì)列 
int InitQueue(LinkQ * LQ){
    LQ->front = LQ->rear = (Qnode *)malloc(sizeof(Qnode));
    LQ->front->pNext = LQ->rear->pNext = NULL;
    LQ->front->node = LQ->rear->node = 0;
    return 0;
}

//入隊(duì) 
int EnQueue(LinkQ * LQ , int i){
    Qnode * qd = (Qnode *)malloc(sizeof(Qnode));
    qd->pNext = NULL;
    qd->node = i;
    LQ->rear->pNext = qd;
    LQ->rear = qd;
}

//出隊(duì) 
int DeQueue(LinkQ * LQ){
    int i;
    Qnode * qd = NULL;
    qd = LQ->front->pNext;
    i = qd->node;
    LQ->front->pNext = LQ->front->pNext->pNext;
    free(qd);
    if(LQ->front->pNext == NULL){
         LQ->rear = LQ->front;
    }
    return i;
}

//判空 
int QueueEmpty(LinkQ * LQ){
    if(LQ->front == LQ->rear){
        return 0;
    }else{
        return 1;
    }
}

//初始化狀態(tài) 
int Initvisited(){
    int i;
    for(i=0;i<MAX;i++){
        visited[i] = 0;
    }
    return 0;
}

//創(chuàng)建圖 
ChartNode CreatChart(){
    ChartNode chart;
    char vex_1 , vex_2;
    int i;
    chart = (ChartNode)malloc(sizeof(Chart));
    memset(chart->arcs,0,sizeof(chart->arcs));
    scanf("%d %d",&chart->vexnum,&chart->arcnum);
    //fflush(stdin);
    scanf("%s",chart->vex);
   // fflush(stdin);
    for(i=0;i<chart->arcnum;i++){
        getchar(); 
        scanf("%c%c",&vex_1,&vex_2);
       // fflush(stdin);
        chart->arcs[vex_1-65][vex_2-65] = 1;
    }
    return chart;
}

//深度優(yōu)先遍歷 
int DFS(ChartNode chart , int i){
    
    int j;
    visited[i] = 1;
    printf("%c",chart->vex[i]);
    for(j = 0;j<chart->vexnum;j++){
        if(chart->arcs[i][j]==1&&!visited[j]){
            DFS(chart,j);
        }
    }   
    return 0;
    
}

//廣度優(yōu)先遍歷 
int DFST(ChartNode chart , LinkQ * LQ){
    int i,j;
    Initvisited();
    InitQueue(LQ);
    for(i=0;i<chart->vexnum;i++){
        
        if(!visited[i]){
            visited[i] = 1;
            printf("%c",chart->vex[i]);
            EnQueue(LQ,i);
            
            while(QueueEmpty(LQ)){
                i = DeQueue(LQ);
                for(j = 0;j<chart->vexnum;j++){
                    if(chart->arcs[i][j] == 1 && !visited[j]){
                        visited[j] = 1;
                        printf("%c",chart->vex[j]);
                        EnQueue(LQ,j);
                    }
                }
            }
        }
    }   
}

//計(jì)算節(jié)點(diǎn)出入度
int Degrees(ChartNode chart){
    int i,j;
    int in = 0,out = 0;
    
    for(i = 0;i<chart->vexnum;i++){
        for(j = 0;j<chart->vexnum;j++){
            if(chart->arcs[i][j] == 1){
                out++;
            }
            if(chart->arcs[j][i] == 1){
                in++;
            }
        }
        printf("%c %d %d\n",chart->vex[i],out,in);
        in = 0;
        out = 0;
    }
}


int main(){
    
    ChartNode chart = NULL;
    LinkQ LQ;
    int i,j;
    chart = CreatChart();   
    Initvisited();
    Degrees(chart);
    DFS(chart,0);
    printf("\n");   
    DFST(chart , &LQ);
    return 0;
}