遍歷演算法求向有權圖

① 求一個有向圖圖遍歷的演算法

static int countOfWays = 0;
int traverseForNum(vertex* sourceBuf, vertex* targetBuf){
int i = 0;
if (sourceBuf->searched){
return 1; /* already searched */
}else{ /* not searched yet */
sourceBuf->searched = 1;
for ( i = 0; i < sourceBuf->numOfGoing; i ++ ){
if(sourceBuf->goingVertex->[i] == targetBuf){
countOfWays ++;
}
}
for ( i = 0; i < sourceBuf->numOfGoing; i ++ ){
if(sourceBuf->goingVertex->[i] != targetBuf){
traverseForNum(sourceBuf->goingVertex[i]), targetBuf);
}
}
}
return 1;
}

如下是頂點的定義：
typedef struct buf vertex;
struct buf{
vertex **goingVertex; /* vertex out the current */
vertex **comingVertex; /* vertex into the current */
int numOfGoing; /* count of vertex going list */
int numOfComing; /* count of vertex coming list */
int searched; /* flag used to search for the graph */

};

代碼我以前調試過，完全OK。
但是你給我的這個題目，我是基於以前的代碼給你修改的，C99下即使調試不通過問題也不太大，你稍微修改一下就好。但是我有需要說明的：這個是做出你問的第一個問題的答案；第二個問題，我想可能跟乘法定律有關，可以用j到i的路徑數目乘以i到k的路徑數目，演算法我想了一下，如果非要用一個遍歷作出來，還真要花點兒時間，還不一定最優。

② 求有權無向圖的DFS演算法

深度優先遍歷類似於樹的先序遍歷，俗稱一條路走到黑，然後再考慮回溯的問題，回溯到最近訪問的頂點並看它是否還有相鄰頂點未訪問，若無繼續往前回溯。

我下面寫寫核心偽代碼，其他諸如圖的類型定義、還有你要對每個結點做的具體操作（我在代碼中用visit()函數來代替了，具體做啥操作根據題目來）我就不寫了。
bool visited[MSX_VERTEX_NUM]; //標記訪問數組
void DFS_Traverse(Grath G) //對圖G進行DFS
{
for(v=0;v<G.vexnum;++v)

{
visited[v]=false; //初始化已訪問標記數據

}
for(v=0;v<G.vexnum;++v) //假設從v=0開始遍歷

{
if(!visited[v])

DFS(G,v);

}

}
void DFS(Graph G,int v) //從頂點v出發，用遞歸的思想，深度優先遍歷
{
visit(v); //這里的visit()就是對頂點v的具體操作，題目是啥就自己寫啥

visited[v]=true; //標記已訪問

for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))

//從最近結點開始，依次找相鄰結點
{
if(!visited[w]) //w為還未訪問的相鄰結點

{
DFS(G,w);

}
}
}

③ 無向有權的圖的深度、廣度優先遍歷怎麼做的啊，他的遍歷序列怎麼求呢

總結深度優先與廣度優先的區別
1、區別

1） 二叉樹的深度優先遍歷的非遞歸的通用做法是採用棧，廣度優先遍歷的非遞歸的通用做法是採用隊列。

2） 深度優先遍歷：對每一個可能的分支路徑深入到不能再深入為止，而且每個結點只能訪問一次。要特別注意的是，二叉樹的深度優先遍歷比較特殊，可以細分為先序遍歷、中序遍歷、後序遍歷。具體說明如下：

先序遍歷：對任一子樹，先訪問根，然後遍歷其左子樹，最後遍歷其右子樹。
中序遍歷：對任一子樹，先遍歷其左子樹，然後訪問根，最後遍歷其右子樹。
後序遍歷：對任一子樹，先遍歷其左子樹，然後遍歷其右子樹，最後訪問根。
廣度優先遍歷：又叫層次遍歷，從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結點，訪問完一層就進入下一層，直到沒有結點可以訪問為止。

3）深度優先搜素演算法：不全部保留結點，佔用空間少；有回溯操作(即有入棧、出棧操作)，運行速度慢。

廣度優先搜索演算法：保留全部結點，佔用空間大； 無回溯操作(即無入棧、出棧操作)，運行速度快。

④ 數據結構課程設計題目，圖的建立以及遍歷。

//圖的遍歷演算法程序

//圖的遍歷是指按某條搜索路徑訪問圖中每個結點，使得每個結點均被訪問一次，而且僅被訪問一次。圖的遍歷有深度遍歷演算法和廣度遍歷演算法，程序如下：
#include <iostream>
//#include <malloc.h>
#define INFINITY 32767
#define MAX_VEX 20 //最大頂點個數
#define QUEUE_SIZE (MAX_VEX+1) //隊列長度
using namespace std;
bool *visited; //訪問標志數組
//圖的鄰接矩陣存儲結構
typedef struct{
char *vexs; //頂點向量
int arcs[MAX_VEX][MAX_VEX]; //鄰接矩陣
int vexnum,arcnum; //圖的當前頂譽指點數和弧數
}Graph;
//隊列類
class Queue{
public:
void InitQueue(){
base=(int *)malloc(QUEUE_SIZE*sizeof(int));
front=rear=0;
}
void EnQueue(int e){
base[rear]=e;
rear=(rear+1)%QUEUE_SIZE;
}
void DeQueue(int &e){
e=base[front];
front=(front+1)%QUEUE_SIZE;
}
public:
int *base;
int front;
int rear;
};
//圖G中查找元素c的位肢橡置
int Locate(Graph G,char c){
for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==c) return i;
return -1;
}
//創建無向網
void CreateUDN(Graph &G){
int i,j,w,s1,s2;
char a,b,temp;
printf("輸入頂點數和弧數:");
scanf("%d%d",&G.vexnum,&G.arcnum);
temp=getchar(); //接收回車
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配頂點數目
printf("輸入%d個頂點.\n",G.vexnum);
for(i=0;i<G.vexnum;i++){ //初始化頂點
printf("輸入頂點%d:",i);
scanf("%c",&G.vexs[i]);
temp=getchar(); //接收回車
}
for(i=0;i<G.vexnum;i++) //初始化鄰接矩陣
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("輸入%d條弧.\n",G.arcnum);
for(i=0;i<G.arcnum;i++){ //初始化弧
printf("輸入弧%d:",i);
scanf("%c %c %d",&a,&b,&w); //輸入一條邊依附的頂點和權值
temp=getchar(); //接收回車
s1=Locate(G,a);
s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w;
}
}
//圖G中頂點k的第一個鄰接頂點
int FirstVex(Graph G,int k){
if(k>=0 && k<G.vexnum){ //k合理
for(int i=0;i<G.vexnum;i++)
if(G.arcs[k][i]!=INFINITY) return i;
}
return -1;
}
//圖G中頂點i的第j個鄰接頂點的下一個鄰接頂點
int NextVex(Graph G,int i,int j){
if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理
for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k;
}
return -1;
}
//深度優先遍歷
void DFS(Graph G,int k){
int i;
if(k==-1){ //第一次執行DFS時,k為-1
for(i=0;i<G.vexnum;i++)
if(!visited[i]) DFS(G,i); //對尚未訪歷虛旁問的頂點調用DFS
}
else{
visited[k]=true;
printf("%c ",G.vexs[k]); //訪問第k個頂點
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); //對k的尚未訪問的鄰接頂點i遞歸調用DFS
}
}
//廣度優先遍歷
void BFS(Graph G){
int k;
Queue Q; //輔助隊列Q
Q.InitQueue();
for(int i=0;i<G.vexnum;i++)
if(!visited[i]){ //i尚未訪問
visited[i]=true;
printf("%c ",G.vexs[i]);
Q.EnQueue(i); //i入列
while(Q.front!=Q.rear){
Q.DeQueue(k); //隊頭元素出列並置為k
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]){ //w為k的尚未訪問的鄰接頂點
visited[w]=true;
printf("%c ",G.vexs[w]);
Q.EnQueue(w);
}
}
}
}

//主函數
void main(){
int i;
Graph G;
CreateUDN(G);
visited=(bool *)malloc(G.vexnum*sizeof(bool));
printf("\n廣度優先遍歷: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
DFS(G,-1);
printf("\n深度優先遍歷: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
BFS(G);
printf("\n程序結束.\n");
}
輸出結果為（紅色為鍵盤輸入的數據，權值都置為1）：
輸入頂點數和弧數:8 9
輸入8個頂點.
輸入頂點0:a
輸入頂點1:b
輸入頂點2:c
輸入頂點3:d
輸入頂點4:e
輸入頂點5:f
輸入頂點6:g
輸入頂點7:h
輸入9條弧.
輸入弧0:a b 1
輸入弧1:b d 1
輸入弧2:b e 1
輸入弧3:d h 1
輸入弧4:e h 1
輸入弧5:a c 1
輸入弧6:c f 1
輸入弧7:c g 1
輸入弧8:f g 1
廣度優先遍歷: a b d h e c f g
深度優先遍歷: a b c d e f g h
程序結束.

⑤ 圖的圖的遍歷

常見的圖遍歷方式有兩種：深度優先遍歷和廣度優先遍歷，這兩種遍歷方式對有向圖和無向圖均適用。 深度優先遍歷的思想類似於樹的先序遍歷。其遍歷過程可以描述為：從圖中某個頂點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); }
}
}

⑥ 數據結構 圖的遍歷 1．圖的遍歷的演示 2．實現圖的廣度，深度優先遍歷。<用鄰接表實現> 3．遞歸的方法實現

Status Build_AdjList(ALGraph &G)//輸入有向圖的頂點數,邊數,頂點信息和邊的信息建立鄰接表
{
InitALGraph(G);
scanf("%d",&v);
if(v<0) return ERROR; //頂點數不能為負
G.vexnum=v;
scanf("%d",&a);
if(a<0) return ERROR; //邊數不能為殲世負
G.arcnum=a;
for(m=0;m<v;m++)
G.vertices[m].data=getchar(); //輸入各頂點的符號
for(m=1;m<=a;m++)
{
t=getchar();h=getchar(); //t為弧尾,h為弧頭
if((i=LocateVex(G,t))<0) return ERROR;
if((j=LocateVex(G,h))<氏團肢0) return ERROR; //頂點未找到
p=(ArcNode*)malloc(sizeof(ArcNode));
if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p;
else
{
for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);
q->nextarc=p;
}
p->adjvex=j;p->nextarc=NULL;
}//while
return OK;
}//Build_AdjList
7.15
//本題中的圖G均為有向無權圖,其餘情況容易由此寫出
Status Insert_Vex(MGraph &G, char v)//在鄰接矩陣表示的圖G上插入頂點v
{
if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE;
G.vexs[++G.vexnum]=v;
return OK;
}//Insert_Vex
Status Insert_Arc(MGraph &G,char v,char w)//在鄰接矩陣表示的圖G上插入邊(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
if(i==j) return ERROR;
if(!G.arcs[i][j].adj)
{
G.arcs[i][j].adj=1;
G.arcnum++;
}
return OK;
}//Insert_Arc
Status Delete_Vex(MGraph &G,char v)//在鄰接矩陣表示的圖G上刪除頂點v
{
n=G.vexnum;
if((m=LocateVex(G,v))<0) return ERROR;
G.vexs[m]<->G.vexs[n]; //將待刪除頂點交換到最後一個頂點
for(i=0;i<n;i++)
{
G.arcs[i][m]=G.arcs[i][n];
G.arcs[m][i]=G.arcs[n][i]; //將邊的關系隨之交換
}
G.arcs[m][m].adj=0;
G.vexnum--;
return OK;
}//Delete_Vex
分析:如果不把待刪除頂點交換到最後或碰一個頂點的話,演算法將會比較復雜,而伴隨著大量元素的移動,時間復雜度也會大大增加.
Status Delete_Arc(MGraph &G,char v,char w)//在鄰接矩陣表示的圖G上刪除邊(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
if(G.arcs[i][j].adj)
{
G.arcs[i][j].adj=0;
G.arcnum--;
}
return OK;
}//Delete_Arc
7.16
//為節省篇幅,本題只給出Insert_Arc演算法.其餘演算法請自行寫出.
Status Insert_Arc(ALGraph &G,char v,char w)//在鄰接表表示的圖G上插入邊(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;p->nextarc=NULL;
if(!G.vertices[i].firstarc) G.vertices[i].firstarc=p;
else
{
for(q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc)
if(q->adjvex==j) return ERROR; //邊已經存在
q->nextarc=p;
}
G.arcnum++;
return OK;
}//Insert_Arc
7.17
//為節省篇幅,本題只給出較為復雜的Delete_Vex演算法.其餘演算法請自行寫出.
Status Delete_Vex(OLGraph &G,char v)//在十字鏈表表示的圖G上刪除頂點v
{
if((m=LocateVex(G,v))<0) return ERROR;
n=G.vexnum;
for(i=0;i<n;i++) //刪除所有以v為頭的邊
{
if(G.xlist[i].firstin->tailvex==m) //如果待刪除的邊是頭鏈上的第一個結點
{
q=G.xlist[i].firstin;
G.xlist[i].firstin=q->hlink;
free(q);G.arcnum--;
}
else //否則
{
for(p=G.xlist[i].firstin;p&&p->hlink->tailvex!=m;p=p->hlink);
if(p)
{
q=p->hlink;
p->hlink=q->hlink;
free(q);G.arcnum--;
}
}//else
}//for
for(i=0;i<n;i++) //刪除所有以v為尾的邊
{
if(G.xlist[i].firstout->headvex==m) //如果待刪除的邊是尾鏈上的第一個結點
{
q=G.xlist[i].firstout;
G.xlist[i].firstout=q->tlink;
free(q);G.arcnum--;
}
else //否則
{
for(p=G.xlist[i].firstout;p&&p->tlink->headvex!=m;p=p->tlink);
if(p)
{
q=p->tlink;
p->tlink=q->tlink;
free(q);G.arcnum--;
}
}//else
}//for
for(i=m;i<n;i++) //順次用結點m之後的頂點取代前一個頂點
{
G.xlist[i]=G.xlist[i+1]; //修改表頭向量
for(p=G.xlist[i].firstin;p;p=p->hlink)
p->headvex--;
for(p=G.xlist[i].firstout;p;p=p->tlink)
p->tailvex--; //修改各鏈中的頂點序號
}
G.vexnum--;
return OK;
}//Delete_Vex
7.18
//為節省篇幅,本題只給出Delete_Arc演算法.其餘演算法請自行寫出.
Status Delete_Arc(AMLGraph &G,char v,char w)////在鄰接多重表表示的圖G上刪除邊(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
if(G.adjmulist[i].firstedge->jvex==j)
G.adjmulist[i].firstedge=G.adjmulist[i].firstedge->ilink;
else
{
for(p=G.adjmulist[i].firstedge;p&&p->ilink->jvex!=j;p=p->ilink);
if (!p) return ERROR; //未找到
p->ilink=p->ilink->ilink;
} //在i鏈表中刪除該邊
if(G.adjmulist[j].firstedge->ivex==i)
G.adjmulist[j].firstedge=G.adjmulist[j].firstedge->jlink;
else
{
for(p=G.adjmulist[j].firstedge;p&&p->jlink->ivex!=i;p=p->jlink);
if (!p) return ERROR; //未找到
q=p->jlink;
p->jlink=q->jlink;
free(q);
} //在i鏈表中刪除該邊
G.arcnum--;
return OK;
}//Delete_Arc
7.19
Status Build_AdjMulist(AMLGraph &G)//輸入有向圖的頂點數,邊數,頂點信息和邊的信息建立鄰接多重表
{
InitAMLGraph(G);
scanf("%d",&v);
if(v<0) return ERROR; //頂點數不能為負
G.vexnum=v;
scanf(%d",&a);
if(a<0) return ERROR; //邊數不能為負
G.arcnum=a;
for(m=0;m<v;m++)
G.adjmulist[m].data=getchar(); //輸入各頂點的符號
for(m=1;m<=a;m++)
{
t=getchar();h=getchar(); //t為弧尾,h為弧頭
if((i=LocateVex(G,t))<0) return ERROR;
if((j=LocateVex(G,h))<0) return ERROR; //頂點未找到
p=(EBox*)malloc(sizeof(EBox));
p->ivex=i;p->jvex=j;
p->ilink=NULL;p->jlink=NULL; //邊結點賦初值
if(!G.adjmulist[i].firstedge) G.adjmulist[i].firstedge=p;
else
{
q=G.adjmulist[i].firstedge;
while(q)
{
r=q;
if(q->ivex==i) q=q->ilink;
else q=q->jlink;
}
if(r->ivex==i) r->ilink=p;//注意i值既可能出現在邊結點的ivex域中,
else r->jlink=p; //又可能出現在邊結點的jvex域中
}//else //插入i鏈表尾部
if(!G.adjmulist[j].firstedge) G.adjmulist[j].firstedge=p;
else
{
q=G.adjmulist[i].firstedge;
while(q)
{
r=q;
if(q->jvex==j) q=q->jlink;
else q=q->ilnk;
}
if(r->jvex==j) r->jlink=p;
else r->ilink=p;
}//else //插入j鏈表尾部
}//for
return OK;
}//Build_AdjList
7.20
int Pass_MGraph(MGraph G)//判斷一個鄰接矩陣存儲的有向圖是不是可傳遞的,是則返回1,否則返回0
{
for(x=0;x<G.vexnum;x++)
for(y=0;y<G.vexnum;y++)
if(G.arcs[x][y])
{
for(z=0;z<G.vexnum;z++)
if(z!=x&&G.arcs[y][z]&&!G.arcs[x][z]) return 0;//圖不可傳遞的條件
}//if
return 1;
}//Pass_MGraph
分析:本演算法的時間復雜度大概是O(n^2*d).
7.21
int Pass_ALGraph(ALGraph G)//判斷一個鄰接表存儲的有向圖是不是可傳遞的,是則返回1,否則返回0
{
for(x=0;x<G.vexnum;x++)
for(p=G.vertices[x].firstarc;p;p=p->nextarc)
{
y=p->adjvex;
for(q=G.vertices[y].firstarc;q;q=q->nextarc)
{
z=q->adjvex;
if(z!=x&&!is_adj(G,x,z)) return 0;
}//for
}//for
}//Pass_ALGraph
int is_adj(ALGraph G,int m,int n)//判斷有向圖G中是否存在邊(m,n),是則返回1,否則返回0
{
for(p=G.vertices[m].firstarc;p;p=p->nextarc)
if(p->adjvex==n) return 1;
return 0;
}//is_adj
7.22
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
7.23
int exist_path_BFS(ALGraph 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[u]=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
7.24
void STraverse_Nonrecursive(Graph G)//非遞歸遍歷強連通圖G
{
int visited[MAXSIZE];
InitStack(S);
Push(S,GetVex(S,1)); //將第一個頂點入棧
visit(1);
visited =1;
while(!StackEmpty(S))
{
while(Gettop(S,i)&&i)
{
j=FirstAdjVex(G,i);
if(j&&!visited[j])
{
visit(j);
visited[j]=1;
Push(S,j); //向左走到盡頭
}
}//while
if(!StackEmpty(S))
{
Pop(S,j);
Gettop(S,i);
k=NextAdjVex(G,i,j); //向右走一步
if(k&&!visited[k])
{
visit(k);
visited[k]=1;
Push(S,k);
}
}//if
}//while
}//Straverse_Nonrecursive
分析:本演算法的基本思想與二叉樹的先序遍歷非遞歸演算法相同,請參考6.37.由於是強連通圖,所以從第一個結點出發一定能夠訪問到所有結點.
7.25
見書後解答.
7.26
Status TopoNo(ALGraph G)//按照題目要求順序重排有向圖中的頂點
{
int new[MAXSIZE],indegree[MAXSIZE]; //儲存結點的新序號
n=G.vexnum;
FindInDegree(G,indegree);
InitStack(S);
for(i=1;i<G.vexnum;i++)
if(!indegree[i]) Push(S,i); //零入度結點入棧
count=0;
while(!StackEmpty(S))
{
Pop(S,i);
new[i]=n--; //記錄結點的拓撲逆序序號
count++;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(!(--indegree[k])) Push(S,k);
}//for
}//while
if(count<G.vexnum) return ERROR; //圖中存在環
for(i=1;i<=n;i++) printf("Old No:%d New No:%d\n",i,new[i])
return OK;
}//TopoNo
分析:只要按拓撲逆序對頂點編號,就可以使鄰接矩陣成為下三角矩陣.
7.27
int visited[MAXSIZE];
int exist_path_len(ALGraph G,int i,int j,int k)//判斷鄰接表方式存儲的有向圖G的頂點i到j是否存在長度為k的簡單路徑
{
if(i==j&&k==0) return 1; //找到了一條路徑,且長度符合要求
else if(k>0)
{
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
l=p->adjvex;
if(!visited[l])
if(exist_path_len(G,l,j,k-1)) return 1; //剩餘路徑長度減一
}//for
visited[i]=0; //本題允許曾經被訪問過的結點出現在另一條路徑中
}//else
return 0; //沒找到
}//exist_path_len
7.28
int path[MAXSIZE],visited[MAXSIZE]; //暫存遍歷過程中的路徑
int Find_All_Path(ALGraph G,int u,int v,int k)//求有向圖G中頂點u到v之間的所有簡單路徑,k表示當前路徑長度
{
path[k]=u; //加入當前路徑中
visited[u]=1;
if(u==v) //找到了一條簡單路徑
{
printf("Found one path!\n");
for(i=0;path[i];i++) printf("%d",path[i]); //列印輸出
}
else
for(p=G.vertices[u].firstarc;p;p=p->nextarc)
{
l=p->adjvex;
if(!visited[l]) Find_All_Path(G,l,v,k+1); //繼續尋找
}
visited[u]=0;
path[k]=0; //回溯
}//Find_All_Path
main()
{
...
Find_All_Path(G,u,v,0); //在主函數中初次調用,k值應為0
...
}//main
7.29
int GetPathNum_Len(ALGraph G,int i,int j,int len)//求鄰接表方式存儲的有向圖G的頂點i到j之間長度為len的簡單路徑條數
{
if(i==j&&len==0) return 1; //找到了一條路徑,且長度符合要求
else if(len>0)
{
sum=0; //sum表示通過本結點的路徑數
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
l=p->adjvex;
if(!visited[l])
sum+=GetPathNum_Len(G,l,j,len-1)//剩餘路徑長度減一
}//for
visited[i]=0; //本題允許曾經被訪問過的結點出現在另一條路徑中
}//else
return sum;
}//GetPathNum_Len
7.30
int visited[MAXSIZE];
int path[MAXSIZE]; //暫存當前路徑
int cycles[MAXSIZE][MAXSIZE]; //儲存發現的迴路所包含的結點
int thiscycle[MAXSIZE]; //儲存當前發現的一個迴路
int cycount=0; //已發現的迴路個數
void GetAllCycle(ALGraph G)//求有向圖中所有的簡單迴路
{
for(v=0;v<G.vexnum;v++) visited[v]=0;
for(v=0;v<G.vexnum;v++)
if(!visited[v]) DFS(G,v,0); //深度優先遍歷
}//DFSTraverse
void DFS(ALGraph G,int v,int k)//k表示當前結點在路徑上的序號
{
visited[v]=1;
path[k]=v; //記錄當前路徑
for(p=G.vertices[v].firstarc;p;p=p->nextarc)
{
w=p->adjvex;
if(!visited[w]) DFS(G,w,k+1);
else //發現了一條迴路
{
for(i=0;path[i]!=w;i++); //找到迴路的起點
for(j=0;path[i+j];i++) thiscycle[j]=path[i+j];//把迴路復制下來
if(!exist_cycle()) cycles[cycount++]=thiscycle;//如果該迴路尚未被記錄過,就添加到記錄中
for(i=0;i<G.vexnum;i++) thiscycle[i]=0; //清空目前迴路數組
}//else
}//for
path[k]=0;
visited[k]=0; //注意只有當前路徑上的結點visited為真.因此一旦遍歷中發現當前結點visited為真,即表示發現了一條迴路
}//DFS
int exist_cycle()//判斷thiscycle數組中記錄的迴路在cycles的記錄中是否已經存在
{
int temp[MAXSIZE];
for(i=0;i<cycount;i++) //判斷已有的迴路與thiscycle是否相同
{ //也就是,所有結點和它們的順序都相同
j=0;c=thiscycle�; //例如,142857和857142是相同的迴路
for(k=0;cycles[i][k]!=c&&cycles[i][k]!=0;k++);//在cycles的一個行向量中尋找等於thiscycle第一個結點的元素
if(cycles[i][k]) //有與之相同的一個元素
{
for(m=0;cycles[i][k+m];m++)
temp[m]=cycles[i][k+m];
for(n=0;n<k;n++,m++)
temp[m]=cycles[i][n]; //調整cycles中的當前記錄的循環相位並放入temp數組中
if(!StrCompare(temp,thiscycle)) //與thiscycle比較
return 1; //完全相等
for(m=0;m<G.vexnum;m++) temp[m]=0; //清空這個數組
}
}//for
return 0; //所有現存迴路都不與thiscycle完全相等
}//exist_cycle
分析:這個演算法的思想是,在遍歷中暫存當前路徑,當遇到一個結點已經在路徑之中時就表明存在一條迴路;掃描路徑向量path可以獲得這條迴路上的所有結點.把結點序列(例如,142857)存入thiscycle中;由於這種演算法中,一條迴路會被發現好幾次,所以必須先判斷該迴路是否已經在cycles中被記錄過,如果沒有才能存入cycles的一個行向量中.把cycles的每一個行向量取出來與之比較.由於一條迴路可能有多種存儲順序,比如142857等同於285714和571428,所以還要調整行向量的次序,並存入temp數組,例如,thiscycle為142857第一個結點為1,cycles的當前向量為857142,則找到後者中的1,把1後部分提到1前部分前面,最終在temp中得到142857,與thiscycle比較,發現相同,因此142857和857142是同一條迴路,不予存儲.這個演算法太復雜,很難保證細節的准確性,大家理解思路便可.希望有人給出更加簡捷的演算法.
7.31
int visited[MAXSIZE];
int finished[MAXSIZE];
int count; //count在第一次深度優先遍歷中用於指示finished數組的填充位置
void Get_SGraph(OLGraph G)//求十字鏈表結構儲存的有向圖G的強連通分量
{
count=0;
for(v=0;v<G.vexnum;v++) visited[v]=0;
for(v=0;v<G.vexnum;v++) //第一次深度優先遍歷建立finished數組
if(!visited[v]) DFS1(G,v);
for(v=0;v<G.vexnum;v++) visited[v]=0; //清空visited數組
for(i=G.vexnum-1;i>=0;i--) //第二次逆向的深度優先遍歷
{
v=finished(i);
if(!visited[v])
{
printf("\n"); //不同的強連通分量在不同的行輸出
DFS2(G,v);
}
}//for
}//Get_SGraph
void DFS1(OLGraph G,int v)//第一次深度優先遍歷的演算法
{
visited[v]=1;
for(p=G.xlist[v].firstout;p;p=p->tlink)
{
w=p->headvex;
if(!visited[w]) DFS1(G,w);
}//for
finished[++count]=v; //在第一次遍歷中建立finished數組
}//DFS1
void DFS2(OLGraph G,int v)//第二次逆向的深度優先遍歷的演算法
{
visited[v]=1;
printf("%d",v); //在第二次遍歷中輸出結點序號
for(p=G.xlist[v].firstin;p;p=p->hlink)
{
w=p->tailvex;
if(!visited[w]) DFS2(G,w);
}//for
}//DFS2
分析:求有向圖的強連通分量的演算法的時間復雜度和深度優先遍歷相同,也為O(n+e).
7.32
void Forest_Prim(ALGraph G,int k,CSTree &T)//從頂點k出發,構造鄰接表結構的有向圖G的最小生成森林T,用孩子兄弟鏈表存儲
{
for(j=0;j<G.vexnum;j++) //以下在Prim演算法基礎上稍作改動
if(j!=k)
{
closedge[j]={k,Max_int};
for(p=G.vertices[j].firstarc;p;p=p->nextarc)
if(p->adjvex==k) closedge[j].lowcost=p->cost;
}//if
closedge[k].lowcost=0;
for(i=1;i<G.vexnum;i++)
{
k=minimum(closedge);
if(closedge[k].lowcost<Max_int)
{
Addto_Forest(T,closedge[k].adjvex,k); //把這條邊加入生成森林中
closedge[k].lowcost=0;
for(p=G.vertices[k].firstarc;p;p=p->nextarc)
if(p->cost<closedge[p->adjvex].lowcost)
closedge[p->adjvex]={k,p->cost};
}//if
else Forest_Prim(G,k); //對另外一個連通分量執行演算法
}//for
}//Forest_Prim
void Addto_Forest(CSTree &T,int i,int j)//把邊(i,j)添加到孩子兄弟鏈表表示的樹T中
{
p=Locate(T,i); //找到結點i對應的指針p,過程略
q=(CSTNode*)malloc(sizeof(CSTNode));
q->data=j;
if(!p) //起始頂點不屬於森林中已有的任何一棵樹
{
p=(CSTNode*)malloc(sizeof(CSTNode));
p->data=i;
for(r=T;r->nextsib;r=r->nextsib);
r->nextsib=p;
p->firstchild=q;
} //作為新樹插入到最右側
else if(!p->firstchild) //雙親還沒有孩子
p->firstchild=q; //作為雙親的第一個孩子
else //雙親已經有了孩子
{
for(r=p->firstchild;r->nextsib;r=r->nextsib);
r->nextsib=q; //作為雙親最後一個孩子的兄弟
}
}//Addto_Forest
main()
{
...
T=(CSTNode*)malloc(sizeof(CSTNode)); //建立樹根
T->data=1;
Forest_Prim(G,1,T);
...
}//main
分析:這個演算法是在Prim演算法的基礎上添加了非連通圖支持和孩子兄弟鏈表構建模塊而得到的,其時間復雜度為O(n^2).
7.33
typedef struct {
int vex; //結點序號
int ecno; //結點所屬的連通分量號
} VexInfo;
VexInfo vexs[MAXSIZE]; //記錄結點所屬連通分量號的數組
void Init_VexInfo(VexInfo &vexs[ ],int vexnum)//初始化
{
for(i=0;i<vexnum;i++)
vexs[i]={i,i}; //初始狀態:每一個結點都屬於不同的連通分量
}//Init_VexInfo
int is_ec(VexInfo vexs[ ],int i,int j)//判斷頂點i和頂點j是否屬於同一個連通分量
{
if(vexs[i].ecno==vexs[j].ecno) return 1;

⑦ 有向圖的遍歷所有邊的演算法

可以考慮中國郵遞員問題。結合哈密頓圖和遞歸去做，把多個奇點分成幾個小圖。這樣的少不了計算

⑧ 圖遍歷演算法之最短路徑Dijkstra演算法

最短路徑問題是圖論研究中一個經典演算法問題，旨在尋找圖中兩節點或單個節點到其他節點之間的最短路徑。根據問題的不同，演算法的具體形式包括：

常用的最短路徑演算法包括：Dijkstra演算法，A 演算法，Bellman-Ford演算法，SPFA演算法（Bellman-Ford演算法的改進版本），Floyd-Warshall演算法，Johnson演算法以及Bi-direction BFS演算法。本文將重點介紹Dijkstra演算法的原理以及實現。

Dijkstra演算法，翻譯作戴克斯特拉演算法或迪傑斯特拉演算法，於1956年由荷蘭計算機科學家艾茲赫爾.戴克斯特拉提出，用於解決賦權有向圖的 單源最短路徑問題 。所謂單源最短路徑問題是指確定起點，尋找該節點到圖中任意節點的最短路徑，演算法可用於尋找兩個城市中的最短路徑或是解決著名的旅行商問題。

問題描述 ：在無向圖 中， 為圖節點的集合， 為節點之間連線邊的集合。假設每條邊 的權重為 ，找到由頂點 到其餘各個節點的最短路徑（單源最短路徑）。

為帶權無向圖，圖中頂點 分為兩組，第一組為已求出最短路徑的頂點集合（用 表示）。初始時 只有源點，當求得一條最短路徑時，便將新增頂點添加進 ，直到所有頂點加入 中，演算法結束。第二組為未確定最短路徑頂點集合（用 表示），隨著 中頂點增加， 中頂點逐漸減少。

以下圖為例，對Dijkstra演算法的工作流程進行演示（以頂點 為起點）：

註：
01） 是已計算出最短路徑的頂點集合；
02） 是未計算出最短路徑的頂點集合；
03） 表示頂點 到頂點 的最短距離為3
第1步 ：選取頂點 添加進

第2步 ：選取頂點 添加進 ，更新 中頂點最短距離

第3步 ：選取頂點 添加進 ，更新 中頂點最短距離

第4步 ：選取頂點 添加進 ，更新 中頂點最短距離

第5步 ：選取頂點 添加進 ，更新 中頂點最短距離

第6步 ：選取頂點 添加進 ，更新 中頂點最短距離

第7步 ：選取頂點 添加進 ，更新 中頂點最短距離

示例：node編號1-7分別代表A,B,C,D,E,F,G

(s.paths <- shortest.paths(g, algorithm = "dijkstra"))輸出結果：

(s.paths <- shortest.paths(g,4, algorithm = "dijkstra"))輸出結果：

示例：

找到D（4）到G（7）的最短路徑：

[1] 維基網路，最短路徑問題： https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98 ；
[2]CSDN，Dijkstra演算法原理： https://blog.csdn.net/yalishadaa/article/details/55827681 ;
[3]RDocumentation: https://www.rdocumentation.org/packages/RNeo4j/versions/1.6.4/topics/dijkstra ;
[4]RDocumentation: https://www.rdocumentation.org/packages/igraph/versions/0.1.1/topics/shortest.paths ;
[5]Pypi: https://pypi.org/project/Dijkstar/