本文共 2260 字，大约阅读时间需要 7 分钟。

问题描述

输入包括三个部分：顶点数、边数，然后是顶点信息和边信息。

• 第一行：输入顶点数和边数。
• 第二行：输入顶点信息，每个顶点用一个字符表示。
• 第三行及以后：依次输入每条边，形式为两个顶点的序号，用空格分隔。

输出包括以下几个部分：

问题分析

需要构建顶点集合和边集合，并判断图是否连通。如果图不连通，还需记录未被遍历的顶点。

代码实现

#include 
   
    using namespace std;const int MaxSize = 20;struct EdgeNode {    int adjvex;    EdgeNode *next;};struct VertexNode {    char vertex;    EdgeNode *firstEdge;};class AlGraph {public:    AlGraph();    ~AlGraph();    void DETraverse(int v);    void BFTraverse(int v);    void LinJie(int v);    void DEnoCross();    void VertexShowing();    int visited[MaxSize];    int EdgeNum, VertexNum;private:    VertexNode adjlist[MaxSize];};void AlGraph::VertexShowing() {    for (int i = 0; i < VertexNum; i++) {        cout << adjlist[i].vertex << " ";    }    cout << endl;}void AlGraph::LinJie(int v) {    for (int i = 0; i < VertexNum; i++) {        visited[i] = 0;    }    EdgeNode *p = NULL;    for (int i = 0; i < VertexNum; i++) {        cout << adjlist[i].vertex << " ";        p = adjlist[i].firstEdge;        while (p != NULL) {            cout << p->adjvex << " ";            p = p->next;        }        cout << endl;    }}void AlGraph::DETraverse(int v) {    EdgeNode *p = NULL;    cout << adjlist[v].vertex << " ";    visited[v] = 1;    p = adjlist[v].firstEdge;    while (p != NULL) {        int j = p->adjvex;        if (visited[j] == 0) {            DETraverse(j);        }        p = p->next;    }}void AlGraph::BFTraverse(int v) {    for (int i = 0; i < VertexNum; i++) {        visited[i] = 0;    }    EdgeNode *p = NULL;    char Q[MaxSize];    int w, j;    int rear = front = -1;    cout << adjlist[v].vertex << " ";    visited[v] = 1;    Q[++rear] = v;    while (rear != front) {        w = Q[++front];        p = adjlist[w].firstEdge;        while (p != NULL) {            j = p->adjvex;            if (visited[j] == 0) {                cout << adjlist[j].vertex << " ";                visited[j] = 1;                Q[++rear] = j;            }            p = p->next;        }    }    front = rear = -1;}int main() {    AlGraph A;    A.VertexShowing();    A.LinJie(0);    A.DEnoCross();    A.BFTraverse(0);}
   

输入样例

5 7A B C D E0 10 20 31 21 32 43 4

输出样例

A B C D EA 3 2 1B 3 2C 4D 4EA D E C BA D C B E