Struct_Graph

Struct_Graph

read book

what’s graph

• linear list : one-to-one
• tree : one-to-many
• graph : many-to-many

linear list and tree could regard as a special case of graph

basic terms

弱连通 : 若有向图中不形成强连通但不考虑方向(即作为无向图考虑)连通则为弱连通

ADT

expression of graph

• adjacent matrix : G[ ][ ]
  
  
  
  
  
  

• adjacency list
  仅对稀疏图效率较高
  
  
  需要N个头指针 + 2E个结点（每个结点至少2个域），则E小于多少是省空间的？

  • n(n-1)/4

• 还有许多表示graph的方法,针对于具体问题分析;不仅仅局限于教科书上的两种常用表示法

---

traverse the graph

DFS(depth first search)

• 对邻接表：每条边访问一次且每个点访问一次 --> O(N+E)

• 以队列实现 --> 弹出队首的同时将直接邻接点入队(同层)
• 1/2 3 4 5 6 7/8 9/10/11 12 13/14 15/16/17 18 19

• BFS:对于解决最短或最少问题特别有效，而且寻找深度小，但缺点是内存耗费量大（需要开大量的数组单元用来存储状态)
  “任意节点时都需要查看周边全部可能结果”

• DFS：对于解决遍历和求所有问题有效，对于问题搜索深度小的时候处理速度迅速，然而在深度很大的情况下效率不高
  “一步错就步步错”