跳到主要内容

数据结构-非线性结构-图

G=(V,E)G=(V,E)

概念​

有向图​

  • 弧:{vi,Vj}∈V,<vi,vj>∈E\{v_i,V_j\} \in V, <v_i,v_j> \in E
  • 出度:OD(v)=∣{<v,vj>,vj∈V∈G}∣OD(v)=|\{<v,v_j>,v_j \in V \in G\}|
  • 入度:ID(v)=∣{<vj,v>,vj∈V∈G}∣ID(v)=|\{<v_j,v>,v_j \in V \in G\}|
  • 度:D(v)=OD(v)+ID(v)D(v)=OD(v)+ID(v)
  • 关系式:∣E∣=12∑i=1∣E∣D(vi)|E|=\frac{1}{2}\sum^{|E|}_{i=1}D(v_i)
  • 路径:∃{vp,vq}⊆V(E),P={<vp,v...>,⋯ ,<v...,vq>}⊆E(G)\exists \{v_p,v_q\} \subseteq V(E), P=\{<v_p,v_{...}>,\cdots,<v_{...},v_q>\}\subseteq E(G)
  • 子图:∃G(V,E),G′(V′,E′)V′⊆VandE′⊆E\exists G(V,E),G'(V',E') V' \subseteq V and E' \subseteq E
  • 强连通图:∀vp,vq∈V(G),P(vp,vq)⊆V(G)\forall v_p,v_q \in V(G),P(v_p,v_q)\subseteq V(G)
    • 强连通分量（极大子图）:G′=GG'=G
  • 网:∀e∈E(G),weight(e)\forall e \in E(G),weight(e)
  • 有向树
    • ∃G=(V,E)∃ one v∈V(G),ID(v)=0∀vx∈V(G)≠v, ID(v)=1\exist G=(V,E) \\ \exist \space one \space v \in V(G), ID(v)=0 \\ \forall v_x \in V(G) \neq v,\space ID(v)=1
  • 有向完全图:∃G=(V,E), ∣E(G)∣=n(n−1∣)2 n=∣V(G)∣\exists G=(V,E),\space |E(G)|=\frac{n(n-1|)}{2} \space n=|V(G)|

单源点最短路径​

无向图​

  • 边:{vi,Vj}∈V,(vi,vj)∈E\{v_i,V_j\} \in V, (v_i,v_j) \in E
  • 度:D(v)=∣{(v,vj),vj∈V∈G}∣D(v)=|\{(v,v_j),v_j \in V \in G\}|
  • 路径:∃{vp,vq}⊆V(E),P={(vp,v...),⋯ ,(v...,vq)}⊆E(G)\exists \{v_p,v_q\} \subseteq V(E), P=\{(v_p,v_{...}),\cdots,(v_{...},v_q)\}\subseteq E(G)
  • 子图:∃G(V,E),G′(V′,E′)V′⊆VandE′⊆E\exists G(V,E),G'(V',E') V' \subseteq V and E' \subseteq E
  • 连通图:∀vp,vq∈V(G),P(vp,vq)⊆V(G)\forall v_p,v_q \in V(G),P(v_p,v_q)\subseteq V(G)
    • 连通分量:G′=GG'=G
  • 网:∀e∈E(G),weight(e)\forall e \in E(G),weight(e)
  • 无向完全图:∃G=(V,E), ∣E(G)∣=n(n−1∣) n=∣V(G)∣\exists G=(V,E),\space |E(G)|=n(n-1|) \space n=|V(G)|

存储结构​

邻接矩阵​

  • G=Aij,i=j=∣V(G)∣aij={0(vi,vj),<vi,vj>∉E(G)1(vi,vj),<vi,vj>∈E(G)∞(vi,vj),<vi,vj>∉E(G)Wij(vi,vj),<vi,vj>∈E(G)G=A_{ij},i=j=|V(G)| \\ a_{ij}= \begin{cases} 0 && (v_i,v_j),<v_i,v_j> \notin E(G) \\ 1 && (v_i,v_j),<v_i,v_j> \in E(G) \\ \infty && (v_i,v_j),<v_i,v_j> \notin E(G) \\ W_{ij} && (v_i,v_j),<v_i,v_j> \in E(G) \end{cases}

邻接链表​

  • type VNode={data:char;firstarc:ArcNode};
    type ArcNode={nextarc:ArcNode;weight:number};
    type Graph={Vnum:number; AdjList:Vnode[]};

推广​

生成树​

  • ∃T=(V,E), T=G(V,E)∣E∣=∣G∣−1\exist T=(V,E),\space T=G(V,E) |E|=|G|-1

最小生成树​

  • ∃Ti∈F=(T),W(Ti)<W(Tk)\exist T_i \in F=(T), W(T_i)<W(T_k)
  • Prim
    • 对于连通网N，依次遍历顶点，把其权值最小的边和该点并入T，直到V(N)=V(T),T为N的最小生成树
  • Kruskal
    • 对于连通网N，建立非连通图T.使V(N)=V(T)，查找N中权最小的边，归入T,直到T连通，T为N的最小生成树

AOV网​

  • 在工程领域，通常把大工程划分为多个子工程，子工程有先后关系，所有子工程完成后，整个工程就完成了。
    • 大工程:AOV
    • 子工程:V
    • 优先级:E
    • AOV=(V,E)
    • AOV 网中存在回路称为DAG，工程必不能完成。
      • 在AOV网中找到ID(v)=0,从网中移除v,AOV中不存在入度=0的点为止，如果成立，则该AOV网是DAG。

AOE网​

  • 使用边记录活动，顶点记录事件(活动结束/开始)，权记录活动信息
    • 源点，入度为0
    • 汇点，出度为0
    • 最早发生时间ve(j)={0j=0max⁡{ve(i)+dut(<i,j>)<i,j>∈T,i≤j≤∣V∣−1}ve(j)=\begin{cases} 0 && j=0 \\ \max\{ve(i)+dut(<i,j>) && <i,j> \in T,i \le j \le |V|-1 \} \end{cases}
    • 最晚结束时间vl(i)={ve(i)i=∣V∣−1min{vl(j)−dut(<i,j>)}<i,j>∈S,i≤i≤n−2vl(i)=\begin{cases} ve(i) && i=|V|-1 \\ min\{vl(j)-dut(<i,j>)\} && <i,j>\in S,i \le i \le n-2 \end{cases}

单源点最短路径​

  • 求从源点开始到各点的最短路径

每对点最短路径​

  • 以每个点为源点，计算每对顶点的最短路径