Old question

Set Elements
A {502, 510, 972, 1444}
B {37, 721, 972, 1444}
C {37, 502, 972, 1444}
D {721, 836}
E {510, 671}
F {671, 836}
原來我主要的目的，是要找出可以從點A再次回到點A的路徑是否存在。

我將上表整理成...若有共同的element表示可以相連
A → B C E
B → A C D
C → A B
D → B F
E → A F
F → D E

鄰接矩陣M為
1 1 1 0 1 0
1 1 1 1 0 0
1 1 1 0 0 0
0 1 0 1 0 1
1 0 0 0 1 1
0 0 0 1 1 1


本想透過Transitive closure的方式，但是他試用於有向圖，如果用在無向圖可能會有A→A的問題。
因此當M^3以後，所有的element均為1，無法用來判斷是否有cycle

不知道是否有其他的演算法可以找出從點p出發，是否存在cycle？以及cycle的路徑為何？

謝謝

編輯記錄

可以請問一下，這是用來作什麼用的呢？
看題目似乎有趣，但可以用來作什麼呢？好好奇喔。
鄰接矩陣M 有什麼用途？

------
http://www.ViewMove.com

 因為我看書：

1. M^2代表走兩步可以到達哪些點....M^n代表走n步可以到達哪些點....如果矩陣內容表示是否有相連(0或1)
2. 同樣的，如果矩陣內容為相乘的結果(非只是0或1)，例如M^2中的( i , j ) = k 表示，從 i 到 j 會有k條路徑(可能會包含 i 到 i 再到 j 這種路徑)。

我最主要的目的只是要求出這個圖形中是否包含path length > 3的cycle，或者是最長的cycle為何。

本來是想透過窮舉的方式，今天翻了DS跟Algorithm的書，找到在directed graph的方法，但是用在undirected graph會有問題。

因此，到這邊問問看是否有人看過其他的方法。大家互相討論吧

您的 鄰接矩陣 與別人的不太一樣耶...
看看維基百科： 鄰接矩陣 其中

void DFS(MGraph G,int v)
{ /* 從第v個頂點出發遞歸地深度優先遍歷圖G。演算法7.5 */

可能看一下英文的 Adjacency matrix 會比較準一些。

只是在應用上可以用在什麼上呢？
還是只是算數學？

------
http://www.ViewMove.com

耶....他的鄰接矩陣的定義是如果有相連，則為1，否則為0....跟我的應該是一樣的。

我是運用在sensor上，有點類似路徑規劃，也不能說是在算數學，畢竟數學部分好像只有矩陣乘法(說不定用不到)，主要還是graph，一下子要我找出相關的也不知道怎麼找。

查到的資料都是用在有向圖，無向圖目前還沒看到....

它是自己對自己是 0 喔, 而您的是 1 主要是這點不同。
以您整理的關係：
A → B C E
B → A C D
C → A B
D → B F
E → A F
F → D E

鄰接矩陣M 應為
0 1 1 0 1 0
1 0 1 1 0 0
1 1 0 0 0 0
0 1 0 0 0 1
1 0 0 0 0 1
0 0 0 1 1 0
由維基百科：http://en.wikipedia.org/wiki/Adjacency_matrix
the adjacency matrix of a finite directed or undirected graph G on n vertices is the n × n matrix where the nondiagonal entry a_ij is the number of edges from vertex i to vertex j, and the diagonal entry a_ii is either twice the number of loops at vertex i or just the number of loops
表示 aii 是自己連到自己的 loop 個數的 1 倍或 2 倍數，但在您的表內，並沒有自己到自己，所以是 0

另一個參考資料：Spectral Graph Theory and its Applications
提到 Lecture 6. Random walks on expanders
若由 A 出發則 p0 為
1
0
0
0
0
0

p1 = M x p0 表示由 A 出發下一點的位置 (即 B,C,E)

0 1 1 0 1 0 1 0
1 0 1 1 0 0 0 1
1 1 0 0 0 0 0 1
0 1 0 0 0 1 0 0
1 0 0 0 0 1 0 1
0 0 0 1 1 0 0 0

p2 = M x p1 = M x M x p0 表示由 A 出發走 2 步的位置 (A,B,C,D,F)

0 1 1 0 1 0 0 3
1 0 1 1 0 0 1 1
1 1 0 0 0 0 1 1
0 1 0 0 0 1 0 1
1 0 0 0 0 1 1 0
0 0 0 1 1 0 0 1

其中，A 位置 3 表示走到第 2 步就有 3 條可走回 A (即 ABA, ACA, AEA)

p3 = M x p2 = M x M x p1 = M x M x M x p0

0 1 1 0 1 0 3 2
1 0 1 1 0 0 1 5
1 1 0 0 0 0 1 4
0 1 0 0 0 1 1 2
1 0 0 0 0 1 0 4
0 0 0 1 1 0 1 1

其中，A 位置 2 表示走到第 3 步就有 2 條可走回 A
這樣的運算，還是要保留每次的結果才知道路徑，只留最後的結果，應該無法知道路徑。

------
http://www.ViewMove.com

真的耶...沒注意看...因為我想說A也可以回到A，所以才一直以為是1

如果要列出所有可能，在執行過程，每當有backtracking，就認定該路經已經完成，並退到前一步驟繼續，這邊就要把前面的路徑也加上來....不然就會像是DFS跑出來的結果：ABCDFE


感覺上，要有兩個stack，S1及S2...第一個是原本DFS的stack，另一個紀錄從第一個pop出來的element，當要往前退一步的時候，就把S2的第一個值pop到S1.....

詳細的步驟我等等再想想...

topic.csdn.net/t/20020901/19/987755.html

<textarea class="cpp" rows="10" cols="60" name="code">const int MAX_N = 100; //最多的節點數 const char* INPUT_FILE = "Graph.txt"; struct Graph { int NodeCount; //節點數目 int AdjMatrix[MAX_N][MAX_N]; // 鄰接矩陣,如果圖中i,j相鄰，則 G[i][j]>0，否則 G[i][j]=0 }; //--------------------------------------------------------------------------- typedef int Path[MAX_N]; // 儲存路徑 typedef bool Marking[MAX_N]; //--------------------------------------------------------------------------- void PrintPath(Path& path, int length) { for(int i=0;iMemo1->Lines->Text=Form1->Memo1->Lines->Text IntToStr(path[i]) " "; Form1->Memo1->Lines->Add(""); } //--------------------------------------------------------------------------- void SearchAllPath(const Graph& G, Path& path, Marking& visited, int v, int des, int length) { if(visited[v]) return; path[length-1] = v; if(v==des) PrintPath(path, length); else { visited[v] = true; for(int i = 0; i < G.NodeCount; i ) if(G.AdjMatrix[v][i] != 0 && !visited[i]) SearchAllPath(G, path, visited, i, des, length 1); visited[v] = false; } } //--------------------------------------------------------------------------- void ReadData(Graph& G, int& src, int& des) //讀入資料 { ifstream fin(INPUT_FILE); G.NodeCount=6; for(int i = 0; i < G.NodeCount; i ) for(int j = 0; j < G.NodeCount; j ) fin >> G.AdjMatrix[i][j]; } //--------------------------------------------------------------------------- main() { Graph G; int src=0, des=1; // 起點和終點 Path path; // 儲存路徑 Marking visited; // 訪問標記 ReadData(G, src, des); //讀入檔案 for (int i = 0; i < G.NodeCount; i ) visited[i] = false; // 初始化 SearchAllPath(G, path, visited, src, des, 1); }</textarea>

一直忘了回覆，我查閱以前的資料結構課本，上面寫說...對角線是0或1看自己的需求，所以0或1都是對的...


===================引 用 dllee 文 章===================
它是自己對自己是 0 喔, 而您的是 1 主要是這點不同。
以您整理的關係：
A → B C E
B → A C D
C → A B
D → B F
E → A F
F → D E

鄰接矩陣M 應為
0 1 1 0 1 0
1 0 1 1 0 0
1 1 0 0 0 0
0 1 0 0 0 1
1 0 0 0 0 1
0 0 0 1 1 0