用C语言基于邻接矩阵存储结构实现有向网络的典型操作(初始化、销毁、增加顶点、删除顶点、增加弧、删除弧、查 找一个顶点、修改一个顶点、查找一个弧、修改一个弧、判空、判满、图中顶点个数、图中的弧个数、深度优先遍历、 广度优先遍历),测试和调试程序。
时间: 2023-09-16 21:09:08 浏览: 106
以下是基于邻接矩阵存储结构实现有向图的典型操作的C语言代码:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
typedef struct {
int vertices[MAX_VERTICES]; // 存储顶点
int arcs[MAX_VERTICES][MAX_VERTICES]; // 存储边
int vertexCount; // 顶点个数
int arcCount; // 边个数
} DirectedGraph;
// 初始化有向图
void initGraph(DirectedGraph* graph) {
graph->vertexCount = 0;
graph->arcCount = 0;
int i, j;
for (i = 0; i < MAX_VERTICES; i++) {
graph->vertices[i] = 0;
for (j = 0; j < MAX_VERTICES; j++) {
graph->arcs[i][j] = 0;
}
}
}
// 销毁有向图
void destroyGraph(DirectedGraph* graph) {
graph->vertexCount = 0;
graph->arcCount = 0;
}
// 增加顶点
bool addVertex(DirectedGraph* graph, int vertex) {
if (graph->vertexCount >= MAX_VERTICES) {
return false;
}
graph->vertices[graph->vertexCount++] = vertex;
return true;
}
// 删除顶点
bool removeVertex(DirectedGraph* graph, int vertex) {
int i, j;
for (i = 0; i < graph->vertexCount; i++) {
if (graph->vertices[i] == vertex) {
for (j = i; j < graph->vertexCount - 1; j++) {
graph->vertices[j] = graph->vertices[j + 1];
}
graph->vertexCount--;
for (j = 0; j < graph->vertexCount; j++) {
graph->arcs[i][j] = graph->arcs[i + 1][j];
}
for (j = 0; j < graph->vertexCount; j++) {
graph->arcs[j][i] = graph->arcs[j][i + 1];
}
return true;
}
}
return false;
}
// 增加弧
bool addArc(DirectedGraph* graph, int startVertex, int endVertex) {
int i, startIndex = -1, endIndex = -1;
for (i = 0; i < graph->vertexCount; i++) {
if (graph->vertices[i] == startVertex) {
startIndex = i;
}
if (graph->vertices[i] == endVertex) {
endIndex = i;
}
}
if (startIndex != -1 && endIndex != -1) {
if (graph->arcs[startIndex][endIndex] == 0) {
graph->arcs[startIndex][endIndex] = 1;
graph->arcCount++;
return true;
}
}
return false;
}
// 删除弧
bool removeArc(DirectedGraph* graph, int startVertex, int endVertex) {
int i, startIndex = -1, endIndex = -1;
for (i = 0; i < graph->vertexCount; i++) {
if (graph->vertices[i] == startVertex) {
startIndex = i;
}
if (graph->vertices[i] == endVertex) {
endIndex = i;
}
}
if (startIndex != -1 && endIndex != -1) {
if (graph->arcs[startIndex][endIndex] == 1) {
graph->arcs[startIndex][endIndex] = 0;
graph->arcCount--;
return true;
}
}
return false;
}
// 查找顶点
int findVertex(DirectedGraph* graph, int vertex) {
int i;
for (i = 0; i < graph->vertexCount; i++) {
if (graph->vertices[i] == vertex) {
return i;
}
}
return -1;
}
// 修改顶点
bool modifyVertex(DirectedGraph* graph, int oldVertex, int newVertex) {
int index = findVertex(graph, oldVertex);
if (index != -1) {
graph->vertices[index] = newVertex;
return true;
}
return false;
}
// 查找弧
bool findArc(DirectedGraph* graph, int startVertex, int endVertex) {
int startIndex = findVertex(graph, startVertex);
int endIndex = findVertex(graph, endVertex);
if (startIndex != -1 && endIndex != -1) {
if (graph->arcs[startIndex][endIndex] == 1) {
return true;
}
}
return false;
}
// 修改弧
bool modifyArc(DirectedGraph* graph, int startVertex, int endVertex, int newArc) {
int startIndex = findVertex(graph, startVertex);
int endIndex = findVertex(graph, endVertex);
if (startIndex != -1 && endIndex != -1) {
graph->arcs[startIndex][endIndex] = newArc;
return true;
}
return false;
}
// 判断图是否为空
bool isEmpty(DirectedGraph* graph) {
return graph->vertexCount == 0;
}
// 判断图是否已满
bool isFull(DirectedGraph* graph) {
return graph->vertexCount == MAX_VERTICES;
}
// 获取图中顶点个数
int getVertexCount(DirectedGraph* graph) {
return graph->vertexCount;
}
阅读全文