本節書摘來自華章出版社《資料結構與算法：python語言描述》一書中的第1章，第1.2節，作者 裘宗燕，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視
本節展示一個具體問題的計算機求解過程，以此說明在這種過程中可能出現的一些情況，需要考慮的一些問題，以及一些可能的處理方法。
交叉路口是現代城市路網中最重要的組成部分，繁忙的交叉路口需要用紅綠燈指揮車輛通行與等待，正确的紅綠燈排程安排對于保證交通安全、道路運作秩序和效率都非常重要。交叉路口的情況多種多樣，常見形式有三岔路口、十字路口，也有較為少見的更複雜形式的路口。進一步說，有些道路是單行線，在中國的交叉路口還有人車分流和專門的人行/自行車紅綠燈等許多情況，這些都進一步增加了路口交通控制的複雜性。要開發一個程式生成交通路口的紅綠燈安排和切換，需要考慮許多複雜情況。
現在計劃考慮的問題很簡單，隻考慮紅綠燈（實際上是相應允許行駛路線）如何安排，可以保證相應的允許行駛路線互不交錯，進而保證路口的交通安全。
為把問題看得更清楚，先考慮一個具體執行個體，希望從中發現解決問題的線索。作為執行個體的交叉路口如圖1.2所示：這是一個五條路的交叉口，其中兩條路是單行線（圖中用箭頭标出），其餘是正常的雙向行駛道路。實際上，這個圖形本身已經是原問題執行個體的一個抽象，與行駛方向無關的因素都已被抽象去除，例如道路的方位、不同道路交叉的角度、各條道路的實際寬度和通常的車流量等。
根據圖形中表示的情況不難看到，從路口各駛入方向來的車輛，都可能向多個方向駛出，各種行駛方向的軌迹互相交錯，形成很複雜的局面。按不同方向行駛的車輛可能互相沖突，存在着很實際的安全問題，是以，紅綠燈的設計必須慎重！
現在的基本想法是對行駛方向分組，使得：
同屬一組的各個方向行駛的車輛，均可以同時行駛，不出現互相交錯的行駛路線，是以保證了安全和路線暢通。
所做的分組應該盡可能大些，以提高路口的效率（經濟問題）。
第一條是基本的安全問題，絲毫不能妥協。而第二條隻是經濟問題，這個要求具有相對性。不難看出，允許同時行駛的方向越少，就越能保證安全。例如，每次隻放行一個行駛方向，肯定能保證安全，但道路通行效率太低，是以完全不可取。另外還可以看到，這不是一個一目了然的問題，需要深入分析，才能找到較好的統一解決方法。
圖形的表達方式一目了然，特别有助于人們把握問題的全局。但是，如圖1.2這樣的圖形并不适合表達問題細節和分析結果。如果把所有允許行駛方向畫在圖中，看到的将是來來去去、互相交錯的許多有向線段，不容易看清其互相關系。
為了理清情況，應該先羅列出路口的所有可能行駛方向，例如從道路a駛向道路b，從道路a駛向道路c。為簡便易讀，用ab、ac表示這兩個行駛方向，其他方向都采用類似的表示方式。不難列出路口總共有13個可行方向：ab, ac, ad, ba, bc, bd, da, db, dc, ea, eb, ec, ed。
采用這種抽象表示，問題的實質看得更清楚了。有了（給定了）一集不同的行駛方向，需要從中确定一些可以同時開綠燈的方向組。也就是說，需要為所有可能方向做出一種安全分組，保證位于每組裡的行駛方向互相不沖突，可以同時放行。
這裡的“沖突”又是一個需要進一步明确的概念。顯然，兩個行駛路線交叉是最明顯的沖突情況。如果對這樣兩個方向同時開綠燈，按綠燈行駛的車輛就有在路口撞車的危險，這是不能允許的。是以，這樣的兩個方向不能放入同一個分組。
為了弄清安全分組，需要設想一種表示沖突的方式，更清晰地描述沖突的情況。如果把所有行駛方向畫在一張紙上，在互相沖突的方向之間畫一條連線，就做出了一個沖突圖。圖1.3就是上面執行個體的沖突圖，其中的13個小矩形表示所有的可能行駛方向，兩個矩形之間有連線表示它們代表的行駛路線互相沖突。注意，在這個圖形中，各個矩形的位置、大小等都不代表任何資訊，隻有矩形中的符号和矩形之間的連線有意義。這樣的圖形構成了一種資料結構，也稱為圖，圖中元素稱為頂點，連線稱為邊或者弧。互相之間有邊的頂點稱為鄰接頂點。第7章将會詳細讨論這種結構。
有了沖突圖，尋找安全分組的問題就可以換一種說法：為沖突圖中的頂點确定一種分組，保證屬于同一組的所有頂點互不鄰接。顯然，可能的分組方法很多。如前所述，将每個頂點作為一個組一定滿足要求。但從原問題看，這裡期待一種比較少的分組或者最少的分組。回到原問題，就是希望在一個周期中的紅綠燈轉換最少。
經過一步步抽象和嚴格化，要解決的問題從交叉路口的紅綠燈安排變成了一類抽象的圖資料結構上的頂點分組。假設有了這樣一個圖結構，現在需要考慮一個算法，其計算的結果給出一個滿足需要的分組。對這個問題，安全性是第一位的基本要求，必須滿足；而分組最少是進一步的附加要求，是一種追求。
以非相鄰為條件的最佳頂點分組問題，實際上對應于有名的圖最佳着色問題：把頂點看作區域，把相鄰看作兩個區域有邊界，把不同分組看作給相鄰頂點以不同顔色着色。著名的四色問題表明，對于以任一方式分割為區域的平面圖，隻需要用4種不同顔色着色，就能保證相鄰區域都具有不同的顔色。但請注意，從交叉路口情況構造出的沖突圖可能不是平面圖，是以完全可能需要更多的顔色。
人們對圖着色的算法做過一些研究，目前的情況是：已經找到的最佳着色算法（得到最佳分組），基本上相當于枚舉出所有可能的着色方案，從中選出使用顔色最少的方案。例如，一種直截了當的方法是首先基于圖中頂點枚舉出所有可能分組，從中篩選出滿足基本要求的分組（各組中的頂點互不相鄰），再從中選出分組數最小的分組。由于計算中需要考慮各種可能組合，這種組合數顯然是頂點個數的指數函數，這個算法的代價太高了。能得到最佳分組的其他算法可能更複雜，但在效率上沒有本質性提高。
下面考慮一種簡單算法，它被稱為是一種貪婪算法，或稱貪心法。貪心法也是一種典型的算法設計思路（或稱算法設計模式），其中的基本想法就是根據當時掌握的資訊，盡可能地向得到解的方向前進，直到不能繼續再換一個方向。這樣做通常不能找到最優解，但能找到“可接受的”解，即給出一種較好的分組。
算法的梗概（僞代碼）如下：
輸入：圖g # 記錄圖中的頂點連接配接關系
集合verts儲存g中所有頂點 # 建立初始狀态
設定集合groups為空集 # 記錄得到的分組，元素是頂點集合
while存在未着色頂點: # 每次疊代用貪心法找一個新分組
選一種新顔色
在未着色頂點中給盡量多的無互連邊的點着色（建構一個分組）
記錄新着色的頂點組
算法結束時集合groups裡記錄着一種分組方式
算法細節還需要進一步考慮
現在考慮用這個算法處理圖1.3中的沖突圖，假定操作按照前面列出的13個方向的順序進行處理。操作中的情況如下：
1.選第1種顔色構造第1個分組：順序選出互相不沖突的ab、ac、ad，以及與任何方向都不沖突的ba、dc和ed，做成一組；
2.選出bc、bd和與它們不沖突的ea作為第二組；
3.選出da和db作為第三組；
4.剩下的ea和eb作為第四組。
由于上面算法中這幾個分組内互不沖突，而且每個行駛方向屬于一個分組，是以是滿足問題要求的一個解。得到的分組如下：
{ab, ac, ad, ba, dc, ed}, {bc, bd, ea}, {da, db}, {ea, eb}
上面算法還有重要的細節缺失：一種新顔色的着色處理。現在考慮這個問題。
假設圖g儲存需着色圖中頂點的鄰接資訊，集合verts是圖中所有尚未着色的頂點的集合。顯然，算法開始時verts應該是g中所有頂點的集合。用另一個變量new_group記錄正在構造的用目前新顔色着色的頂點（一個集合），在上面算法的每次疊代中重新構造，每次開始做分組時将這個集合重新設定為空集。
在上面安排的基礎上，找出verts中可用新顔色着色的頂點集的算法是：
這樣就有了一個完整的算法。
檢查上面算法，可以看到算法中假設了一些集合操作和一些圖操作。集合操作包括判斷一個集合是否為空集，構造一個空集，從一個集合裡删除元素，向一個集合裡加入元素，順序獲得集合裡的各個元素（上面算法中for循環做這件事）。圖操作包括擷取圖中所有頂點、判斷兩個頂點是否相鄰。
上面讨論中實際上也介紹了兩種最基本的算法設計方法：
枚舉和選擇（選優）：根據問題，設法枚舉出所有可能的情況，首先篩選出問題的解（為此需要判斷枚舉生成的結果是否為問題的解），而後從得到的解中找出最優解（這一步需要能評價解的優劣）。
貪心法：根據當時已知的局部資訊，完成盡可能多的工作。這樣做通常可以得到正确的解，但可能并非最優。對于一個複雜的問題，全面考慮的工作代價可能太高，為得到實際可用的算法，常常需要在最優方面做出妥協。
前面給出了一個解決圖着色的抽象算法，它與實際程式還有很大距離。要進一步考慮如何實作，還有很多需要處理的細節，例如：
如何表示顔色？例如，可以考慮用順序的整數。
如何記錄得到的分組？可以考慮用集合表示分組，把構造好的分組（集合）加入groups作為元素（也就是說，groups是集合的集合）。
如何表示圖結構？
實際上，是否把“顔色”記入groups并不重要，可以記錄或者不記錄。下面的考慮是記錄顔色，将“顔色”和新分組做成二進制組。
現在考慮如何把上述算法映射到一個python程式中，填充其中的許多細節。前面考慮的集合操作大都可以直接用python的集合操作：
判斷一個集合vs是空集，對應于直接判斷not vs。
設定一個集合為空，對應于指派語句vs = set()。
從集合中去掉一個元素的對應操作是vs.remove(v)。
向集合裡增加一個元素的對應操作是vs.add(v)。
python的集合資料類型不支援元素周遊，但上述算法中需要周遊集合元素，還要在周遊中修改集合。處理這個問題的方法是在每次需要周遊時從當時的verts生成一個表，而後對表做周遊（并不直接對集合周遊）。
算法中需要的圖操作依賴于圖的表示，需要考慮如何在python中實作圖資料結構。圖是一種複雜資料結構，應該支援一些操作。圖的可能實作方法很多，第7章将詳細讨論這方面問題。這裡假定兩個與圖結構有關的操作（依賴于圖的表示）：
函數vertices(g)得到g中所有頂點的集合。
謂詞not_adjacent_with_set(v,group,g)檢查頂點v與頂點集group中各頂點在圖g中是否有邊連接配接。
假設有了圖結構及其操作，程式實作就不難了。下面是一個程式（算法）：
這個算法實際上已經是一個python函數，能對任何一個圖算出頂點分組。其中欠缺的細節就是圖的表示，以及函數裡涉及的兩個圖操作。
完成了工作并不是結束。任何時候完成了一個算法或者程式，都應該回過頭去仔細檢查做出的結果，考慮其中有沒有問題。做出了一個圖着色程式，傳遞給它一個沖突圖，它将傳回一個分組的集合。現在應該回過頭進一步認真考慮工作中遇到的各種情況和問題，包括一些前面沒有關注的情況。
解唯一嗎？
首先，可以看到，對于給定的交叉路口執行個體，可行的分組可能不唯一。除了前面幾次提到的每個方向獨立成組的平凡解之外，完全可能找到一些與前面給出的解的分組數相同的解。對前面問題執行個體，下面是另一種滿足要求的分組：
{ab, eb, ec}, {ac, ad, bc}, {ba, bd, db, ed}, {da, dc, ea}
讀者不難驗證這一分組确實是該問題執行個體的解。
算法給出的解是确定的，依賴于算法中選擇頂點的具體政策，以及對圖中頂點的周遊順序，即list(verts)給出的頂點序列中的順序。
求解算法和原問題的關系
回顧前面從問題出發最終做出一個python程式的工作過程：
1.有關工作開始于交叉路口的抽象圖示，首先枚舉出所有允許通行方向；
2.根據通行方向和有關不同方向沖突的定義，畫出沖突圖；
3.把通行方向的分組問題歸結為沖突圖中不相鄰頂點的劃分問題，用求出不相鄰頂點的分組作為交叉路口中可以同時通行的方向分組。
問題是，這樣得到的結果滿足原交叉路口問題執行個體的需要嗎？
仔細分析可以看到，上面算法中采用的定義不統一：算法給出的結果是行駛方向的一種劃分（各分組互不相交，每個頂點隻屬于一個分組）；而工作開始考慮安全分組時，隻要求同屬一組的頂點（行駛方向）是互不沖突的。也就是說，原問題允許一個行駛方向屬于不同分組的情況（現實情況也是這樣，可能某個行駛方向在多種情況下都是綠燈。典型的例子如無害的右轉彎）。出現分組不相交的情況，原因是在建構新分組時一旦選擇了某個頂點，就将其從未分組頂點集中删除，這樣就産生了劃分的效果。
要回到求解之前的考慮，并不一定要推翻得到的算法，也可能在原算法上調整。例如，對于圖1.2的交叉路口執行個體，前面算法給出：
将分組盡可能擴充，加入與已有成員不沖突的方向，得到：
{ab, ac, ad, ba, dc, ed}, {bc, bd, ea, ba, dc, ed},
{da, db, ba, dc, ed, ad}, {ea, eb, ba, dc, ed, ea}
根據前面的定義，這樣得到的各分組仍然是安全的，請讀者檢查。如何修改前面算法，使之能給出這樣分組的問題留給讀者考慮。
另一個問題前面已有所讨論，就是沖突概念的定義問題。前面采用行駛方向交叉作為不安全情況的定義，這隻是一種合理選擇。另外的情況是否看作沖突，可能存在不同考慮。如前面提到的直行與旁邊道路的右轉問題（例如，在允許bd方向的情況下，是否允許ad和ed）。對同一個路口，如果沖突的定義不同，做出的沖突圖就會不同。實際定義可能需要反映交管部門對具體路口實際情況的考量，需要根據具體情況确定。
還有許多實際問題在前面算法中都沒有考慮。例如，在用于控制交叉路口的紅綠燈時，得到的行駛方向分組應該按怎樣的順序循環更替？這裡能不能有一些排程的原則，能不能通過算法得出結果？另一些問題更實際，可能更難通過計算機處理。例如各個分組綠燈持續的時間，這裡牽涉到公平性、實際需要等。可能還有其他問題。
從以上讨論中可以看到，前面工作中從問題出發逐漸抽象，得到的算法處理的問題與原問題已經有了很大的距離。該算法的輸入是經過人工分析和加工而得到的沖突圖，做出沖突圖需要确定沖突的定義，是人為的一步。考慮實際需要的紅綠燈排程，該算法産生的結果也缺乏許多資訊，真正運用到實際還需要人工做許多工作。
對于上面這些情況，在用計算機解決實際問題時經常可能看到。
本節的假設是希望做出一個程式，給它任意一個交叉路口的有關資訊，它能對該路口的可能行駛方向做出一種安全分組。經過仔細分析問題，考慮了一些情況，前面讨論已經給出了一種解決問題的方案（算法），并進一步精化，給出了另一個采用python語言形式描述的“函數定義”。但這還不是一個可以運作的程式。
python是一種比較進階的語言，提供了許多進階的資料類型和相關操作。針對這個算法，python語言的集合和相關操作可以直接使用。但算法中的一些功能是python語言沒有的，主要是缺少圖結構及若幹相關操作。如果設法在python語言裡實作圖結構及所需操作，這個“算法”就變成了一個可以運作的實際程式。
另一些程式設計語言沒有進階的資料類型，隻提供了很少的一組基本類型和幾種資料組合機制。c語言就是這樣，隻有幾個類型和數組、結構、指針等低級組合機制。要在c語言裡實作上述算法，就需要自己實作集合、圖及相關操作。
在解決各種問題的程式裡，經常要用到諸如集合、圖等複雜的資料結構，用于表達計算中獲得、構造和處理的複雜資訊。了解這類進階結構的各方面性質，在程式設計語言裡有效實作它們，是本書後面章節中讨論的主要問題。對于提供了一些進階資料結構的python語言，本書還将介紹這些結構的性質和合理使用方法。