图的基本操作c语言
时间: 2023-09-28 09:03:48 浏览: 38
以下是图的基本操作C语言实现的示例代码:
定义结构体表示节点:
```
#define MAX_VERTEX_NUM 20
typedef struct ArcNode {
int adjvex;
struct ArcNode *nextarc;
} ArcNode;
typedef struct {
char data;
ArcNode *firstarc;
} VNode;
typedef struct {
VNode vertex[MAX_VERTEX_NUM];
int vexnum, arcnum;
} Graph;
```
创建图:
```
void createGraph(Graph *graph) {
// 初始化节点和边数
graph->vexnum = 0;
graph->arcnum = 0;
// 输入节点数和边数
printf("请输入节点数和边数:");
scanf("%d %d", &graph->vexnum, &graph->arcnum);
// 输入节点数据
for (int i = 0; i < graph->vexnum; i++) {
printf("请输入第%d个节点的数据:", i + 1);
scanf(" %c", &graph->vertex[i].data);
graph->vertex[i].firstarc = NULL;
}
// 输入边数据
for (int i = 0; i < graph->arcnum; i++) {
int v1, v2;
printf("请输入第%d条边的两个节点的编号:", i + 1);
scanf("%d %d", &v1, &v2);
// 创建邻接表节点
ArcNode *node1 = (ArcNode*)malloc(sizeof(ArcNode));
node1->adjvex = v2;
node1->nextarc = graph->vertex[v1].firstarc;
graph->vertex[v1].firstarc = node1;
ArcNode *node2 = (ArcNode*)malloc(sizeof(ArcNode));
node2->adjvex = v1;
node2->nextarc = graph->vertex[v2].firstarc;
graph->vertex[v2].firstarc = node2;
}
}
```
深度优先遍历:
```
void DFS(Graph *graph, int v, int visited[]) {
visited[v] = 1;
printf("%c ", graph->vertex[v].data);
ArcNode *p = graph->vertex[v].firstarc;
while (p) {
if (!visited[p->adjvex]) {
DFS(graph, p->adjvex, visited);
}
p = p->nextarc;
}
}
void DFSTraverse(Graph *graph) {
int visited[MAX_VERTEX_NUM] = {0};
for (int i = 0; i < graph->vexnum; i++) {
if (!visited[i]) {
DFS(graph, i, visited);
}
}
}
```
广度优先遍历:
```
void BFSTraverse(Graph *graph) {
int visited[MAX_VERTEX_NUM] = {0};
Queue *queue = createQueue();
for (int i = 0; i < graph->vexnum; i++) {
if (!visited[i]) {
visited[i] = 1;
printf("%c ", graph->vertex[i].data);
enQueue(queue, i);
while (!isQueueEmpty(queue)) {
int v = deQueue(queue);
ArcNode *p = graph->vertex[v].firstarc;
while (p) {
if (!visited[p->adjvex]) {
visited[p->adjvex] = 1;
printf("%c ", graph->vertex[p->adjvex].data);
enQueue(queue, p->adjvex);
}
p = p->nextarc;
}
}
}
}
}
```