数据结构邻接矩阵和邻接表图的基本操作的实现代码

邻接矩阵的基本操作实现代码：

#define MAX_VERTICES 100 // 图中最大顶点数
typedef struct {
    int no; // 顶点信息
} VertexType;

typedef struct {
    int edges[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
    int n; // 顶点数
    int e; // 边数
    VertexType vexs[MAX_VERTICES]; // 顶点信息
} MGraph;

// 初始化图
void InitGraph(MGraph &G, int n)
{
    G.n = n;
    G.e = 0;
    for (int i = 0; i < G.n; ++i) {
        for (int j = 0; j < G.n; ++j) {
            G.edges[i][j] = 0;
        }
    }
}

// 添加边
void AddEdge(MGraph &G, int u, int v)
{
    G.edges[u][v] = 1;
    G.edges[v][u] = 1;
    G.e++;
}

// 删除边
void DeleteEdge(MGraph &G, int u, int v)
{
    G.edges[u][v] = 0;
    G.edges[v][u] = 0;
    G.e--;
}

// 判断是否有边
bool HasEdge(MGraph &G, int u, int v)
{
    return G.edges[u][v] == 1;
}

邻接表的基本操作实现代码：

#define MAX_VERTICES 100 // 图中最大顶点数
typedef struct EdgeNode {
    int adjvex; // 邻接点下标
    struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;

typedef struct {
    int no; // 顶点信息
    EdgeNode *firstedge; // 指向第一个邻接点的指针
} VertexNode;

typedef struct {
    VertexNode adjlist[MAX_VERTICES]; // 邻接表
    int n; // 顶点数
    int e; // 边数
} Graph;

// 初始化图
void InitGraph(Graph &G, int n)
{
    G.n = n;
    G.e = 0;
    for (int i = 0; i < G.n; ++i) {
        G.adjlist[i].no = i;
        G.adjlist[i].firstedge = NULL;
    }
}

// 添加边
void AddEdge(Graph &G, int u, int v)
{
    EdgeNode *p = new EdgeNode;
    p->adjvex = v;
    p->next = G.adjlist[u].firstedge;
    G.adjlist[u].firstedge = p;

    EdgeNode *q = new EdgeNode;
    q->adjvex = u;
    q->next = G.adjlist[v].firstedge;
    G.adjlist[v].firstedge = q;

    G.e++;
}

// 删除边
void DeleteEdge(Graph &G, int u, int v)
{
    EdgeNode *p = G.adjlist[u].firstedge;
    EdgeNode *pre = NULL;
    while (p != NULL && p->adjvex != v) {
        pre = p;
        p = p->next;
    }
    if (p != NULL) {
        if (pre == NULL) {
            G.adjlist[u].firstedge = p->next;
        } else {
            pre->next = p->next;
        }
        delete p;
    }

    EdgeNode *q = G.adjlist[v].firstedge;
    EdgeNode *pre_q = NULL;
    while (q != NULL && q->adjvex != u) {
        pre_q = q;
        q = q->next;
    }
    if (q != NULL) {
        if (pre_q == NULL) {
            G.adjlist[v].firstedge = q->next;
        } else {
            pre_q->next = q->next;
        }
        delete q;
    }

    G.e--;
}

// 判断是否有边
bool HasEdge(Graph &G, int u, int v)
{
    EdgeNode *p = G.adjlist[u].firstedge;
    while (p != NULL) {
        if (p->adjvex == v) {
            return true;
        }
        p = p->next;
    }
    return false;
}