图的基本结构和基本操作

最近一直在研究严书风格的图代码,感觉比之前学习算法时用的“前向星”的操作要麻烦一些,不过总算是有点小突破。现在以王道P211练习题的第四题入手,来实现一下图的邻接表以及如何在这个存储结构上跑DFS。

头文件以及一些预定义

#include<iostream>
using namespace std;

#define MaxVertexNum 100
#define VertexType char

图的结构主要包含两个部分:第一个部分是边表,类似链表,主要包含一个结点的编号(不是结点的值),另一个是指向下一个边表结点的指针

图一
typedef struct ArcNode { 
    int adjvex;          //结点的编号
    ArcNode * next;      //指向下一个边表
}ArcNode;

第二个部分是顶点表,顶点表用一个数组AdjList将顶点存起来,其中的每个顶点主要由两部分组成,一个是顶点的值(顶点的编号由vertices数组的下标维护),另一个是指向边表的指针,也就是说,顶点表中存放的每个结点其实就相当于边表的头节点。

//顶点表结点
typedef struct VNode {  
    VertexType data;            //顶点的值
    ArcNode * first;              //指向边表
} VNode, AdjList[MaxVertexNum]; //顶点和顶点表

最后再使用一个结构体存放顶点表和图的顶点数和边数

//图的存储结构
typedef struct {       
    AdjList vertices;    //邻接表,用于存放结点的值,其下标就是结点的编号
    int vertexnum, arcnum; //维护图的顶点数和边的个数
} ALGraph;

这里有一个细节就是使用typedef来定义一个数组,大家可能之前没有用过或者用的很少,这里举个简单的例子,比方说typedef int vector[10]; 这条语句定义了一个元素类型为int,含有10个元素的数组类型vector,之后要使用的时候:vector v1,v2; 这就定义了两个数组v1和v2,每个数组都包含十个int类型的元素。这里定义的AdjList vertices也是如此,它是一个数组,用于存放顶点,数组长度为MaxVertexNum。

LocateVex操作,用于根据顶点的值,找到其编号(在vertices中的位置(下标),在边表中是adjvex)

//找到结点x在顶点表中的位置
int LocateVex(ALGraph & G, VertexType x) {
    for(int i = 0; i < G.vertexnum; i ++) {
        if(x == G.vertices[i].data) 
            return i;
    }
    return -1;
}

之后比较麻烦的就是图的创建了,这块看看我写的注释应该可以看懂

大概流程:输入节点数和边数,然后输入每个结点的值,之后输入边,每输入一条边(两个结点的值)都需要先通过LocateVex找到对应的结点编号,然后使用类似头插法的操作,将这个结点作为边表结点插入到对应的顶点后面,因为是无向图,所以需要两次建边,比如(a, b),需要先 a -> b,再b -> a。

void CreateALGrapha(ALGraph & G) {
    cout << "输入顶点数和边数:";
    cin >> G.vertexnum >> G.arcnum;
    for(int i = 0; i < G.vertexnum; ++i) {
        cout << "输入第" << i + 1 << "个顶点的信息:";
        cin >> G.vertices[i].data;        //将结点的值保存到vertices
        G.vertices[i].first = NULL;       //这里一定要初始化一下
    }

    for(int i = 0; i < G.arcnum; ++i) {
        VertexType e1, e2;
        cout << "输入第" << i + 1 << "条边的顶点:";  //一条边需要两个结点确定
        cin >> e1 >> e2;           
        ArcNode * e = new ArcNode;        //用malloc也行
        if(!e) {
            cout << "内存分配失败:" << endl;
            exit(0);
        }
        
        int vi = LocateVex(G, e1);    //根据值找到编号
        int vj = LocateVex(G, e2);

        //e1和e2之间有一条边,类似头插法将e2的边表结点插到e1的顶点表后
        e -> adjvex = vj;
        e -> next = G.vertices[vi].first;
        G.vertices[vi].first = e;
	
	//无向图需要插入两次,将e1的边表结点插到e2的顶点表后
        e = new ArcNode;
        if(!e) {
            cout << "内存分配失败:" << endl;
            exit(0);
        }
        
        //再将e1的边表插到e2的顶点表
        e -> adjvex = vi;
        e -> next = G.vertices[vj].first;
        G.vertices[vj].first = e;
    }
}

创建好了之后,跑下DFS

DFS每次会以编号为i的结点为起点搜索一个连通块,也就是说,调用dfs的次数,取决于连通块的个数。

DFSTraverse,则是对每个结点都跑一下DFS,因为图可能不连通

bool visited[MaxVertexNum];
//邻接表从起点i开始的深度优先搜索
void DFS(ALGraph G, int i) { 
    ArcNode * p;
    cout << G.vertices[i].data << endl;  
    visited[i] = true;       //标记当前结点为访问过
    p = G.vertices[i].first;   //p指向当前顶点相邻的边表
    while(p) {
        if(!visited[p -> adjvex]) {   //如果还没有访问过,那就访问
            DFS(G, p -> adjvex);
        }
        p = p -> next;     //看看下一个结点
    }
}

//邻接表的全局深度优先搜索
void DFSTraverse(ALGraph G) {
    for(int i = 0; i < G.vertexnum; ++i){   //初始化visit数组为false
        visited[i] = false;
    }

    for(int i = 0; i < G.vertexnum; ++i) {  //不一定是连通图,所以每个结点都要看看
        if(!visited[i])
            DFS(G, i);
    }
}

全部代码

#include<iostream>
using namespace std;

#define MaxVertexNum 100
#define VertexType char

//边表结点
typedef struct ArcNode { 
    int adjvex;          //存储该结点在顶点表中的下标
    ArcNode * next;      //指向下一个边表
}ArcNode;

//顶点表结点
typedef struct VNode {  
    VertexType data;            //顶点信息
    ArcNode * first;             //指向边表
} VNode, AdjList[MaxVertexNum]; //顶点和顶点表

//图的存储结构
typedef struct {       
    AdjList vertices;  //邻接表
    int vertexnum, arcnum; //维护图的顶点数和边的个数
} ALGraph;

//找到结点x在顶点表中的位置
int LocateVex(ALGraph & G, VertexType x) {
    for(int i = 0; i < G.vertexnum; i ++) {
        if(x == G.vertices[i].data) 
            return i;
    }
    return -1;
}

void CreateALGrapha(ALGraph & G) {
    cout << "输入顶点数和边数:";
    cin >> G.vertexnum >> G.arcnum;
    for(int i = 0; i < G.vertexnum; ++i) {
        cout << "输入第" << i + 1 << "个顶点的信息:";
        cin >> G.vertices[i].data;
        G.vertices[i].first = NULL;
    }

    for(int i = 0; i < G.arcnum; ++i) {
        VertexType e1, e2;
        cout << "输入第" << i + 1 << "条边的顶点:";
        cin >> e1 >> e2;
        ArcNode * e = new ArcNode;
        if(!e) {
            cout << "内存分配失败:" << endl;
            exit(0);
        }

        
        int vi = LocateVex(G, e1);
        int vj = LocateVex(G, e2);

        //e1和e2之间有一条边,先用头插法将e2的边表插到e1的顶点表后
        e -> adjvex = vj;
        e -> next = G.vertices[vi].first;
        G.vertices[vi].first = e;

        e = new ArcNode;
        if(!e) {
            cout << "内存分配失败:" << endl;
            exit(0);
        }
        //再将e1的边表插到e2的顶点表
        e -> adjvex = vi;
        e -> next = G.vertices[vj].first;
        G.vertices[vj].first = e;
    }
}

bool visited[MaxVertexNum];
//邻接表从起点i开始的深度优先搜索
void DFS(ALGraph G, int i) {  //DFS每次会搜索一个连通图,也就是说,调用dfs的次数,取决于连通块的个数
    ArcNode * p;
    visited[i] = true;
    cout << G.vertices[i].data << endl;
    p = G.vertices[i].first;
    while(p) {
        if(!visited[p -> adjvex]) {
            DFS(G, p -> adjvex);
        }
        p = p -> next;
    }
}

//邻接表的全局深度优先搜索
void DFSTraverse(ALGraph G) {
    for(int i = 0; i < G.vertexnum; ++i){
        visited[i] = false;
    }

    for(int i = 0; i < G.vertexnum; ++i) {
        if(!visited[i])
            DFS(G, i);
    }
}

int main() {
    ALGraph G;
    CreateALGrapha(G);
    cout << "DFS:" << endl;
    DFSTraverse(G);  
}

/*
以图一为例的输入序列
输入序列
5 7
a b c d e
a b
a e
b c
b d
b e
c d
d e
*/

邻接表to邻接矩阵

其实思路很简单,就是遍历每个顶点的邻接表,因为邻接表结点中存放的正是顶点的相邻结点的编号,在数组的对应位置修改为1,思路很简单,但是前提是要对图的存储结构比较熟悉。

int Matrix[MaxVertexNum][MaxVertexNum];
void Table2Matrix(ALGraph G) {
    for(int i = 0; i < G.vertexnum; ++i) {  //访问每个顶点
        ArcNode * p = G.vertices[i].first;    //遍历顶点的邻接表
        while(p) {
            Matrix[i][p -> adjvex] = 1;          //将对应位置修改为1
            p = p -> next;
        }
    }
}

完整代码

#include<iostream>
using namespace std;

#define MaxVertexNum 100
#define VertexType char

//边表结点
typedef struct ArcNode { 
    int adjvex;          //存储该结点在顶点表中的下标
    ArcNode * next;      //指向下一个边表
}ArcNode;

//顶点表结点
typedef struct VNode {  
    VertexType data;            //顶点信息
    ArcNode * first;             //指向边表
} VNode, AdjList[MaxVertexNum]; //顶点和顶点表

//图的存储结构
typedef struct {       
    AdjList vertices;  //邻接表
    int vertexnum, arcnum; //维护图的顶点数和边的个数
} ALGraph;


//找到结点x在顶点表中的位置
int LocateVex(ALGraph & G, VertexType x) {
    for(int i = 0; i < G.vertexnum; i ++) {
        if(x == G.vertices[i].data) 
            return i;
    }
    return -1;
}

void CreateALGrapha(ALGraph & G) {
    //cout << "输入顶点数和边数:";
    cin >> G.vertexnum >> G.arcnum;
    for(int i = 0; i < G.vertexnum; ++i) {
        //cout << "输入第" << i + 1 << "个顶点的信息:";
        cin >> G.vertices[i].data;
        G.vertices[i].first = NULL;
    }

    for(int i = 0; i < G.arcnum; ++i) {
        VertexType e1, e2;
        //cout << "输入第" << i + 1 << "条边的顶点:";
        cin >> e1 >> e2;
        ArcNode * e = new ArcNode;
        if(!e) {
            cout << "内存分配失败:" << endl;
            exit(0);
        }
        
        int vi = LocateVex(G, e1);
        int vj = LocateVex(G, e2);

        //e1和e2之间有一条边,先用头插法将e2的边表插到e1的顶点表后
        e -> adjvex = vj;
        e -> next = G.vertices[vi].first;
        G.vertices[vi].first = e;
		
        e = new ArcNode;
        if(!e) {
            cout << "内存分配失败:" << endl;
            exit(0);
        }
        
        //再将e1的边表插到e2的顶点表
        e -> adjvex = vi;
        e -> next = G.vertices[vj].first;
        G.vertices[vj].first = e;
    }
}

int Matrix[MaxVertexNum][MaxVertexNum];
void Table2Matrix(ALGraph G) {
    for(int i = 0; i < G.vertexnum; ++i) {
        ArcNode * p = G.vertices[i].first;
        while(p) {
            Matrix[i][p -> adjvex] = 1;
            p = p -> next;
        }
    }
}

int main() {
    ALGraph G;
    CreateALGrapha(G);
    Table2Matrix(G);
    for(int i = 0; i < G.vertexnum; ++i) {
        for(int j = 0; j < G.vertexnum; ++j) {
            cout << Matrix[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

/*
5 7
a b c d e
a b
a e
b c
b d
b e
c d
d e
*/


立志做一名攻城狮