解析關於有向圖的輸入

Question

我正在解決一個我遇到輕微延遲的問題。我正在使用有向圖，並試圖確定在某個輸入內是否存在到達那裏的路線。現在我的問題是，我必須在一個字符串中輸入輸入，但它必須按照抽出重要信息的方式進行解析。例如：

你有其中G是向圖，從S到T（節點）

我的輸入字符串將是一個路徑的問題，比如：（1,2,3,4,5 ），（（1,2），（1,3），（2,3），（2,4），（3,2），（3,5），（4,3），（5,2） ），1,5

第一組圓括號代表節點，第二組代表圖的組成和路線，其中數字1代表s，而5代表t（最後兩個數字）結束）。

我必須實現一個程序來確定路徑是否存在。問題在於解析。我需要提取節點列表（第一個括號），邊緣列表（第二個集合），起始節點（1）和結束節點（5）。

任何人都可以提供一些關於如何解析這些和他們在這樣的方式，我可以提取和打印出這些方面的見解嗎？我不想以任何方式尋找完整的書面工作程序，只是澄清，也許代碼片段指向正確的方向。任何幫助將不勝感激。

Answer 1

如果我們假設輸入將嚴格遵循您提供的格式，那麼這只是一個解析問題。這是你如何得到三大塊（頂點，邊和st）。

String input=" (1,2,3,4,5),((1,2),(1,3),(2,3),(2,4),(3,2),(3,5),(4,3),(5,2)),1,5"; 

String nodes=input.substring(0, input.indexOf("((")-1).trim(); 
String edges=input.substring(input.indexOf("((")+1, input.indexOf("))")+1).trim(); 
String st=input.substring(input.indexOf("))")+3).trim(); 

然後，您可以單獨解析每個塊並獲取其值。有一件事：邊界列表足以定義圖形（你真的不需要第一個塊）。

編輯： 您可以簡單地初始化一個大小等於頂點數的布爾數組visited[]。最初，所有的頂點都沒有被訪問。