尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


作者:尼采般地抒情

站点信息

文章数目:240
已运行时间:
目录
  1. 一、深度优先搜索算法(Depth-First-Search)
    1. 算法说明
    2. 邻接矩阵的 DFS 代码
    3. 邻接表的 DFS 代码
  2. 二、广度优先搜索算法(Breadth-First-Search)
    1. 算法说明
    2. 邻接矩阵的 BFS 代码
    3. 邻接表的 BFS 代码

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


作者:尼采般地抒情

站点信息

文章数目:240
已运行时间:

image.png

用邻接矩阵和邻接表两种图的存储形式实现DFS、BFS算法,并附例子实现。 总的来说,邻接矩阵比较好处理,没有邻接表处理那么复杂,但是数组永远不能规避的一个缺点就是内存的占用较邻接表高。

一、深度优先搜索算法(Depth-First-Search)

算法说明

访问步骤:

  • 访问顶点 v;
  • 依次从 v 的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和 v 有路径相通的顶点都被访问;
  • 若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。

核心代码就是利用递归,以及标志数组的设定,每次访问数组元素的那一行,对那行链表进行遍历,每遍历一个链表结点,就将“其”所在的那个数组元素“点亮”。如果标志数组里面的所有元素都被访问了,说明遍历完了

深度优先搜索类似于树里面遍历算法当中的先序遍历。

邻接矩阵的 DFS 代码

以这个无向图为例
image.png
image.png

#include<bits/stdc++.h>
using namespace std;

#define MVNum 100
#define MaxInt 32767

typedef char VerTexType;
typedef int ArcType;

/**
 * 邻接矩阵存储形式
 */
typedef struct {
    /* data */
    VerTexType vexs[MVNum]; //顶点表
    ArcType arcs[MVNum][MVNum]; //邻接矩阵
    int vexnum, arcnum; //图的当前顶点和边数
}AMGraph;

/**
 * 确定v在G中的位置,即顶点数组的下标
 */
int LocateVex(AMGraph &G, char v) {
    for (int i = 0; i < G.vexnum;i++) {
        if (v == G.vexs[i]){
            return i;
        }
    }
}

/**
 * 如果创建无向图
 */
void CreateUDN(AMGraph &G) {
    // 采用邻接矩阵表示法,创建无向图G
    cout << "请输入顶点数和边数:" << endl;
    cin >> G.vexnum >> G.arcnum; //输入顶点数和边数
    // 初始化顶点
    for (int i = 0; i < G.vexnum;i++){
        cout << "请输入第" << i << "个顶点值" << endl;
        cin >> G.vexs[i];
    }
    // 初始化邻接矩阵的边的权值为最大值
    for (int i = 0; i < G.vexnum;i++) {
        for (int j = 0; j < G.vexnum;j++) {
            G.arcs[i][j] = 0;
        }
    }
    // 构造邻接矩阵
    for (int k = 0; k < G.arcnum;k++) {
        cout << "请输入每条边所依附的顶点:" << endl;
        char v1, v2;
        int w = 1; //一条边所依附的顶点和权值
        cin >> v1 >> v2;
        int i = LocateVex(G, v1);
        int j = LocateVex(G, v2);
        G.arcs[i][j] = w;
        G.arcs[j][i] = w;
    }
}

/**
 * 打印输出图
 */
void Display(AMGraph &G) {
    for (int i = 0; i < G.vexnum;i++) {
        for (int j = 0; j < G.vexnum;j++) {
            cout << G.arcs[i][j] << " ";
        }
        cout << endl;
    }
}




//----邻接矩阵的DFS遍历----

//访问标志数组,其初值为false
bool visited[MVNum];

/**
 * 图G为邻接矩阵类型,从第v个顶点出发深度优先搜索遍历图G
 */
void DFS_AM(AMGraph &G, int v) {
    //访问第v个顶点,并置访问标志数组相应分量值为true
    cout<<v;
    visited[v] = true;
    //依次检查邻接矩阵v所在的行
    for(int w = 0; w < G.vexnum; w++)
        //G.arcs[v][w] != 0表示w是v的邻接点,!visited[w]表示未访问到
        if((G.arcs[v][w] != 0) && (!visited[w]))
            DFS_AM(G, w);    //递归调用DFS_AM
}

/**
 * 图G的储存类型任意,对非连通图G做深度优先遍历
 */
void DFSTraverse(AMGraph &G) {
    //访问标志数组初始化
    for(int v = 0; v < G.vexnum; v++)
        visited[v] = false;
    //循环调用DFS
    for(int v = 0; v < G.vexnum; v++)
        if(!visited[v])
            DFS_AM(G, v); //对尚未访问的顶点调用DFS
}




int main() {
    AMGraph test;
    CreateUDN(test);
    Display(test);
    DFSTraverse(test);
    return 0;
}

邻接表的 DFS 代码

举之前上课的一张 PPT 例子(元素插入为后插法)
image.png
结果
image.png

#include <bits/stdc++.h>
using namespace std;

#define MVNum 100
#define MaxInt 32767

typedef char VerTexType;
typedef int OtherInfo;

/**
 * 邻接表存储
 */

/**
 * 存储结构
 */
typedef struct ArcNode {  //边结点
    int adjvex;  //该边所指向的结点的位置
    struct ArcNode *nextarc; //指向下一条边的指针
    OtherInfo info;   //和边相关的其他信息
}ArcNode;

typedef struct VNode {   //顶点信息
    VerTexType data;  //数据域,存放顶点vi的名称或其他有关信息
    ArcNode *firstarc;  //指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum]; //AdjList表示邻接表的类型

typedef struct {
    AdjList vertices;
    int vexnum, arcnum; //图当前的顶点数和边数
}ALGragh; //邻接表(Adjacency List)


/**
 * 找到v顶点在图的顶点数组中的位置
 */
int LocateVex(ALGragh &G, char v) {
    for (int i = 0; i < G.vexnum;i++) {
        if (v == G.vertices[i].data) {
            return i;
        }
    }
}

/**
 * 邻接表创建无向图
 */
void CreateUDG(ALGragh &G) {
    cout << "请输入顶点数和边数:" << endl;
    cin >> G.vexnum >> G.arcnum; // 邻接表的顶点数和边数
    // 初始化顶点数组
    for (int i = 0; i < G.vexnum;i++) {
        cin >> G.vertices[i].data; // 初始化顶点数组里面的结点data
        G.vertices[i].firstarc = NULL; // 初始化顶点数组里面的结点next域
    }
    // 初始化所有的边
    for (int k = 0; k < G.arcnum;k++) {
        char v1, v2;
        cout << "请输入每条边所依附的顶点:" << endl;
        cin >> v1 >> v2;
        int i = LocateVex(G, v1); // 找到v1在顶点数组的下标
        int j = LocateVex(G, v2); // 找到v2在顶点数组的下标
        // 下面建立p1和p2是因为无向图,如果是有向图就没必要了只需要p1
        // 前插
        ArcNode *p1 = new ArcNode;
        p1->adjvex = j;
        p1->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p1;
        ArcNode *p2 = new ArcNode;
        p2->adjvex = i;
        p2->nextarc = G.vertices[j].firstarc;
        G.vertices[j].firstarc = p2;
    }
}

/**
 * 打印输出图
 */
void Display(ALGragh &G) {
    for (int i = 0; i < G.vexnum;i++) {
        cout << "结点" << i << ":";
        // 复制选中的节点数组中的结点
        VNode p;
        p = G.vertices[i];
        if (p.firstarc != NULL){
            ArcNode *temp;
            temp = G.vertices[i].firstarc;
            while (temp != NULL) {
                cout << temp->adjvex<<" ";
                temp = temp->nextarc;
            }
            cout << "\n";
        }
    }
}



//----邻接表的DFS遍历----
bool visited[MVNum];                                                    //访问标志数组,其初值为false

void DFS_AL(ALGragh G, int v)
{//图G为邻接表类型,从从第v个顶点出发深度优先搜索遍历图G
    cout<<v;                                                            //访问第v个顶点,并置访问标志数组相应分量值为true
    visited[v] = true;
    ArcNode *p;
    p = G.vertices[v].firstarc;                                         //p指向v的边链表的第一个边结点
    while(p != NULL)
    {
       int w = p->adjvex;                                               //w是v的邻接点
        if(!visited[w])                                                 //如果w未访问
            DFS_AL(G, w);                                               //递归调用DFS_AL
        p = p->nextarc;                                                 //p指向下一个结点
    }
}

void DFSTraverse(ALGragh G)
{//图G的储存类型任意,对非连通图G做深度优先遍历
    for(int v = 0; v < G.vexnum; v++)                                   //访问标志数组初始化
        visited[v] = false;
    for(int v = 0; v < G.vexnum; v++)                                   //循环调用DFS
        if(!visited[v])
            DFS_AL(G, v);                                                  //对尚未访问的顶点调用DFS
}


int main() {
    ALGragh test;
    CreateUDG(test);
    // Display(test);
    DFSTraverse(test);
}

二、广度优先搜索算法(Breadth-First-Search)

算法说明

从某个顶点 V0 出发,并在访问此顶点之后依次访问 V0 的所有未被访问过的邻接点,之后按这些顶点被访问的先后次序依次访问它们的邻接点,直至图中所有和 V0 有路径相通的顶点都被访问到。
若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

邻接矩阵的 BFS 代码

还是这个例子
image.png
image.png

#include<bits/stdc++.h>
using namespace std;

#define MVNum 100
#define MaxInt 32767

typedef char VerTexType;
typedef int ArcType;

/**
 * 邻接矩阵的bfs代码
 */
typedef struct {
    /* data */
    VerTexType vexs[MVNum]; //顶点表
    ArcType arcs[MVNum][MVNum]; //邻接矩阵
    int vexnum, arcnum; //图的当前顶点和边数
}AMGraph;

/**
 * 确定v在G中的位置,即顶点数组的下标
 */
int LocateVex(AMGraph &G, char v) {
    for (int i = 0; i < G.vexnum;i++) {
        if (v == G.vexs[i]){
            return i;
        }
    }
}

/**
 * 创建无向网
 * 如果创建无向图
 */
void CreateUDN(AMGraph &G) {
    // 采用邻接矩阵表示法,创建无向图G
    cout << "请输入顶点数和边数:" << endl;
    cin >> G.vexnum >> G.arcnum; //输入顶点数和边数
    // 初始化顶点
    for (int i = 0; i < G.vexnum;i++){
        cout << "请输入第" << i << "个顶点值" << endl;
        cin >> G.vexs[i];
    }
    // 初始化邻接矩阵的边的权值为最大值
    for (int i = 0; i < G.vexnum;i++) {
        for (int j = 0; j < G.vexnum;j++) {
            G.arcs[i][j] = 0;
        }
    }
    // 构造邻接矩阵
    for (int k = 0; k < G.arcnum;k++) {
        cout << "请输入每条边所依附的顶点:" << endl;
        char v1, v2;
        int w = 1; //一条边所依附的顶点和权值
        cin >> v1 >> v2;
        int i = LocateVex(G, v1);
        int j = LocateVex(G, v2);
        G.arcs[i][j] = w;
        G.arcs[j][i] = w;
    }
}

/**
 * 打印输出图
 */
void Display(AMGraph &G) {
    for (int i = 0; i < G.vexnum;i++) {
        for (int j = 0; j < G.vexnum;j++) {
            cout << G.arcs[i][j] << " ";
        }
        cout << endl;
    }
}




//----邻接矩阵的BFS遍历----

bool visited[MVNum];

void BFS_AM(AMGraph G, int v)
{//按广度优先非递归遍历连通图G
    cout<<v;
    visited[v] = true; //访问第v个顶点,并置访问标志数组相应分量值为true
    queue<int> Q;
    Q.push(v);
    while(!Q.empty())
    {
        int u = Q.front(); //队头元素出队并置为u
        Q.pop();
        for(int w = 0; w < G.vexnum; w++)
            if((G.arcs[u][w] != 0) && (!visited[w])) //G.arcs[v][w] != 0表示w是v的邻接点,!visited[w]表示未访问到                                            //w为u的尚未访问的邻接顶点
            {
                cout<<w;
                visited[w] = true; //访问w,并置访问标志数组相应分量值为true
                Q.push(w); //w进队
            }
    }
}

void BFSTraverse(AMGraph &G) {
    //访问标志数组初始化
    for(int v = 0; v < G.vexnum; v++)
        visited[v] = false;
    //循环调用BFS
    for(int v = 0; v < G.vexnum; v++)
        if(!visited[v])
            BFS_AM(G, v); //对尚未访问的顶点调用BFS
}


int main() {
    AMGraph test;
    CreateUDN(test);
    Display(test);
    // DFSTraverse(test);
    BFSTraverse(test);
    return 0;
}

邻接表的 BFS 代码

还用和 DFS 一样的例子
image.pngimage.png

#include <bits/stdc++.h>
using namespace std;

#define MVNum 100
#define MaxInt 32767

typedef char VerTexType;
typedef int OtherInfo;

/**
 * 邻接表的bfs代码
 */

/**
 * 存储结构
 */
typedef struct ArcNode {  //边结点
    int adjvex;  //该边所指向的结点的位置
    struct ArcNode *nextarc; //指向下一条边的指针
    OtherInfo info;   //和边相关的其他信息
}ArcNode;

typedef struct VNode {   //顶点信息
    VerTexType data;  //数据域,存放顶点vi的名称或其他有关信息
    ArcNode *firstarc;  //指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum]; //AdjList表示邻接表的类型

typedef struct {
    AdjList vertices;
    int vexnum, arcnum; //图当前的顶点数和边数
}ALGraph; //邻接表(Adjacency List)


/**
 * 找到v顶点在图的顶点数组中的位置
 */
int LocateVex(ALGraph &G, char v) {
    for (int i = 0; i < G.vexnum;i++) {
        if (v == G.vertices[i].data) {
            return i;
        }
    }
}

/**
 * 邻接表创建无向图
 */
void CreateUDG(ALGraph &G) {
    cout << "请输入顶点数和边数:" << endl;
    cin >> G.vexnum >> G.arcnum; // 邻接表的顶点数和边数
    // 初始化顶点数组
    for (int i = 0; i < G.vexnum;i++) {
        cin >> G.vertices[i].data; // 初始化顶点数组里面的结点data
        G.vertices[i].firstarc = NULL; // 初始化顶点数组里面的结点next域
    }
    // 初始化所有的边
    for (int k = 0; k < G.arcnum;k++) {
        char v1, v2;
        cout << "请输入每条边所依附的顶点:" << endl;
        cin >> v1 >> v2;
        int i = LocateVex(G, v1); // 找到v1在顶点数组的下标
        int j = LocateVex(G, v2); // 找到v2在顶点数组的下标
        // 下面建立p1和p2是因为无向图,如果是有向图就没必要了只需要p1
        // 前插
        ArcNode *p1 = new ArcNode;
        p1->adjvex = j;
        p1->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p1;
        ArcNode *p2 = new ArcNode;
        p2->adjvex = i;
        p2->nextarc = G.vertices[j].firstarc;
        G.vertices[j].firstarc = p2;
    }
}

/**
 * 打印输出图
 */
void Display(ALGraph &G) {
    for (int i = 0; i < G.vexnum;i++) {
        cout << "结点" << i << ":";
        // 复制选中的节点数组中的结点
        VNode p;
        p = G.vertices[i];
        if (p.firstarc != NULL){
            ArcNode *temp;
            temp = G.vertices[i].firstarc;
            while (temp != NULL) {
                cout << temp->adjvex<<" ";
                temp = temp->nextarc;
            }
            cout << "\n";
        }
    }
}



//----邻接表的BFS遍历----

bool visited[MVNum];

int FirstAdjvex(ALGraph& G, int u)
{
    int w = G.vertices[u].firstarc->adjvex;
    return w;
}
int NextAdjVex(ALGraph& G, int u, int w)
{
    ArcNode *temp = G.vertices[u].firstarc;
    while (temp->adjvex != w)
    {
        temp = temp->nextarc;
    }
    if (temp->nextarc)
        return temp->nextarc->adjvex;
    else
        return -1;
    delete temp;
}
void BFS_AL(ALGraph& G, int v){
    cout << v;
    visited[v] = true;
    queue<int> Q;
    Q.push(v);
    int u = v;
    while (!Q.empty()){
        u = Q.front();
        Q.pop();
        for (int w = FirstAdjvex(G, u); w >= 0; w = NextAdjVex(G, u, w)){
            if (!visited[w]){
                cout <<w;
                visited[w] = true;
                Q.push(w);
            }
        }
    }
}

void BFSTraverse(ALGraph &G) {
    //访问标志数组初始化
    for(int v = 0; v < G.vexnum; v++)
        visited[v] = false;
    //循环调用BFS
    for(int v = 0; v < G.vexnum; v++)
        if(!visited[v])
            BFS_AL(G, v); //对尚未访问的顶点调用BFS
}

int main() {
    ALGraph test;
    CreateUDG(test);
    Display(test);
    BFSTraverse(test);
}
【插眼】为啥我写的一个函数不需要队列也可以???直接将顶点数组的一个元素后面接的链表遍历不就好了,然后再遍历标志数组元素值部位true的不就好了。。。为啥要压队列呀? 莫不是哪里有隐藏的bug,插个眼!!!

【拔眼】这样是一种特殊情况,只适合图的各个结点是按照层次标号的,并且放入标志数组也是按照顺序放入的……

插眼代码如下:

void BFS_AL(ALGraph &G, int v)
{//按广度优先非递归遍历连通图G
    cout<<v;
    visited[v] = true;    //访问第v个顶点,并置访问标志数组相应分量值为true
    ArcNode *p;
    p = G.vertices[v].firstarc;
    if (p != NULL) {
        while(p != NULL) {
            if (!visited[p->adjvex]){
                cout << p->adjvex;
            }
            visited[p->adjvex] = true;
            p = p->nextarc;
        }
    }
}

博客内容遵循: 署名-非商业性使用-禁止演绎 4.0 国际(CC BY-NC-ND 4.0)

本文永久链接: https://www.wztlink1013.com/blog/ztiag3/

编辑: 部署: 订阅:

评论区

Twikoo 转换 utterances

最新评论

Loading...