图的构建和遍历

图是一种包括节点和边的数据结构，本文对图的构建、图的遍历给出详细的代码。其中，

图的表示方法有：

邻接矩阵
邻接表

图的遍历方法有：

深度优先搜索（DFS）
广度优先搜索（BFS）

1. 图的表示 1.1 邻接矩阵

#include 
#include 
using namespace std;

#define maxNodeNum 100 //最大顶点数

//定义图
struct GraphNode{
    int nodeNum; //顶点数
    int edgeNum; //边数
    vector> graph;
    
    GraphNode(): nodeNum(0),edgeNum(0),graph(maxNodeNum,vector(maxNodeNum,0)){}
    GraphNode(int n,int m): nodeNum(n),edgeNum(m),graph(maxNodeNum,vector(maxNodeNum,0)){}
};

class Solution{
public:
    GraphNode* buildGraph(){
        GraphNode* g = new GraphNode();
        cin>>g->nodeNum; //输入顶点数
        cin>>g->edgeNum; //输入边数
        if(g->edgeNum!=0){ //如果有边
            //输入边，建图
            for(int i=0;iedgeNum;i++){
                int node1,node2; //边连接的两个节点
                int weight; //边权重，可以设为1，表示有连接，0表示无连接
                cin>>node1>>node2>>weight;
                g->graph[node1][node2] = weight; //插入边
                g->graph[node2][node1] = weight; //此处模拟无向图
            }
        }
        
        return g;
    }

    //遍历图
    void printGraph(GraphNode* g){
        for(int i=0;inodeNum;i++){
            for(int j=0;jnodeNum;j++){
                cout<graph[i][j]<<" ";
            }
            cout<
    Solution s;
    GraphNode* g = s.buildGraph();
    s.printGraph(g);
    return 0;
}

1.2 邻接表

#include 
#include 
using namespace std;

#define maxNodeNum 100 //最大顶点数

//图节点定义
struct VNode{
    int nodeVal; //邻接点下标
    int weight; //边权重
    
    VNode* next; //指向下一个邻接点的指针

    VNode():nodeVal(-1),weight(0),next(NULL){} // 这里的-1是随便设的
    VNode(int node,int w,VNode* ptr):nodeVal(node),weight(w),next(ptr){}
};

//图定义
struct GraphNode{
    int nodeNum;  //顶点数
    int edgeNum; //边数
    vector graph; //邻接表
    //下面的初始化逻辑是错误的，graph(maxNodeNum,new VNode())的意思是maxNodeNum个指针全都指向new Node()开辟的一个空间
    //导致插入节点时都是在一个头节点上进行插入
    GraphNode(): nodeNum(0),edgeNum(0){
        for(int i=0;i
            VNode* init = new VNode();
            graph.push_back(init);
        }
    }
    GraphNode(int n,int m): nodeNum(n),edgeNum(m),graph(maxNodeNum){
        for(int i=0;i
            VNode* init = new VNode();
            graph.push_back(init);
        }
    }
};

class Solution{
public:
    //插入边
    void insertEdge(GraphNode* g,int node1,int node2,int weight){
        VNode* newNode1 = new VNode();
        
        newNode1->nodeVal = node2;
        newNode1->weight = weight;
        //将node2插入node1的头节点
        newNode1->next = g->graph[node1]->next;
        g->graph[node1]->next = newNode1;

        
        VNode* newNode2 = new VNode();
        newNode2->nodeVal = node1;
        newNode2->weight = weight;
        //将node1插入node2的头节点
        newNode2->next = g->graph[node2]->next;
        g->graph[node2]->next = newNode2;
    }
    //构建图
    GraphNode* buildGraph(){
        GraphNode* g = new GraphNode();
        cin>>g->nodeNum;
        cin>>g->edgeNum;
        if(g->edgeNum!=0){ //边数不为零时
            for(int i=0;iedgeNum;i++){
                int node1,node2; //边节点
                int weight; //边权重
                cin>>node1>>node2>>weight;
                insertEdge(g,node1,node2,weight);
            }
        }
        // 如果顶点有数据的话，读入数据

        return g;
    }
    void printGraph(GraphNode* g){
        VNode* cur;
        for(int i=0;inodeNum;i++){
            cout<graph[i]->next;
            while(cur){
                cout<nodeVal<<" ";
                cur = cur->next;
            }
            cout<
    Solution s;
    GraphNode* g = s.buildGraph();
    s.printGraph(g);
    return 0;
}

2. 图的遍历 2.1 深度优先搜索

深度优先遍历图的方法是，从图中某顶点v出发：

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

深度优先搜系类似于树的先序遍历，伪代码如下所示：

void DFS(Vertex V)
{ 
    visited[V] = true;
    for(V的每个邻接点W)
        if (!visited[W])
            DFS(W) ;
}

若有N个顶点、E条边，时间复杂度：

用邻接表存储图，为 O ( N + E ) O (N+E) O(N+E)
用邻接矩阵存储图，为 O ( N 2 ) O ( N^2 ) O(N2)

2.2 广度优先搜索

广度优先搜索的基本过程：BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。

广度优先搜索类似于树的层序遍历，伪代码如下所示：

void BFS(Vertex V)
{ 
    visited[V] = true;
    Enqueue(V, Q);
    while(!IsEmpty (Q)){
        V = Dequeue(Q);
        for (V的每个邻接点W){
			if(!visited[W]){
                visited[W]= true;
                Enqueue (W, Q);
            }
		}   
    }
}

若有N个顶点、E条边，时间复杂度：

用邻接表存储图，为 O ( N + E ) O (N+E) O(N+E)
用邻接矩阵存储图，为 O ( N 2 ) O ( N^2 ) O(N2)

3. 图的遍历代码 3.1 邻接矩阵的遍历

#include 
#include 
#include 
using namespace std;

#define maxNodeNum 100 //最大顶点数

//定义图
struct GraphNode{
    int nodeNum; //顶点数
    int edgeNum; //边数
    vector> graph;
    
    GraphNode(): nodeNum(0),edgeNum(0),graph(maxNodeNum,vector(maxNodeNum,0)){}
    GraphNode(int n,int m): nodeNum(n),edgeNum(m),graph(maxNodeNum,vector(maxNodeNum,0)){}
};

class Solution{
public:
    GraphNode* buildGraph(){
        GraphNode* g = new GraphNode();
        cin>>g->nodeNum; //输入顶点数
        cin>>g->edgeNum; //输入边数
        if(g->edgeNum!=0){ //如果有边
            //输入边，建图
            for(int i=0;iedgeNum;i++){
                int node1,node2; //边连接的两个节点
                int weight; //边权重，可以设为1，表示有连接，0表示无连接
                cin>>node1>>node2>>weight;
                g->graph[node1][node2] = weight; //插入边
                g->graph[node2][node1] = weight; //此处模拟无向图
            }
        }
        
        return g;
    }
};

vector visit(maxNodeNum,false);
//深搜,类似于二叉树的递归遍历
void dfs(GraphNode* g,int val){
    visit[val] = true;
    cout<<"正在访问节点"<nodeNum;i++){
        if(!visit[i] && g->graph[val][i]){
            dfs(g,i);
        }
    }
}

//广搜，类似于二叉树的层序遍历
void bfs(GraphNode* g,int val){
    queue que;
    que.push(val);
    visit[val] = true;
    cout<<"正在访问节点"<
        int curVal = que.front();
        que.pop();
        for(int i=0;inodeNum;i++){
            if(!visit[i] && g->graph[curVal][i]){
                que.push(i);
                visit[i] = true;
                cout<<"正在访问节点"<
    Solution s;
    GraphNode* g = s.buildGraph();
    dfs(g,0);
    for(int i=0;i
        visit[i] = false;
    }
    bfs(g,0);
    return 0;
}

3.2 邻接表的遍历

#include 
#include 
#include 
using namespace std;

#define maxNodeNum 100 //最大顶点数

//图节点定义
struct VNode{
    int nodeVal; //邻接点下标
    int weight; //边权重
    
    VNode* next; //指向下一个邻接点的指针

    VNode():nodeVal(-1),weight(0),next(NULL){} // 这里的-1是随便设的
    VNode(int node,int w,VNode* ptr):nodeVal(node),weight(w),next(ptr){}
};

//图定义
struct GraphNode{
    int nodeNum;  //顶点数
    int edgeNum; //边数
    vector graph; //邻接表
    //下面的初始化逻辑是错误的，graph(maxNodeNum,new VNode())的意思是maxNodeNum个指针全都指向new Node()开辟的一个空间
    //导致插入节点时都是在一个头节点上进行插入
    GraphNode(): nodeNum(0),edgeNum(0){
        for(int i=0;i
            VNode* init = new VNode(i,0,NULL);
            graph.push_back(init);
        }
    }
    GraphNode(int n,int m): nodeNum(n),edgeNum(m),graph(maxNodeNum){
        for(int i=0;i
            VNode* init = new VNode();
            graph.push_back(init);
        }
    }
};

class Solution{
public:
    //插入边
    void insertEdge(GraphNode* g,int node1,int node2,int weight){
        VNode* newNode1 = new VNode();
        
        newNode1->nodeVal = node2;
        newNode1->weight = weight;
        //将node2插入node1的头节点
        newNode1->next = g->graph[node1]->next;
        g->graph[node1]->next = newNode1;

        
        VNode* newNode2 = new VNode();
        newNode2->nodeVal = node1;
        newNode2->weight = weight;
        //将node1插入node2的头节点
        newNode2->next = g->graph[node2]->next;
        g->graph[node2]->next = newNode2;
    }
    //构建图
    GraphNode* buildGraph(){
        GraphNode* g = new GraphNode();
        cin>>g->nodeNum;
        cin>>g->edgeNum;
        if(g->edgeNum!=0){ //边数不为零时
            for(int i=0;iedgeNum;i++){
                int node1,node2; //边节点
                int weight; //边权重
                cin>>node1>>node2>>weight;
                insertEdge(g,node1,node2,weight);
            }
        }
        // 如果顶点有数据的话，读入数据

        return g;
    }
    void printGraph(GraphNode* g){
        VNode* cur;
        for(int i=0;inodeNum;i++){
            cout<graph[i]->next;
            while(cur){
                cout<nodeVal<<" ";
                cur = cur->next;
            }
            cout< visit(maxNodeNum,false);
//深搜，类似于二叉树的递归遍历
void dfs(GraphNode* g,int val){
    cout<<"正在访问顶点"<graph[val]->next;
    while(curNode){
        if(!visit[curNode->nodeVal]){
            dfs(g,curNode->nodeVal);
        }
        curNode = curNode->next;
    }
}

//广搜，类似于二叉树的层序遍历
void bfs(GraphNode* g,int val){
    queue que;
    que.push(g->graph[val]);
    cout<<"正在访问节点"<
        VNode* curNode = que.front();
        que.pop();
        VNode* nextNode = curNode->next;
        while(nextNode){
            if(!visit[nextNode->nodeVal]){
                que.push(g->graph[nextNode->nodeVal]);
                cout<<"正在访问节点"<nodeVal<nodeVal] = true;
            }
            nextNode = nextNode->next;
        }
    }
}


int main(){
    Solution s;
    GraphNode* g = s.buildGraph();
    dfs(g,0);
    cout<<"=============="<
        visit[i] = false;
    }
    bfs(g,0);
    return 0;
}

参考

数据结构（四）—— 图（1）：什么是图
数据结构（四）—— 图（2）：图的遍历

图的构建和遍历

C/C++/C#相关栏目本月热门文章