『壹』 已知有向圖的鄰接表存儲結構如下圖所示
深度優先是從某個頂點出發，訪問完後，尋找一個未訪問的鄰接頂點繼續深度優先，如果此路不同就往回退，所以看鄰接表，首先訪問V1，完了後順鏈尋找沒有訪問的鄰接頂點，自然鏈表中的第一個結點就是v3，接著轉到v3再來深度優先，訪問v3後，在其鏈表中第一個鄰接頂點是v4
接著訪問v4，下面走不通，回到v3，繼續順鏈往後，自然是v5，v5的鄰接頂點中v2還沒有訪問
所以序列為v1, v3, v4, v5, v2
再看廣度優先，從某個頂點完成後，需要一口氣將其鄰接未訪問的所有頂點都訪問，後面類推
於是過程是先v1，再順鏈將v3，v2依次訪問完，然後再依次訪問v3和v2的各個未訪問鄰接頂點，v3鏈表中順鏈可以訪問v4，v5，所以最後訪問序列為v1, v3, v2, v4, v5
『貳』 求演算法！！用傳遞閉包來操作 BFS判斷鄰接表存儲有向圖G中頂點i到頂點j是否有路徑
int exist_path_BFS(AdjGraph G,int i,int j)//廣度優先判斷有向圖G中頂點i到頂點j是否有路徑,是則返回1,否則返回0 { int visited[MAXSIZE]; InitQueue(Q); EnQueue(Q,i); while(!QueueEmpty(Q)) //隊列不空時循環 { DeQueue(Q,u); visited=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(k==j) return 1; if(!visited[k]) EnQueue(Q,k); }//for }//while return 0; }//exist_path_BFS 這個是普通實現，求傳遞閉包的解法，謝謝
『叄』 判斷用鄰接表存儲的有向圖G是否存在迴路的演算法，答案給的這個看不懂，哪位大佬給注釋一下
因此要在多個鄰接頂點之間約定一種訪問次序。@由於圖中可能存在迴路，在訪問某個頂點之後，可能沿著某條路徑又回到圖的深度優先搜索遍歷演算法p88 聯通的無迴路的無向圖，簡稱樹。樹中的懸掛點又成為樹葉，其他頂點稱為分支點
『肆』 編寫一個程序,判別以鄰接表方式的存儲有向圖G中是否存在由頂點Vi到頂點Vj的路徑(i!=j)
int visited[MAXSIZE]; //指示頂點是否在當前路徑上
int exist_path_DFS(ALGraph G,int i,int j)//深度優先判斷有向圖G中頂點i到頂點j是否有路徑,是則返回1,否則返回0
{
if(i==j) return 1; //i就是j
else
{
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(!visited[k]&&exist_path(k,j)) return 1;//i下游的頂點到j有路徑
}//for
}//else
}//exist_path_DFS
void find(int A[][],int m,int n)//求矩陣A中的馬鞍點
{
int i,j,min,flag;
for(i=0;i<m;i++)
{
for(min=A[i][0],j=0;j<n;j++)
if(A[i][j]<min) min=A[i][j]; //求一行中的最小值
for(j=0;j<n;j++)
if(A[i][j]==min) //判斷最小值是否是馬鞍點
{
for(flag=1,k=0;k<m;k++)
if(min<A[k][j]) flag=0;
if(flag)
printf("%d",A[i][j]);
}
}
}
void Merge(LinkList &A,LinkList &B,LinkList &C) //假設是遞增序列
{
LinkList p,q,r;
p=A->next;
q=B->next;
r=C=A;
while(p&&q)
{
if(p->data<q->data)
{
r->next=p;
r=r->next;
p=p->next;
}
else
{
r->next=q;
r=r->next;
q=q->next;
}
}
r->next=(p!=NULL?p:q);
free(B);
}
『伍』 對於無向圖的鄰接矩陣存儲結構，判斷是否有迴路
鄰接矩陣的話，從一個點出發（假設a）看它與哪個節點（假設b）有路徑，那麼再接著看b與誰有路，挨個試完以後，如果又回到了a，那就構成了一條迴路。
『陸』 怎麼寫一個演算法確定一個有N個頂點的有向圖是否包含迴路，此演算法時間的代價應該是O（n）,要用C來寫
對於這個題目我們可以用DFS來做，每當訪問當前節點的鄰接表時，如果存在某個鄰接的元素已被標記為訪問狀態，那麼這個圖就是存在迴路的。
『柒』 鄰接表 判斷有向圖是否有環 python
鄰接表還是逆鄰接表看如果是逆鄰接表，每個頂點出發鄰接表的鏈表中的結點個數就是入度
如果是鄰接表過程如下：
有一個輔助數組，大小就是頂點數量，所有元素初值都為0
從頭到尾遍歷每個頂點出發的鄰接表的結點，只要當前結點的數據是幾（也就是第幾個結點被有向弧進入了），這個下標的輔助數組元素加1，等所有的鄰接表的小鏈表遍歷完了，這個輔助數組中各個下標的數字就是該頂點的入度
『捌』 如何判斷有向圖中是否存在環
解法一：深度遍歷
假設圖以鄰接矩陣表示，一條深度遍歷路線中如果有結點被第二次訪問到，那麼有環。我們用一個變數來標記某結點的訪問狀態（未訪問，訪問過，其後結點都被訪問過），然後判斷每一個結點的深度遍歷路線即可。
因為採用鄰接矩陣存儲，一般至少需要將矩陣中元素的一半給過一下，由於矩陣元素個數為n^2， 因此時間復雜度就是O(n^2)。如果採用鄰接表存儲，則只存儲了邊結點(e條邊，無向圖是2e條邊)，加上表頭結點為n（也就是頂點個數），因此時間復雜度為O(n+e)。
解法二：拓撲排序
方法是重復尋找一個入度為0的頂點，將該頂點從圖中刪除（即放進一個隊列里存著，這個隊列的順序就是最後的拓撲排序，具體見程序），並將該結點及其所有的出邊從圖中刪除（即該結點指向的結點的入度減1），最終若圖中全為入度為1的點，則這些點至少組成一個迴路。
採用鄰接矩陣存儲時，遍歷二維數組，求各頂點入度的時間復雜度是O(n^2)。 遍歷所有結點，找出入度為0的結點的時間復雜度是O(n)。對於n個入度為0的結點，刪除他們的出邊的復雜度為O(n^2)。 所以總的復雜度為O(n^2)。
對於鄰接表，遍歷所有邊，求各頂點入度的時間復雜度是O(e)，即邊的個數。遍歷所有結點，找出入度為0的結點的時間復雜度是O(n)，即頂點的個數。遍歷所有邊，刪除入度為0的結點的出邊的復雜度為O(e)，即邊的個數。所以總的時間復雜度是O(n+e)。
『玖』 怎麼用深度遍歷判斷有向圖是否有環
圖用鄰接矩陣表示。用回溯法實現非遞歸深度優先遍歷圖，如果是無向圖，則遍歷時只看上三角，如果是有向圖，則不加限制。遍歷時，如果遇到了之前訪問過的結點，則圖中存在環。
『拾』 此程序為判斷以鄰接表方式存儲的有向圖中是否存在有vi到Vj的路徑，請大蝦們幫我改正一下，最好寫出正確程序
10分- -直接懶得看，，