逆鄰接表

鎖定

//圖的鄰接表
#include<stdio.h>
#include<stdlib.h>
#define MAX_VEX_NUM 20

typedef char VertexType;          //頂點類型設為字符型
typedef enum {Directed_graph, Undirected_graph} GraphType;

typedef enum {Adjacency_list,Inverse_adjacency_list} ListType;

typedef struct ArcNode{    //表節點
    VertexType adjvex;      //鄰接點
    struct ArcNode *nextarc;   //指向下一條邊的指針
} ArcNode;

typedef struct VexNode{   //頭節點
    VertexType vexdata;      //頂點名稱
    ArcNode *firstarc;     //指向第一個依附該頂點的邊的指針
} VexNode, AdjList[MAX_VEX_NUM];

typedef struct{
    AdjList vexs;   //頂點集合,即vexs[MAX_VEX_NUM]，AdjLIst為結構數組
    int vexnum;   //圖的頂點數
    int edgenum;  //圖的邊數
    GraphType graph_type;
    ListType list_type;
} ALGraph;

//函數聲明
void Create_ALGraph(ALGraph *ALG);
int Get_Index_Of_Vex(ALGraph *ALG,char vex);
void Print_ALGraph(ALGraph ALG);
void Insert_adjvex(ALGraph * ALG,int ADvex,char vex);

//創建圖並初始化圖
void Create_ALGraph(ALGraph *ALG){
    int i;
    int v1,v2;
    char c1,c2;
    int graph_type;
    int list_type;
    printf("Please input graph graph_type Directed_graph(0) or Undirected_graph(1) :");
    scanf("%d", &graph_type);
    if(graph_type==0){
        ALG->graph_type=Directed_graph;
        printf("Please input list list_type Adjacency_list(0) or Inverse_adjacency_list(1) :");
        scanf("%d",&list_type);
        if(list_type==0)
            ALG->list_type=Adjacency_list;
        else if(list_type==1)
            ALG->list_type=Inverse_adjacency_list;
        else{
            printf("Please input correct list_type!\n");
            return ;
        }
    }
    else if(graph_type==1)
        ALG->graph_type=Undirected_graph;
    else{
        printf("Please input correct graph graph_type!\n");
        return ;
    }

    printf("Please input vexmun : ");
    scanf("%d",&ALG->vexnum);
    printf("Please input edgenum : ");
    scanf("%d",&ALG->edgenum);
    getchar();
    //頂點為字符型數據,以需要用getcgar()來接收換行符,也可用fflush(stdin)清空輸入緩存區
    for(i=0;i<ALG->vexnum;i++){
        printf("Please input %dth vex(char):",(i+1));
        scanf("%c",&(ALG->vexs[i].vexdata));
        getchar();
        ALG->vexs[i].firstarc=NULL;
    }
    if(ALG->graph_type==1){
        for(i=0;i<ALG->edgenum;i++){
            printf("Please input %dth edge v1(char) v2(char) : ",i+1);
            scanf("%c %c",&c1,&c2);
            getchar();
            v1=Get_Index_Of_Vex(ALG,c1);   //v1的位置
            v2=Get_Index_Of_Vex(ALG,c2);   //v2的位置
            Insert_adjvex(ALG,v1,c2);
            Insert_adjvex(ALG,v2,c1);
        }
    }
    else{
        if(ALG->list_type==0){
            for(i=0;i<ALG->edgenum;i++){
                printf("Please input %dth edge v1(char) v2(char) : ",i+1);
                scanf("%c %c",&c1,&c2);
                getchar();
                v1=Get_Index_Of_Vex(ALG,c1);   //v1的位置
                v2=Get_Index_Of_Vex(ALG,c2);   //v2的位置
                Insert_adjvex(ALG,v1,c2);
            }
        }
        else{
            for(i=0;i<ALG->edgenum;i++){
                printf("Please input %dth edge v1(char) v2(char) : ",i+1);
                scanf("%c %c",&c1,&c2);
                getchar();
                v1=Get_Index_Of_Vex(ALG,c1);   //v1的位置
                v2=Get_Index_Of_Vex(ALG,c2);   //v2的位置
                Insert_adjvex(ALG,v2,c1);
            }
        }
    }
}

//根據名稱得到指定頂點在頂點集合中的下標
int Get_Index_Of_Vex(ALGraph *ALG,char vex){
    int i;
    for(i=0;i<ALG->vexnum;i++)
        if(ALG->vexs[i].vexdata==vex)
            return i;
    return 0;
}

//打印鄰接表
void Print_ALGraph(ALGraph ALG){
    int i,j;
    ArcNode *first;
    
    if(ALG.graph_type==Directed_graph){
        printf("Graph graph_type: Direct graph\n");
    }
    else{
        printf("Graph graph_type: Undirect graph\n");
    }

    printf("Graph vertex number: %d\n",ALG.vexnum);
    printf("Graph edge number: %d\n",ALG.edgenum);
 
    printf("Vertex set:");
    for(i=0;i<ALG.vexnum;i++)
        printf("%3c",ALG.vexs[i].vexdata);
    printf("\n");

    if(ALG.graph_type==Undirected_graph||ALG.list_type==Adjacency_list)
        printf("Adjacency List:\n");
    else if(ALG.list_type==Inverse_adjacency_list)
        printf("Inverse Adjacency List:\n");

    for(i=0;i<ALG.vexnum;i++){
        printf("V%d | %c",i,ALG.vexs[i].vexdata);
        if(ALG.vexs[i].firstarc!=NULL){
            first=ALG.vexs[i].firstarc;
            while(first){
                printf(" --> %c ",first->adjvex);
                first=first->nextarc;
            }
        }
        printf("\n");
    }
}

//插入鄰接點
void Insert_adjvex(ALGraph *ALG,int ADvex,char vex){
    ArcNode *arc1,*arc2;
    arc1=(ArcNode *)malloc(sizeof(ArcNode));
    arc1->adjvex=vex;
    arc1->nextarc=NULL;
    if(ALG->vexs[ADvex].firstarc==NULL){
        ALG->vexs[ADvex].firstarc=arc1;
    }
    else{
        arc2=ALG->vexs[ADvex].firstarc;
        while(arc2->nextarc){
            arc2=arc2->nextarc;
        }
        arc2->nextarc=arc1;
    }
}

int main(){
    ALGraph ALG;
    Create_ALGraph(&ALG);
    Print_ALGraph(ALG);
    return 0;
}

逆鄰接表

逆鄰接表

逆鄰接表