数据结构基础(七)

Chapter 6 Graph

Definition

• G(V, E)
  • G ::= graph
  • V ::= vertice
  • E ::= edge
• Undirected graph: $<v, w> = <w, v>$
• Directed graph: $<v, w> \ne <w, v>$
• Restrictions:
  • No self loop
  • No multigraph
• Complete graph: has the maximum number of edges
  • Undirected Graph: $V = n\to E=C^2_n$
  • Directed Graph: $V = n\to E=P^2_n$
• Adjacent:
  • Adjacent to
  • Adjacent from
• Subgraph
• Path form $v_p$ to $v_q$
• Length of path
• Simple path: No repeated $v_i$
• Cycle: simple path with $v_p,v_q$
• Connected
• Component of an undirected graph: the maximal connected subgraph
• Tree: connected & acyclic graph
• DAG: directed acyclic graph
• Strongly connected directed graph
  • Weakly conncted directed graph (ignore direction)
• Strongly connected component
• Degree(v): number of edges incident to v
  • in-degree
  • out-degree
  • $e=(\displaystyle\sum_{i=0}^{n-1} d_i/2)$

Representation

Adjacency Matrix

$$adj\_mat[i][j]=\begin{cases}1&<v_i,v_j>\\0&otherwise\end{cases}$$

If G is undirected, adj_mat[][] is symmetric — space-wasting

replace by one-dimension array

$adj\_mat[n(n + 1) / 2]$
$a_{ij} = i(i-1)/2 + j$

即使如此，对于稀疏图 / 散点图，邻接矩阵依然 spece-wasting

Adjacency Lists

Replace each row by a linked list

[Example figure TBD]

The order of nodes in each list does not matter

$S = n\mathrm{\ heads}+2e\mathrm{\ nodes}=(n+2e)\mathrm{\ ptrs}+2e\mathrm{\ ints}$

To calculate the degree of undirected G:

1. Add inverse adjacency lists

   同时维护出度表和入度表

2. Multilist representation for adj_mat[ i ][ j ]

Adjacency Multilists

graph[i] -> [node] <- graph[j]

each node represents a edge

$S = n\mathrm{\ heads}+e\mathrm{\ nodes}=(n+2e)\mathrm{\ ptrs}+2e\mathrm{\ ints}+\mathrm{(mark)}$

• mark: the feature of edge (weight, direction, …)

Topological Sort

[Eg] Choosing Course Problem

• AOV Network: activity on vertice network
• Predecessor
  • Immediate Predecessor
• Partial order: both transitive irreflexive ($i\to i$ is impossible)

If a project is feasible, it must be irreflexive

Topo. sort is not unique

Implementation

See Also: 小时候写的 Topo. Sort

void Toposort(Graph G){
    int Counter;
    Vertex V, W;
    for(Counter = 0; Counter < NumVertex; ++ Counter){
        V = FindNewVertexOfDegreeZero();
        if(V == NotAVertex){
            Error(“Graph has a cycle”);
            Break;
        }
        TopNum[V] = Counter;
        for(each W adjacent V)
            Indegree[W] --;
    }
}

$T=O(|V|^2)$

queue or stack amplify

officialpersonal

void Toposort(){
}

void toposort(Graph G){  
    Queue q;  
    Vector v;   //储存排序后的结果, 也可以直接输出拓扑序  
    int cnt = 0;  
    for V:0->N{ //初始将所有入度为0的节点入队  
        if( V.indegree == 0 ){  
            q.push(V);  
        }
    }  
      
    while(q){  
        V = q.pop();  
        v.push(V);  
        ++cnt;  
        //对所有V的后驱W进行操作  
        for W:0->N{  
            if( <V,W> == 1 ){  
                --W.indegree;  
                //如果减去这个入度后, W的入度为0, 则入队  
                if( W.indegree == 0 ){  
                    q.push(W);  
                }  
            }  
        }  
    }
    if( cnt != N ){ 
        //如果只排序了不到N个节点, 说明存在环导致有的节点的入度无法归零  
        Erorr();
        return Vector{};
    }  
    else{  
        return v;  
    }  
}

$T=O(|V|+|E|)$