图是一种中一对多的数据类型。图的表示方法有邻接矩阵法，十字链表法。

图的操作包括

  • Adjacent(G,x,y):判断图G是否存在边<x,y>或(x,y)。

  • Neighbors(G,x):列出图G中与结点x邻接的边。

  • InsertVertex(G,x):在图G中插入顶点x。

  • DeleteVertex(G,x):从图G中删除顶点x。

  • AddEdge(G,x,y):若无向边(x,y)或有向边<x,y>不存在，则向图G中添加该边。

  • RemoveEdge(6,x,y):若无向边(x,y)或有向边<x,y>存在，则从图G中删除该边。

  • FirstNeighbor(G,x):求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。

邻接矩阵表示适合密集图

图的存储方式

1
2
3
4
5
6
7
#define MAX_SIZE 10
typedef struct Graph
{
    int vexnum; /*节点个数*/
    int vertices[MAX_SIZE]; /*节点数组*/
    int matrix[MAX_SIZE][MAX_SIZE]; /*邻接矩阵*/
}Graph;

图的初始化

1
2
3
4
5
6
7
8
9
10
11
12
/*初始化图*/
Graph * initGraph(){
    Graph *graph=(Graph *)malloc(sizeof(struct Graph));
    /*没有边，值设为0*/
    for(int i=0;i<MAX_SIZE;i++){
        for(int j=0;j<MAX_SIZE;j++)
            graph->matrix[i][j]=0;
        graph->vertices[i]=-1;
    }
    graph->vexnum=0;
    return graph;
}

边的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*添加边*/
 void addEdge(Graph *graph, int i, int j)
{
    if(graph->vexnum>=MAX_SIZE||i>=graph->vexnum||j>=graph->vexnum)
        return;
    
    
    graph->matrix[i][j]=1;
    graph->matrix[j][i]=1;
}
/*删除边*/
void deleteEdge(Graph* graph,int i,int j)
{
    if(i>=graph->vexnum||j>=graph->vexnum)
        return;
    graph->matrix[i][j]=graph->matrix[j][i]=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
/*添加结点*/
void addVertex(Graph *graph, int val)
{
    int num=graph->vexnum;
    graph->vertices[num]=val;

    graph->vexnum++;
}
/*删除节点*/
void removeVertex(Graph *graph, int index)
{
    if(index>=graph->vexnum||index<0)
        return;
    /*vertices在数组中删除节点*/
    for(int i=index;i<graph->vexnum-1;i++){
        graph->vertices[i]=graph->vertices[i+1];
    }
    /*横排向上覆盖*/
    for(int row=index;row<graph->vexnum;row++){
        for(int col=0;col<graph->vexnum;col++)
            graph->matrix[row][col]=graph->matrix[row+1][col];
    }
    /*竖排向左覆盖*/
    for(int row=0;row<graph->vexnum;row++){
        for(int col=index;col<graph->vexnum;col++)
            graph->matrix[row][col]=graph->matrix[row][col+1];
    }
   
    /*进行移动*/
    graph->vexnum--;
}

完整代码

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<stdio.h>
#include<stdlib.h>

#define MAX_SIZE 10
typedef struct Graph
{
    int vexnum; /*节点个数*/
    int vertices[MAX_SIZE]; /*节点数组*/
    int matrix[MAX_SIZE][MAX_SIZE]; /*邻接矩阵*/
}Graph;
/*初始化图*/
Graph * initGraph(){
    Graph *graph=(Graph *)malloc(sizeof(struct Graph));
    /*没有边，值设为0*/
    for(int i=0;i<MAX_SIZE;i++){
        for(int j=0;j<MAX_SIZE;j++)
            graph->matrix[i][j]=0;
        graph->vertices[i]=-1;
    }
    graph->vexnum=0;
    return graph;
}
/*判断图G是否存在边(x,y)*/
int adjacent(Graph *graph,int x,int y){
    return graph->matrix[x][y] || graph->matrix[y][x];
}

/*添加边*/
 void addEdge(Graph *graph, int i, int j)
{
    /*越界判断*/
    if(graph->vexnum>=MAX_SIZE||i>=graph->vexnum||j>=graph->vexnum)
        return;
    
    graph->matrix[i][j]=1;
    graph->matrix[j][i]=1;
}
/*删除边*/
void deleteEdge(Graph* graph,int i,int j)
{
    if(i>=graph->vexnum||j>=graph->vexnum)
        return;
    graph->matrix[i][j]=graph->matrix[j][i]=0;;
    
}
/*
    删除节点

      A B C D E
    A[0,0,0,0,0]
    B[0,0,0,0,0]
    C[0,1,0,0,0]
    D[0,0,0,0,0]
    E[0,0,0,0,0]
  
*/


/*删除节点*/
void removeVertex(Graph *graph, int index)
{
    if(index>=graph->vexnum||index<0)
        return;
    /*vertices在数组中删除节点*/
    for(int i=index;i<graph->vexnum-1;i++){
        graph->vertices[i]=graph->vertices[i+1];
    }
    /*横排向上覆盖*/
    for(int row=index;row<graph->vexnum;row++){
        for(int col=0;col<graph->vexnum;col++)
            graph->matrix[row][col]=graph->matrix[row+1][col];
    }
    /*竖排向左覆盖*/
    for(int row=0;row<graph->vexnum;row++){
        for(int col=index;col<graph->vexnum;col++)
            graph->matrix[row][col]=graph->matrix[row][col+1];
    }
   
    /*进行移动*/
    graph->vexnum--;
}
/*添加结点*/
void addVertex(Graph *graph, int val)
{
    int num=graph->vexnum;
    graph->vertices[num]=val;

    graph->vexnum++;
}
int firstNeighbor(Graph *graph,int x){
    for(int col=0;col<graph->vexnum;col++){
        if(graph->matrix[x][col]){
            return col;
        }
    }
    return -1;
}
/*显示图的矩阵*/
void printGraph(Graph *graph){
    printf("  ");
    /*打印节点*/
    for(int i=0;i<graph->vexnum;i++){
        printf("%d ",graph->vertices[i]);
    }
    printf("\n");
    for(int row=0;row<graph->vexnum;row++){
        printf("%d ",graph->vertices[row]);
        for(int col=0;col<graph->vexnum;col++)
            printf("%d ",graph->matrix[row][col]);
        printf("\n");
    }
}
int main(){
    Graph *graph=initGraph();
    addVertex(graph,4);
    addVertex(graph,5);
    addVertex(graph,6);
    addVertex(graph,7);

    addEdge(graph,0,2);
    addEdge(graph,0,1);
    addEdge(graph,1,2);
    addEdge(graph,3,1);
    addEdge(graph,3,2);

    printGraph(graph);
    removeVertex(graph,1);

    printGraph(graph);
    return 0;
}