<数据结构>图的构建与基本遍历方法

时间：2024-10-13 16:34:02

建立一个图

核心问题

  1. 怎么表示结点
  2. 怎么表示边以及边权

邻接矩阵

用二维数组表示一张图：数组的下标表示结点，数组的值表示边权。

如 G[1][2] = 11 表示结点1和2之间有条边且边权为2。

如要表示结点1和3之间没有边，可以写作： G[1][3] = 0/-1/INF。（INF是一个很大的数，一般取100,000,000)

const MAXV = 100; //最大顶点数

int n, G[MAXV][MAXV] = 0;   //n为顶点数,MAXV为最大顶点数

int main(){

	int n,m; //结点数和边数

	int u,v,weight; //边的两端点和边权

	scanf("%d%d", &n,&m);

	for(int i = 0; i < m; i++){

		scanf("%d%d%d", &u,&v,&weight);

		G[u][v] = weight;

		G[v][u] = weight； //如果是无向图

	}

}

邻接表

用一维数组的下标表示结点，且数组的每个元素是一个指针，指向一条链表。故每个结点对应一条链表。

每个结点对应链表中存放着它的邻接点和边权，这样就表示出了每个结点所连接的边。

<数据结构>图的构建与基本遍历方法

/*直接应用stl库中的vector实现*/

/*可以直接把vector理解为变长数组，这样免去了链表操作的麻烦*/

#include<stdio.h>

#include<vector>

using namespace std; //调用vector

const int MAXV = 100;//最大结点数

struct Node{

	int v; //边的终点编号

	int w; //边权

	Node(int _v, int _w) : v(_v), w(_w) {} //构造函数

};

vector<Node> Adj[MAXV]; //用邻接表表示的图

int n;

int main(){

	int n,m; //结点数和边数

	int u,v,w; //边的两端点和边权

	scanf("%d%d", &n,&m);

	for(int i = 0; i < m; i++){

		scanf("%d%d%d", &u,&v,&w);

		Adj[u].push_back(Node(v,w));  //利用构造函数，省去了构建临时结点的麻烦

		Adj[v].push_back(Node(u,w));  //如果是无向图

	}

}

深度优先遍历（DFS）

DFS就是一路走到黑

具体步骤：

第一部分：给定结点u,遍历u所在的连通块的所有结点

  1. 访问当前结点u
  2. 遍历u的所有邻接点Vi
  3. 如果邻接点Vi还未被访问过，对Vi重复1.2步骤

第二部分：对图G所有结点进行第一部分的操作，即遍历了图的所有连通分量

伪代码

注： vis：标记数组，如果顶点i已被访问，则vis[i] == true。 初始化为 false

DFS(u){ //访问顶点u

    vis[u] = true; //设置u已被访问

    for(从u出发能到达的所有顶点v){ //枚举从u出发可以到达的所有顶点v

        if vis[v] == false   //如果v未被访问

            DFS(v);  //递归访问v

    }

}

DFSTrave(G){      //遍历图G

    for(G的所有顶点u)  //对G的所有顶点u

        if vis[u] == flase;  //如果u未被访问

            DFS(u);    //访问u所在的连通块

}

邻接矩阵实现

#include<stdio.h>

const int MAXV = 100; //最大顶点数

const int INF  = 100000000; //设INF为一个很大的数

int n, G[MAXV][MAXV];     //n为顶点数，MAXV为最大顶点数

bool vis[MAXV] = {false}; //标记数组，如果顶点i已被访问，则vis[i] == true。

void DFS(int u, int depth){ //u为当前访问的节点标号，depth为深度

    vis[u] = true;  // 设置u已被访问

    //如果需要对u进行一些操作，可以在这里进行

    //线面对所有从u出发能到大的分支点顶点进行枚举

    for(int v = 0; v < n; v++){  //对每个顶点v

        if(vis[v] == false && G[u][v] != INF){  //v未被访问 且 u可以到达v

            DFS(v, depth+1); //访问v，深度+1

        }

    }

}

void DFSTrave(){  //遍历图G

    for(int u = 0; u < n; u++){ //对每个顶点u

        if(vis[u] == false){    //如果u未被访问

            DFS(u, 1);   //访问u和u所在的连通块，1表示初始为第一层

        }

    }

}

邻接表实现

#include<stdio.h>

#include<vector>

using namespace std;

const int MAXV = 100; //最大顶点数

const int INF  = 100000000; //设INF为一个很大的数

vector<int> Adj[MAXV]; //图G的邻接表

int n; //顶点数

bool vis[MAXV] = {false}; //标记数组

void DFS(int u, int depth){

    vis[u] = true;

    //如果需要对u进行一些操作，可以在这里进行

    for(int i = 0; i < Adj[u].size(); i++){

        int v = Adj[u][i];

        if(vis[v] == false){

            DFS(v, depth+1);

        }

    }

}

void DFSTrave(){ //遍历图G

    for(int u = 0; u < n; u++){  //对每个顶点u

        if(vis[u] == false){     //如果u未被访问

            DFS(u, 1);           //访问u和u所在的连通块，1表示初始为第一层

        }

    }

}

广度优先遍历（BFS）

BFS就是放射状探索

具体步骤

第一部分：给定结点u,遍历u所在的连通块的所有结点

先将起点u加入队列，设置u为已访问

  1. 取出队首元素u
  2. 将u的所有未被访问的邻接点Vi入队，并设置为已访问
  3. 如果队列非空，重复1.2步骤

第二部分：对图G所有结点进行第一部分的操作，即遍历了图的所有连通分量

伪代码

BFS(u){

    queue q;

    inq[u] = true;

    while(q非空){

        去除q的队首元素u进行访问；

        for(从u出发可达的所有顶点v)

            if(inq[v] == false){

                将v入队；

                inq[v] = true;

            }

    }

}

BFSTrave(G){   //遍历图G

    for(G的所有顶点u)  //枚举G所有的顶点u

        if(inq[u] == false){ //如果u未曾加入过队列

            BFS(u);  //遍历u所在的连通块

        }

}

邻接矩阵实现

#include<stdio.h>

#include<queue>    //直接应用stl中定义的队列queue

using namespace std;

#define MAXV 100

#define INF 100000000

int n, G[MAXV][MAXV];  //图的邻接矩阵表示

bool inq[MAXV] = {false};   //标记数组

void BFS(int u){   //遍历u所在的连通块

    queue<int> q;    //定义队列u

    q.push(u);       //将初始点u入队

    inq[u] = true;   //设置u已加入过队列

    while(!q.empty()){  //只要队列非空

        int u = q.front();  //取出队首元素

        q.pop();            //将队首元素出队

        for(int v = 0; v < n; v++){

            //如果u的邻接点未加入过队列

            if(inq[v] == false && G[u][v] != INF){

                q.push(v);     //入队

                inq[v] = true; //标记

               //可以在此处根据题目添加一些操作

            }

        }

    }

}

void BFSTrave(){  //遍历图G

    for(int u = 0; u < n; u++){ //枚举所有顶点

        if(inq[u] == false){    //如果u未曾加入过队列

            BFS(u); //遍历u所在的连通块

        }

    }

}

邻接表实现

#include<stdio.h>

#include<queue>

#include<vector>

using namespace std;

#define MAXV 100

vector<int> Adj[MAXV];  //图的邻接表表示

int n;

bool inq[MAXV] = {false}; //标记数组

void BFS(int u){

    queue<int> q;

    q.push(u);

    inq[u] = true;

    while(!q.empty()){

        int u = q.front();

        q.pop();

        //只有下面的遍历部分与邻接矩阵写法不同

        for(int i=0; i < Adj[u].size(); i++){

            int v = Adj[u][i];

            if(inq[v] == false){

                q.push(v);

                inq[u] = true;

                //可以在此处根据题目添加一些操作

            }

        }

    }

}

void BFSTrave(){

    for(int u = 0; u < n; u++){

        if(inq[u] == false){

            BFS(u);

        }

    }

}

DFS,BFS遍历方法总结

  1. 前置准备：图G的实现（邻接数组，邻接表），标记数组vis（初始化为false）
  2. 函数主体：递归实现。分两部分。

    函数a：遍历结点s所在的连通块。

    函数b：对遍历图G结点应用函数a。
  3. 注意：遍历前用vis判断是否已被标记

相关文章