图的基本操作

图的基本操作

基本操作

  1. Adjacent(G,x,y):判断图G是否存在边<x,y>或(x,y)。
  • 无向图
  • 有向图
  • 代码实现
    1
    2
    3
    int Adjacent(Graph *graph, int src, int dest) {
        return graph->edges[src][dest];
    }
  1. Neighbors(G, x):列出图G中与结点x邻接的边。
  • 无向图
  • 有向图
  • 代码实现
    1
    2
    3
    4
    5
    6
    7
    void neighbors(Graph *graph, int vertex) {
        for (int i = 0; i < graph->numVertices; i++) {
            if (graph->edges[vertex][i] == 1) {
                printf("Edge: <%d, %d>\n", vertex, i);
            }
        }
    }
  1. Insertvertex (G,x):在图 G 中插入顶点 x。
  • 代码实现
    1
    2
    3
    void insertVertex(Graph *graph, int vertex) {
        graph->vertices[vertex] = 1;
    }
  1. DeleteVertex (G, x):从图 G 中删除顶点 x。
  • 无向图
  • 有向图
  • 代码实现
    1
    2
    3
    4
    5
    6
    7
    void deleteVertex(Graph *graph, int vertex) {
        graph->vertices[vertex] = 0;
        for (int i = 0; i < graph->numVertices; i++) {
            graph->edges[vertex][i] = 0;
            graph->edges[i][vertex] = 0;
        }
    }
  1. AddEdge (G, x, y)：若无向边(x,y)或有向边<x,y>不存在，.则向图G中添加该边
  • 代码实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 有向图
    void addEdge(Graph *graph, int src, int dest) {
        graph->edges[src][dest] = 1;
    }
    // 无向图
    void addEdge(Graph *graph, int src, int dest) {
        graph->edges[src][dest] = 1;
        graph->edges[dest][src] = 1;
    }
  1. RemoveEdge (G, x, y):若无向边(x,y)或有向边<x,y>存在，则从图G中删除该边.
  • 代码实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 有向图
    void removeEdge(Graph *graph, int src, int dest) {
        graph->edges[src][dest] = 0;
    }
    // 无向图
    void removeEdge(Graph *graph, int src, int dest) {
        graph->edges[src][dest] = 0;
        graph->edges[dest][src] = 0;
    }
  1. FirstNeighbor (G, x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x,则返回-1。
  • 无向图
  • 有向图
  • 代码实现
    1
    2
    3
    4
    5
    6
    7
    8
    int firstNeighbor(Graph *graph, int vertex) {
        for (int i = 0; i < graph->numVertices; i++) {
            if (graph->edges[vertex][i] == 1) {
                return i;
            }
        }
        return -1;
    }
  1. NextNeighbor (G, x, y):假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
  • 代码实现
    1
    2
    3
    4
    5
    6
    7
    8
    int nextNeighbor(Graph *graph, int vertex, int neighbor) {
        for (int i = neighbor + 1; i < graph->numVertices; i++) {
            if (graph->edges[vertex][i] == 1) {
                return i;
            }
        }
        return -1;
    }

完整代码

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
132
133
134
135
136
#include <stdio.h>

#define MAX_VERTICES 100

typedef struct {
    int vertices[MAX_VERTICES];
    int edges[MAX_VERTICES][MAX_VERTICES];
    int numVertices;
} Graph;

void initGraph(Graph *graph, int numVertices) {
    graph->numVertices = numVertices;
    for (int i = 0; i < numVertices; i++) {
        graph->vertices[i] = 0;
        for (int j = 0; j < numVertices; j++) {
            graph->edges[i][j] = 0;
        }
    }
}

void addEdge(Graph *graph, int src, int dest) {
    graph->edges[src][dest] = 1;
}

void removeEdge(Graph *graph, int src, int dest) {
    graph->edges[src][dest] = 0;
}

int Adjacent(Graph *graph, int src, int dest) {
    return graph->edges[src][dest];
}

void printGraph(Graph *graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        for (int j = 0; j < graph->numVertices; j++) {
            printf("%d ", graph->edges[i][j]);
        }
        printf("\n");
    }
}

void neighbors(Graph *graph, int vertex) {
    for (int i = 0; i < graph->numVertices; i++) {
        if (graph->edges[vertex][i] == 1) {
            printf("Edge: <%d, %d>\n", vertex, i);
        }
    }
}

void insertVertex(Graph *graph, int vertex) {
    graph->vertices[vertex] = 1;
}

void deleteVertex(Graph *graph, int vertex) {
    graph->vertices[vertex] = 0;
    for (int i = 0; i < graph->numVertices; i++) {
        graph->edges[vertex][i] = 0;
        graph->edges[i][vertex] = 0;
    }
}

//void addEdge(Graph *graph, int src, int dest) {
//    graph->edges[src][dest] = 1;
//    // If the graph is undirected, uncomment the following line
//    // graph->edges[dest][src] = 1;
//}
//
//void removeEdge(Graph *graph, int src, int dest) {
//    graph->edges[src][dest] = 0;
//    // If the graph is undirected, uncomment the following line
//    // graph->edges[dest][src] = 0;
//}

int firstNeighbor(Graph *graph, int vertex) {
    for (int i = 0; i < graph->numVertices; i++) {
        if (graph->edges[vertex][i] == 1) {
            return i;
        }
    }
    return -1;
}

int nextNeighbor(Graph *graph, int vertex, int neighbor) {
    for (int i = neighbor + 1; i < graph->numVertices; i++) {
        if (graph->edges[vertex][i] == 1) {
            return i;
        }
    }
    return -1;
}

void setEdgeValue(Graph *graph, int src, int dest, int value) {
    // Assuming edges are represented as weights
    graph->edges[src][dest] = value;
    // If the graph is undirected, uncomment the following line
    // graph->edges[dest][src] = value;
}

int main() {
    Graph graph;
    initGraph(&graph, 5);

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

    printf("Graph:\n");
    printGraph(&graph);

    int x = 0;
    int y = 2;
    if (hasEdge(&graph, x, y)) {
        printf("Edge <%d, %d> or (%d, %d) exists.\n", x, y, x, y);
    } else {
        printf("Edge <%d, %d> or (%d, %d) does not exist.\n", x, y, x, y);
    }

    printf("Neighbors of vertex %d:\n", x);
    neighbors(&graph, x);

    int newVertex = 5;
    insertVertex(&graph, newVertex);
    addEdge(&graph, newVertex, 2);

    printf("Graph after inserting vertex %d:\n", newVertex);
    printGraph(&graph);

    deleteVertex(&graph, 2);

    printf("Graph after deleting vertex %d:\n", 2);
    printGraph(&graph);

    return 0;
}
数据结构 > 第六章 图 > 图的存储及基本操作
图的基本操作
https://lzyjx.github.io.git/2023/05/23/图的基本操作/
作者
六只羊
发布于
2023年5月23日
许可协议