無向圖遍歷演算法

1. 輸出無向圖的所有深度優先遍歷序列，求代碼

每個節點設置一個記錄表,記錄當次遍歷,各個邊的訪問順序.這個訪問順序決定了遍歷序列的不同.每次回溯之後,重新排列這個表(其實是全排列),對這個節點進行重新遍歷.除非這個節點的訪問表已經嘗試了所有的全排列,則繼續回溯.

2. 數據結構C++無向圖的鄰接矩陣深度優先遍歷,求解答

你能不能給貼上一個深度遍歷錯誤的用例？你這個輸入用例的結果就是1，2，3，4
現在能看出來的就是這個了，
int LocateVex (MGraph G,VertexType v){
int i;
for(i = 0;i<G.vexnum;i++)
if(G.vexs[i] == v){ //這里應該是等於v，而不是等於i
return i;
}
return -1;
}

3. 無向圖的深度優先遍歷怎麼做

#include<stdio.h>
#define n 5
int a[10]={0};
int top=0;//定義堆棧
int main()
{
void dfs(int (*edge)[n],int *status);
int edge[n][n]={{0,0,1,1,0},{0,0,0,0,1},{1,0,0,0,0},{1,0,0,0,1},{0,1,0,1,0}};//臨接矩陣表示的圖
int status[n]={0};//每個點的狀態，有沒有被訪問
int i=0,j=0;
// for(i=0;i<n;i++)
// for(j=0;j<n;j++)
// scanf("%d",&edge[i][j]);
dfs(edge,status);
return 0;
}
void dfs(int (*edge)[n],int *status)//遍歷
{
int k=0,j=0;
while(top>=0)
{
// for(i=0;i<n;i++)
// {
if(status[k]==0)
{
top++;
a[top]=k;
// b[count++]=k;
printf("%d",k);
status[k]=1;
}
while(j<n)
{
// for(j=0;j<n;j++)
if(edge[k][j]==1)
{
if(status[j]==0)
{
top++;
a[top]=j;
// b[count++]=k;
printf("%5d",j);
status[j]=1;
k=j;
j=0;
}
else
j++;
}
else
j++;
}
top-=1;
k=a[top];
j=0;
}
}

這個是非遞歸的，
#include<stdio.h>
#define n 5
int main()
{
void dft(int (*edge)[n],int *status);
int i=0,j=0;
int edge[n][n]={0};
int status[n]={0};
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&edge[i][j]);
dft(edge,status);
return 0;
}
void dft(int (*edge)[n],int *status)
{
void dftcore(int (*edge)[n],int *status,int i);
int i=0;
for(i=0;i<n;i++)
dftcore(edge,status,i);
}
void dftcore(int (*edge)[n],int *status,int i)
{
int j=0;
if(status[i]==1)
return;
printf("%5d",i);
status[i]=1;
for(j=0;j<n;j++)
if(edge[i][j]==1)
dftcore(edge,status,j);
}
這個遞歸的

4. 有誰幫忙解釋一下 有向圖和無向圖遍歷的區別 謝謝各位

若圖中的每條邊都是有方向的，則稱為有向圖。有向圖中的邊是由兩個頂點組成的有序對，有序對通常用尖括弧表示，如
<vi,vj>表示一條有向邊，其中vi是邊的始點，vj是邊的終點。<vi,vj>和<vj,vi>代表兩條不同的有向邊。

5. 有向圖的遍歷演算法和無向圖一樣嗎

看下演算法導論，那裡面用的頂點染色，對有向圖、無向圖處理是一樣的。

6. 已知有N個結點的無向圖，採用鄰接表結構存儲，要求編寫演算法實現廣度優先搜索策略遍歷圖中所有頂點。

//按廣度優先非遞歸遍歷圖G。使用輔助隊列Q和訪問標志數組visited.僅適用於鄰接表結構
void BFSTraverse1(ALGraph G,void(* Visit)(char *))
{
int v,u;
ArcNode * p;//p指向表結點
LinkQueue Q;//鏈隊列類型
for (v=0; v<G.vexnum; ++v)
{
visited[v] = FALSE;//置初值為未被訪問
}
InitQueue(&Q);//初始化輔助隊列Q
for (v=0; v<G.vexnum; ++v)//如果是連通圖，只v=0就遍歷全圖
{
if (! visited[v])//v尚未被訪問
{
visited[v] = TRUE;//設v為已被訪問
Visit(G.vertices[v].data);//訪問v
EnQueue(&Q,v);//v入隊
while (! QueueEmpty(Q))//隊列不空
{
DeQueue(&Q,&u);//隊頭元素出隊並置為u
for (p=G.vertices[u].firstarc; p; p=p->next)//p依次指向u的鄰接頂點
{
if (! visited[p->data.adjvex])//u的鄰接頂點尚未被訪問
{
visited[p->data.adjvex] = TRUE;//該鄰接頂點設為已被訪問
Visit(G.vertices[p->data.adjvex].data);//訪問該鄰接頂點
EnQueue(&Q,p->data.adjvex);//入隊該鄰接頂點序號
}
}
}//while
}//if
}//for(v=......)
printf("\n");
}

7. 圖的圖的遍歷

常見的圖遍歷方式有兩種：深度優先遍歷和廣度優先遍歷，這兩種遍歷方式對有向圖和無向圖均適用。 深度優先遍歷的思想類似於樹的先序遍歷。其遍歷過程可以描述為：從圖中某個頂點v出發，訪問該頂點，然後依次從v的未被訪問的鄰接點出發繼續深度優先遍歷圖中的其餘頂點，直至圖中所有與v有路徑相通的頂點都被訪問完為止。
深度優先遍歷演算法實現：
為了便於在演算法中區分頂點是否已被訪問過，需要創建一個一維數組visited[0..n-1]（n是圖中頂點的數目），用來設置訪問標志，其初始值visited（0≤i≤n-1）為"0"，表示鄰接表中下標值為i的頂點沒有被訪問過，一旦該頂點被訪問，將visited置成"1"。
int visited[0..n-1]={0,0,...0};
void DFS(AdjList adj,int v)
{//v是遍歷起始點的在鄰接表中的下標值，其下標從0開始
visited[v]=1; visited(adj[v].elem);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) DFS(adj,w->adjvex);
}
對於無向圖，這個演算法可以遍歷到v頂點所在的連通分量中的所有頂點，而與v頂點不在一個連通分量中的所有頂點遍歷不到；而對於有向圖可以遍歷到起始頂點v能夠到達的所有頂點。若希望遍歷到圖中的所有頂點，就需要在上述深度優先遍歷演算法的基礎上，增加對每個頂點訪問狀態的檢測： intvisited[0..n-1]={0,0,...0};voidDFSTraverse(AdjListadj){for(v=0;v<n;v++)if(!visited[v])DFS(adj,v);} 對圖的廣度優先遍歷方法描述為：從圖中某個頂點v出發，在訪問該頂點v之後，依次訪問v的所有未被訪問過的鄰接點，然後再訪問每個鄰接點的鄰接點，且訪問順序應保持先被訪問的頂點其鄰接點也優先被訪問，直到圖中的所有頂點都被訪問為止。下面是對一個無向圖進行廣度優先遍歷的過程。
下面我們討論一下實現廣度優先遍歷演算法需要考慮的幾個問題：
（1）在廣度優先遍歷中，要求先被訪問的頂點其鄰接點也被優先訪問，因此，必須對每個頂點的訪問順序進行記錄，以便後面按此順序訪問各頂點的鄰接點。應利用一個隊列結構記錄頂點訪問順序，就可以利用隊列結構的操作特點，將訪問的每個頂點入隊，然後，再依次出隊，並訪問它們的鄰接點；
（2）在廣度優先遍歷過程中同深度優先遍歷一樣，為了避免重復訪問某個頂點，也需要創建一個一維數組visited[0..n-1]（n是圖中頂點的數目），用來記錄每個頂點是否已經被訪問過。
int visited[0..n-1]={0,0,...0};
void BFS(AdjList adj,int v)
{//v是遍歷起始點在鄰接表中的下標，鄰接表中下標從0開始
InitQueue(Q); //Q是隊列
visited[v]=1; visite(adj[v].elem); EnQueue(Q,v);
while (!QueueEmpty(Q)) {
DeQueue(Q,v);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) {
visited[w->adjvex]=1;
visite(adj[w->adjvex].elem);
EnQueue(Q,w->adjvex); }
}
}

8. 無向圖中查找環的演算法有哪些

比較直觀的辦法是，從初始結點 S 開始，用深度優先的方法遍歷圖的結點，如果在這個過程中，你遇到了一個先前就已經發現過的結點（假定它叫 V），說明存在一個環。
如果你想輸出這個環，那麼就從 V 沿路返回，直到又遇到 V，途中經過的所有結點就組成了這個環。

9. 我想問一下 圖的遍歷兩種方法DFS和BFS作用域有向圖和無向圖有什麼區別，例如如果是同一個結構的圖就是上面

結果肯定不一樣的
可以通過鏈表實現，一個點作為起點的話，箭頭指向的點就作為鏈表連接的下一個節點，依次直到最後一個點沒有指向的點了
也可以通過數組實現，把圖的所有點之間的聯系做成一個矩陣，假如是10個點，就做一個10*10的矩陣數組a[10][10]，a[m][n]表示由m點指向n點，如果沒有連接設置a[m][n]=0，如果是n指向m就把a[m][n]設置為一個比較大的數，如果是m指向n就設置為m到n的距離。而a[n][m]也要設置一下，這就是有向圖的a[m][n]和a[n][m]是不同的
思路大概是這樣的，都寫了好久了，你要需要的話，我可以發個源碼給你參考，你可以留郵箱