图的基本操作与实现，要求用邻接表存储结构，实现对图11-3所示的有向带权网络G的操作。 ⑴ 输入含n（1≤n≤100）个顶点（用字符表示顶点）和e条边； ⑵ 求每个顶点的出度和入度，输出结果； ⑶ 指定任意顶点x为初始顶点，对图G作DFS遍历，输出DFS顶点序列； ⑷ 指定任意顶点x为初始顶点，对图G作BFS遍历，输出BFS顶点序列； ⑸ 输入顶点x，查找图G：若存在含x的顶点，则删除该结点及与之相关联的边，并作DFS遍历；否则输出信息“无x”； ⑹ 判断图G是否是连通图，输出信息“YES”/“NO”； ⑺ 根据图G的邻接表创建图G的邻接矩阵，即复制图G。 ⑻ 找出该图的一棵最小生成树。

邻接表存储结构定义：

typedef char VertexType; // 顶点类型
typedef int EdgeType; // 边权值类型

// 边表结点
typedef struct EdgeNode {
    int adjvex; // 邻接点编号
    EdgeType weight; // 边权值
    struct EdgeNode *next; // 指向下一个邻接点
} EdgeNode;

// 顶点表结点
typedef struct VertexNode {
    VertexType data; // 顶点数据
    EdgeNode *firstEdge; // 指向第一个邻接点
} VertexNode, AdjList[MAXVEX];

// 邻接表存储结构
typedef struct {
    AdjList adjList; // 邻接表
    int numVertexes, numEdges; // 顶点数和边数
} GraphAdjList;

辅助函数：

// 返回顶点在邻接表中的位置
int LocateVex(GraphAdjList G, VertexType v) {
    for (int i = 0; i < G.numVertexes; i++) {
        if (G.adjList[i].data == v) {
            return i;
        }
    }
    return -1;
}

// 深度优先搜索遍历
void DFS(GraphAdjList G, int i, bool visited[]) {
    visited[i] = true;
    printf("%c", G.adjList[i].data);
    EdgeNode *p = G.adjList[i].firstEdge;
    while (p) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

// 广度优先搜索遍历
void BFS(GraphAdjList G, int i, bool visited[]) {
    int queue[MAXVEX], front = 0, rear = 0;
    printf("%c", G.adjList[i].data);
    visited[i] = true;
    queue[rear++] = i;
    while (front != rear) {
        int j = queue[front++];
        EdgeNode *p = G.adjList[j].firstEdge;
        while (p) {
            if (!visited[p->adjvex]) {
                printf("%c", G.adjList[p->adjvex].data);
                visited[p->adjvex] = true;
                queue[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

// 删除结点及其相关联的边
void DeleteVex(GraphAdjList *G, VertexType v) {
    int i = LocateVex(*G, v);
    if (i == -1) {
        printf("无%c\n", v);
        return;
    }
    EdgeNode *p = G->adjList[i].firstEdge;
    while (p) {
        int j = p->adjvex;
        EdgeNode *q = G->adjList[j].firstEdge, *r = NULL;
        while (q) {
            if (q->adjvex == i) {
                if (r == NULL) {
                    G->adjList[j].firstEdge = q->next;
                } else {
                    r->next = q->next;
                }
                free(q);
                G->numEdges--;
                break;
            }
            r = q;
            q = q->next;
        }
        p = p->next;
    }
    G->numVertexes--;
    for (int j = i; j < G->numVertexes; j++) {
        G->adjList[j] = G->adjList[j+1];
    }
    for (int j = 0; j < G->numVertexes; j++) {
        EdgeNode *p = G->adjList[j].firstEdge;
        while (p) {
            if (p->adjvex > i) {
                p->adjvex--;
            }
            p = p->next;
        }
    }
}

// 连通性检查
bool DFS2(GraphAdjList G, int i, bool visited[]) {
    visited[i] = true;
    EdgeNode *p = G.adjList[i].firstEdge;
    while (p) {
        if (!visited[p->adjvex]) {
            DFS2(G, p->adjvex, visited);
        }
        p = p->next;
    }
    return true;
}

bool IsConnected(GraphAdjList G) {
    bool visited[MAXVEX] = { false };
    DFS2(G, 0, visited);
    for (int i = 0; i < G.numVertexes; i++) {
        if (!visited[i]) {
            return false;
        }
    }
    return true;
}

// 边的最小堆
typedef struct {
    int u, v; // 边的两个顶点
    EdgeType w; // 边的权值
} Edge;

typedef struct {
    Edge data[MAXEDGE];
    int size;
} MinHeap;

void Insert(MinHeap *H, Edge e) {
    H->data[++H->size] = e;
    int i = H->size;
    while (i > 1 && H->data[i].w < H->data[i/2].w) {
        Edge tmp = H->data[i];
        H->data[i] = H->data[i/2];
        H->data[i/2] = tmp;
        i /= 2;
    }
}

Edge Delete(MinHeap *H) {
    Edge ret = H->data[1];
    H->data[1] = H->data[H->size--];
    int i = 1;
    while (i*2 <= H->size) {
        int child = i*2;
        if (child < H->size && H->data[child+1].w < H->data[child].w) {
            child++;
        }
        if (H->data[child].w < H->data[i].w) {
            Edge tmp = H->data[child];
            H->data[child] = H->data[i];
            H->data[i] = tmp;
            i = child;
        } else {
            break;
        }
    }
    return ret;
}

操作实现：

⑴ 输入含n（1≤n≤100）个顶点（用字符表示顶点）和e条边；

void CreateGraph(GraphAdjList *G) {
    printf("输入顶点数和边数：");
    scanf("%d%d", &G->numVertexes, &G->numEdges);
    getchar(); // 读取多余的换行符
    printf("输入顶点：");
    for (int i = 0; i < G->numVertexes; i++) {
        scanf("%c", &G->adjList[i].data);
        G->adjList[i].firstEdge = NULL;
    }
    getchar(); // 读取多余的换行符
    printf("输入边（<vi,vj,w>）：");
    for (int k = 0; k < G->numEdges; k++) {
        VertexType vi, vj;
        EdgeType w;
        scanf("<%c,%c,%d>", &vi, &vj, &w);
        getchar(); // 读取多余的换行符
        int i = LocateVex(*G, vi), j = LocateVex(*G, vj);
        EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->weight = w;
        e->next = G->adjList[i].firstEdge;
        G->adjList[i].firstEdge = e;
    }
}

⑵ 求每个顶点的出度和入度，输出结果；

void PrintInAndOutDegree(GraphAdjList G) {
    int inDegree[MAXVEX] = { 0 }, outDegree[MAXVEX] = { 0 };
    for (int i = 0; i < G.numVertexes; i++) {
        EdgeNode *p = G.adjList[i].firstEdge;
        while (p) {
            outDegree[i]++;
            inDegree[p->adjvex]++;
            p = p->next;
        }
    }
    printf("顶点 出度 入度\n");
    for (int i = 0; i < G.numVertexes; i++) {
        printf("%c %d %d\n", G.adjList[i].data, outDegree[i], inDegree[i]);
    }
}

⑶ 指定任意顶点x为初始顶点，对图G作DFS遍历，输出DFS顶点序列；

void DFSTraverse(GraphAdjList G, VertexType v) {
    bool visited[MAXVEX] = { false };
    int i = LocateVex(G, v);
    DFS(G, i, visited);
}

⑷ 指定任意顶点x为初始顶点，对图G作BFS遍历，输出BFS顶点序列；

void BFSTraverse(GraphAdjList G, VertexType v) {
    bool visited[MAXVEX] = { false };
    int i = LocateVex(G, v);
    BFS(G, i, visited);
}

⑸ 输入顶点x，查找图G：若存在含x的顶点，则删除该结点及与之相关联的边，并作DFS遍历；否则输出信息“无x”；

void DeleteVexAndDFS(GraphAdjList *G, VertexType v) {
    DeleteVex(G, v);
    bool visited[MAXVEX] = { false };
    if (LocateVex(*G, v) != -1) {
        printf("DFS遍历序列：");
        int i = 0;
        while (visited[i]) i++;
        DFS(*G, i, visited);
    }
}

⑹ 判断图G是否是连通图，输出信息“YES”/“NO”；

void PrintConnected(GraphAdjList G) {
    if (IsConnected(G)) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }
}

⑺ 根据图G的邻接表创建图G的邻接矩阵，即复制图G。

void CreateMGraph(GraphAdjList G, EdgeType (*matrix)[MAXVEX]) {
    for (int i = 0; i < G.numVertexes; i++) {
        for (int j = 0; j < G.numVertexes; j++) {
            matrix[i][j] = INFINITY;
        }
        EdgeNode *p = G.adjList[i].firstEdge;
        while (p) {
            matrix[i][p->adjvex] = p->weight;
            p = p->next;
        }
    }
}

⑻ 找出该图的一棵最小生成树。

void MiniSpanTree_Kruskal(GraphAdjList G) {
    Edge edges[MAXEDGE];
    int k = 0;
    for (int i = 0; i < G.numVertexes; i++) {
        EdgeNode *p = G.adjList[i].firstEdge;
        while (p) {
            if (i < p->adjvex) {
                edges[k].u = i;
                edges[k].v = p->adjvex;
                edges[k].w = p->weight;
                k++;
            }
            p = p->next;
        }
    }
    MinHeap H = { 0 };
    for (int i = 0; i < k; i++) {
        Insert(&H, edges[i]);
    }
    int parent[MAXVEX];
    for (int i = 0; i < G.numVertexes; i++) {
        parent[i] = i;
    }
    int count = 0;
    while (count < G.numVertexes-1 && H.size > 0) {
        Edge e = Delete(&H);
        int u = e.u, v = e.v;
        while (parent[u] != u) {
            u = parent[u];
        }
        while (parent[v] != v) {
            v = parent[v];
        }
        if (u != v) {
            printf("%c-%c ", G.adjList[e.u].data, G.adjList[e.v].data);
            parent[v] = u;
            count++;
        }
    }
}

完整代码：