有向图

发表于 分类于 阅读次数： 本文字数： 549 阅读时长 ≈ 2 分钟

Data Structures Experiment #10 - 使用邻接表来完成有向图的存储，并实现相应的辅助函数用于检测图存储的是否正确。

根据要求，不可使用顺序表，故对算法进行了改进。

实现Graph的成员函数

  • Graph(int v);

    构造一个顶点最多为v的图(编号从1到v)

  • ~Graph();

    析构函数，将分配的空间都释放

  • void addedge(int s, int t, int w);

    向图中加入从s到t权重为w的边

  • int getOutDegree(int v);

    获得顶点v的出度

  • int getInDegree(int v);

    获得顶点v的入度

  • int access(int s, int t);

    检查从s到t是否存在一个直接连接到边，如果存在，则返回边的权重，如果不存在，则返回-1

0x01 数据域封装

定义边与顶点结构体。

用邻接表的方式，边需要包括终点和权值，以及用于指向下一条边的指针域。点需要包括入度和出度，以及链接边的头指针。

将顶点创建为图。定义num为点的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
private:
    struct EdgeNode {
        int dest;
        int cost;
        EdgeNode* link;
    };
    struct VertexNode {
        int inDegree, outDegree;
        EdgeNode* firstAdj;
    };

    VertexNode* VexList;
    int num;

0x02 构造函数

为顶点分配内存，注意顶点从1开始计数。

将顶点的度初始化为0，头指针初始化为空。

1
2
3
4
5
6
7
8
9
Graph::Graph(int v){
    num = v;
    VexList = new VertexNode[v + 1];
    for (int i = 1; i <= v; i++) {
        VexList[i].inDegree = 0;
        VexList[i].outDegree = 0;
        VexList[i].firstAdj = NULL;
    }
}

0x03 addedge

用尾插法加边，首先存储边的终点和权值，指针域赋空。

寻找起点链接的最后一条边，将新边链接到它的后面。注意第9行不可写为p = newEdge;，要改变的是头指针，而不是p的指向。

对相应的顶点增加入度或出度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Graph::addedge(int s, int t, int w){
    EdgeNode* newEdge = new EdgeNode;
    newEdge->cost = w;
    newEdge->dest = t;

    newEdge->link = NULL;
    EdgeNode* p = VexList[s].firstAdj;
    if (!p)
        VexList[s].firstAdj = newEdge;
    else {
        while (p->link)
            p = p->link;
        p->link = newEdge;
    }

    VexList[s].outDegree++;
    VexList[t].inDegree++;
}

采用头插法会更加简洁，可以将6～14行替换为

1
2
newEdge->link = VexList[s].firstAdj;
VexList[s].firstAdj = newEdge;

0x04 getInDegree

返回对应顶点的入度。

1
2
3
int Graph::getInDegree(int v){
    return VexList[v].inDegree;
}

0x05 getOutDegree

返回对应顶点的出度。

1
2
3
int Graph::getOutDegree(int v){
    return VexList[v].outDegree;
}

0x06 access

若起点的头指针为空，则说明不存在以此顶点为起点的边。

若起点的头指针不为空，则从起点的头指针开始，遍历所有边，寻找终点满足条件的边并返回其权值。

找不到则返回-1。

1
2
3
4
5
6
7
8
9
10
11
int Graph::access(int s, int t){
    EdgeNode* p = VexList[s].firstAdj;
    if (!p)
        return -1;
    while (p) {
        if (p->dest == t)
            return p->cost;
        p = p->link;
    }
    return -1;
}

0x07 析构函数

遍历并释放内存。

Visual Studio可能会在第5行出现不同的问题导致不可运行。

1
2
3
4
5
6
7
8
9
10
Graph::~Graph(){
    for (int i = 1; i <= num; i++) {
        while (VexList[i].firstAdj) {
            EdgeNode* temp = VexList[i].firstAdj;
            VexList[i].firstAdj = temp->link;
            delete temp;
        }
    }
    delete[] VexList;
}