[数据结构与算法] 数据结构_第7讲图的基本概念、存储与遍历

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构_第7讲图的基本概念、存储与遍历 -> 正文阅读

[数据结构与算法]数据结构_第7讲图的基本概念、存储与遍历

1.图的基本概念

(1) 有向图、无向图
(2) 度数（出度、入度）有向图(度数= 出度+ 入度)
(3) 简单图：不存在顶点到其自身的边，且同一条边不重复出现
(4) 路径、环、简单路径(路径不包括重复的点和边)
(5) 无向完全图：任意两个顶点之间都存在边，有n个顶点的无向完全图有 n × (n - 1) / 2条边

$C_n^2$

(6) 有向完全图：任意两个顶点之间都存在方向护卫相反的两条弧，有n个顶点的无向完全图有 n × (n - 1) 条弧

$A_n^2$

(7) 稀疏图&稠密图：有很少条边或弧的图称为稀疏图，反之称为稠密图，相对的概念。

2.图的存储及基本操作

(1) 邻接矩阵：适用于稠密图，可存有向图、无向图。常用。空间复杂度： $O(n^2)$ 无法存重边

$O(n^2)$

无向图每条边看成2条有向边

(2) 邻接表：适用于稀疏图，可存有向图、无向图。常用。空间复杂度：O(n + m) O(m) 可存重边

可存储重边 使用最多

上机用的最多 vector set stack queue？

当有重边：

(3) 邻接多重表，适用于稀疏图，可存无向图。不常用。空间复杂度：O(n + m) 可重存边

领接表不方便找反向边

领接表优化为邻接多重表

上机不会用，因为oj中会用数组模拟链表，存储连续，相邻的就是反向边。

(4) 十字链表，适用于稀疏图，可存有向图、无向图。不常用。空间复杂度：O(n + m) 不能存重边

对邻接矩阵优化

(5) 三元组表，适用于稀疏图，可存有向图，无向图。常用于Bellman-Ford算法、Kruskal算法。空间复杂度：O(m)

m条边 $O (m)$

3.图的遍历

(1) 深度优先搜索。邻接表存储的时间复杂度： $O (n + m)$ 。邻接矩阵存储的时间复杂度： $O(n^2)$

DFS : 能走就必须走，判重

深搜：能走就走，可能撞了南墙才会回头吧、

(2) 广度优先搜索。邻接表存储的时间复杂度： $O (n + m)$ 。邻接矩阵存储的时间复杂度： $O(n^2)$

bfs 宽搜求最短路径

4.拓扑排序

拓扑排序：存在拓扑排序 == 无环

所有边从前指向后

常用bfs $O (n + m)$

入度为 0 的点、最后判断是否每个点是否遍历到了

AcWing 848. 有向图的拓扑序列

BFS：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5+5,M = 1e5+5;
int n,m;

struct Node {
    
    int id;
    Node* next;
    Node(int _id): id(_id),next(NULL){}
    
}*head[N];

int d[N] ; // 入度
int q[N] ; //数组模拟队列

void add(int a, int b)  // 添加一条边b->a  头插法 3->2->1;
{
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
    
}
// bfs 广搜 
bool istopsort(){
    int hh = 0, tt  = -1 ;
    
    for(int i= 1; i<=n;i++){ // n个点  先找到入度为0的点入队列
        
        if(!d[i]) // 此点入度为0
        {
            q[++tt]= i ; // 队列入队
        }
        
    } 
    
    while(hh<=tt){ // 队列不为空
        
        int t = q[hh++]; // 取队头
        
        for(auto p= head[t];p;p=p->next){ //遍历 领接表 队头的链表head[t]
            if(-- d[p->id] == 0)
                q[++tt] = p->id;  // 队头去掉后; 后面相连的点入度-1 ; 为0的入队
            
        }
        
    }
    
    return tt == n - 1 ;  //队长是否等于n-1  判断是否所有的点都入队了，就是判断是否所有点遍历到了
    
}


int main()
{
    cin>>n>>m;  // n个点 m 条边
    
    while(m--){
        int a,b;
        cin>>a>>b;
        d[b]++ ;  // a->b 入度+1
        add(a,b); // 插入
        
    }
    // for(auto p=head[1];p;p=p->next)
    // cout << p->id<<endl;
    
    if(!istopsort()) cout<<-1<<endl;  // 不是拓扑排序
    else{
        // q[N] 打印队列
        for(int i=0;i<n;i++)
        cout<<q[i]<<' ';
        
    }
    
    return 0;
}