图的邻接矩阵表示法

数据结构定义

1
2
3
4
5
6
7
8
9
typedef struct AdjNode {
    struct AdjNode* next;/*后继顶点*/
    char vtxname;	/*顶点名称*/
}AdjNode;

typedef struct Graph{
    struct AdjNode* list[MAX_SIZE]; /*头节点列表*/
    int vtxnum; /*顶点数*/
}Graph;

图的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*初始化图*/
struct Graph* initGraph();

/*根据顶点名称找到顶点索引*/
int findNodeIndex(Graph *graph,char vtxname);
/*根据顶点名称找到顶点指针*/
AdjNode *findNode(Graph *graph,char vtxname);


/*在邻边链表中删除元素的辅助函数*/
int deleteEdgeHelp(AdjNode* head,char vtx);
/*在vtx1邻边链表中删除元素vtx2*/
int deleteEdge(Graph *graph,char vtx1,char vtx2);
/*在图中添加边 <vtx1,vtx2> */
int addEdge(Graph *graph,char vtx1,char vtx2);

/*添加顶点*/
void addVertex(Graph *graph,char vtxname);
/*删除顶点*/
void deleteVertex(Graph *graph,char vtxname);

/*打印与顶点邻接的边*/
void printNeibor(AdjNode* head);
/*打印图*/
void printGraph(Graph *graph)

初始化图

1
2
3
4
5
6
/*初始化图*/
struct Graph* initGraph()
{
    Graph* graph=(Graph *)malloc(sizeof(struct Graph));
    graph->vtxnum=0;
}

添加删除边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int addEdge(Graph *graph,char vtx1,char vtx2){
    /*查找顶点vtx1*/
    AdjNode *head=findNode(graph,vtx1);
    if(!head)   return -1;

    AdjNode *node=(struct AdjNode*)malloc(sizeof(struct AdjNode));
    node->vtxname=vtx2;

     /*头插法*/
    node->next=head->next;
    head->next=node;
    return 0;
}

int deleteEdgeHelp(AdjNode* head,char vtx){
   
    AdjNode *current=head;
    AdjNode *pre=NULL;
    /*查找顶点vtx*/
    while(current){
        if(current->vtxname==vtx){
            pre->next=current->next; /*删除vtx2，释放空间*/
            free(current);
            return 1;
        }
        pre=current;
        current=current->next;
    }
    return 0;
}

int deleteEdge(Graph *graph,char vtx1,char vtx2){
    /*查找顶点vtx1*/
    AdjNode *head=findNode(graph,vtx1);
    if(!head)   -1;
    return deleteEdgeHelp(head,vtx2);
    
}

添加，删除，查找顶点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int findNodeIndex(Graph *graph,char vtxname){
    for(int i=0;i<graph->vtxnum;i++){
        if(graph->list[i]->vtxname==vtxname)
            return i;
    }
    return -1;
}
/*根据顶点名称找到顶点指针*/
AdjNode *findNode(Graph *graph,char vtxname){
    int index=findNodeIndex(graph,vtxname);
    if(index!=-1){
        return graph->list[index];
    }
    return NULL;
}
/*添加顶点*/
void addVertex(Graph *graph,char vtxname){
    AdjNode *adjnode=(AdjNode *)malloc(sizeof(AdjNode));
    adjnode->vtxname=vtxname;
    adjnode->next=NULL;

    graph->list[graph->vtxnum++]=adjnode;
}
/*删除顶点*/
void deleteVertex(Graph *graph,char vtxname){

    AdjNode* vtx=findNode(graph,vtxname);
    AdjNode* current=vtx->next;
    AdjNode* pre=NULL;
    while(current){
        pre=current;
        current=current->next;
        free(pre);
    }
    free(vtx);/*释放空间*/

    for(int i=0;i<graph->vtxnum;i++)
        deleteEdgeHelp(graph->list[i],vtxname); /*删除与之相连的边*/

    /*查找顶点的索引*/
    int index=-1;
    for(int i=0;i<graph->vtxnum;i++)
        if(graph->list[i]->vtxname==vtxname)
            index=i;

    /*将要删除顶点的后面元素向前移动，删除顶点*/
    for(int i=index;i<graph->vtxnum;i++)
        graph->list[i]=graph->list[i+1];
   
    graph->vtxnum--;
}

图的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*打印邻接的边*/
void printNeibor(AdjNode* head){
    AdjNode *cur=head;
    while(cur){
        printf("%c->",cur->vtxname);
        if(cur->next==NULL)
            printf("NULL");
        cur=cur->next;
    }
    printf("\n");
}
/*打印图*/
void printGraph(Graph *graph){
    for(int i=0;i<graph->vtxnum;i++){
        printNeibor(graph->list[i]);
    }
}