DATA STRUCTURE September 18, 2019

数据结构之建图方法

Words count 6.5k Reading time 6 mins. Read count 0

关于图

简介

图有多种变体,包括简单图、多重图、有向图、无向图等。James Joseph Sylvester在1878年首次提出“图”这一名词。其中树是一种特殊的图,其边总等于结点数少1。图也有许多类型,不同类型存在不同局限,例如:有向图的边是有方向的,比如从结点1到结点2存在有向边,其为结点1指向结点2的单向边,且结点2到结点1没有连接,那么你就无法直接从结点2到达结点1,除非走更多的其他可行的边。图最重要的两个参数,即边 (Edge) 和结点 (Node) ,其中边或者结点都有可能有更多定义。

拓扑学上的意义*

In topology, a subject in mathematics, a graph is a topological space which arises from a usual graph{\displaystyle G=(E,V)} by replacing vertices by points and each edge {\displaystyle e=xy\in E} by a copy of the unit interval [0,1] where {\displaystyle 0} is identified with the point associated to x and 1 with the point associated to y. That is, as topological spaces, graphs are exactly the simplicial 1-complexes and also exactly the one-dimensional CW complexes.

Thus, in particular, it bears the quotient topology of the set

{\displaystyle X_{0}\sqcup \bigsqcup _{e\in E}I_{e}} (disjoint union)

*转载自维基百科

图的参数

  • (Order):图G中顶集V的大小称作图G的阶。
  • 子图(Sub-Graph):图G’称作图G的子图如果以及E(G')\subseteq E(G)
  • 生成子图(Spanning Sub-Graph):指满足条件 V(G’) = V(G) 的G的子图G’。
  • (Degree):一个顶点的度是指与该顶点相关联的总边数,顶点vv的度记作。度和边有如下关系:\sum_{v\in V} d(v)=2\left|E\right|
  • 出度(Out-degree)和入度(In-degree):对有向图而言,顶点的度还可分为出度和入度。一个顶点的出度为d0,是指有d0条边以该顶点为起点,或说与该点关联的出边共有d0条。入度的概念也类似。
  • 邻接矩阵(Adjacency matrix)
  • 自环(Loop):若一条边的两个顶点相同,则此边称作自环。
  • 路径(Path):从顶点u到顶点v的一条路径是指一个序列v_0,e_1,v_1,e_2,v_2,...e_k,v_k,ei的起点终点为vi-1及vi;k称作路径的长度;v0=u,称为路径的起点;vk=u,称为路径的终点。如果u=v,称该路径是的,反之则称为的;如果v1,…,vk两两不等,则称之为简单路径(Simple path,注意,u=v是允许的)。
  • 行迹(Trace):如果路径P(u,v)中边各不相同,则该路径称为u到v的一条行迹。
  • 轨道(Track):即简单路径。
  • 闭的行迹称作回路(Circuit),闭的轨道称作(Cycle)。(现存文献中的命名法并无统一标准。比如在另一种定义中,walk对应上述的path,path对应上述的track,trail对应上述的trace。)
  • 距离(Distance): 从顶点u出发到顶点v的最短路径若存在,则此路径的长度称作从uv的距离。若从u到v根本不存在路径,则记该距离为无穷。
  • 距离矩阵(Distance matrix)
  • (Bridge):若去掉一条边,便会使得整个图不连通,该边称为桥。

建图

我在此推荐利用到STL的vector<>建图前向星两种方式。

这篇文章介绍vector<>建图。

基础实现

vector<>是向量数组,可以在C++中如此定义:

vector中存放的是一个结构体,结构体包含 目标边to边权值val ,通过输入图的边,按照边数循环进行输入每一条边的参数。存储原理:

from为一个结构体,结构体内容表示这个from结点的参数to和val

G[]数组包含唯一from值,但是from值对应的参数不一定唯一,也就是说一个结点可以连接许多的结点

换一种说法就是,G[from]是一个结构体

#include <iostream>
#include <vector>
#define N 105
using namespace std;
struct Edge{ int val, to;}edge;
vector<Edge>G[N];

void add_single_edge(int from,int to,int value){
    Edge e;
    e.to=to, e.val=value;
    G[from].push_back(e);
}

void add_double_edge(int from,int to,int value){
    Edge e1,e2;
    e1.to=to, e1.val=value;
    e2.to=from, e2.val=value;
    G[from].push_back(e1);
    G[from].push_back(e2);
}

int main(){
    int node, edge, a, b, c;
    cin>>node>>edge;
    //输入图
    for(int i=1;i<=edge;i++){
        cin>>a>>b>>c;
        addedge(a, b, c);
    }
    //输出图测试
    for(int i=1;i<=node;i++){
        for(int j=0;j<G[i].size();j++){
            cout<<i<<" - "<<G[i][j].to<<"     val = "<<G[i][j].val<<endl;
        }
    }
    return 0;
}
0%