圖遍歷演算法

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

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的路徑數目，演算法我想了一下，如果非要用一個遍歷作出來，還真要花點兒時間，還不一定最優。

B. 數據結構 圖的遍歷

無向圖可以。有向圖的話，因為可以認為是多條遍歷路徑同時進行，對於一個已訪問過的結點無法判斷該節點或其後代結點中是否存在當前遍歷路徑上的結點；而對於深度優先遍歷，任何時候都只有一條遍歷路徑，可以通過標記區分出某個已訪問結點是在當前路徑上的結點還是不在當前路徑上的已回溯結點。

C. 求c語言圖的深度優先遍歷演算法

#define MaxVerNum 100 /* 最大頂點數為*/
typedef enum {False,True} boolean;
#include "stdio.h"
#include "stdlib.h"
boolean visited[MaxVerNum];

typedef struct node /* 表結點*/
{
int adjvex;/* 鄰接點域,一般是放頂點對應的序號或在表頭向量中的下標*/
char Info; /*與邊(或弧)相關的信息*/
struct node * next; /* 指向下一個鄰接點的指針域*/
} EdgeNode;
typedef struct vnode /* 頂點結點*/
{
char vertex; /* 頂點域*/
EdgeNode * firstedge; /* 邊表頭指針*/
} VertexNode;
typedef struct
{
VertexNode adjlist[MaxVerNum]; /* 鄰接表*/
int n,e; /* 頂點數和邊數*/
} ALGraph; /* ALGraph是以鄰接表方式存儲的圖類型*/

//建立一個無向圖的鄰接表存儲的演算法如下：
void CreateALGraph(ALGraph *G)/* 建立有向圖的鄰接表存儲*/
{
int i,j,k;
int N,E;
EdgeNode *p;
printf("請輸入頂點數和邊數：");
scanf("%d %d",&G->n,&G->e);
printf("n=%d,e=%d\n\n",G->n,G->e);
getchar();
for(i=0;i<G->n;i++) /* 建立有n個頂點的頂點表*/
{
printf("請輸入第%d個頂點字元信息(共%d個)：",i+1,G->n);
scanf("%c",&(G->adjlist[i].vertex)); /* 讀入頂點信息*/
getchar();
G->adjlist[i].firstedge=NULL; /* 頂點的邊表頭指針設為空*/
}
for(k=0;k<2*G->e;k++) /* 建立邊表*/
{
printf("請輸入邊<Vi,Vj>對應的頂點序號(共%d個)：",2*G->e);
scanf("%d %d",&i,&j);/* 讀入邊<Vi,Vj>的頂點對應序號*/
p=(EdgeNode *)malloc(sizeof(EdgeNode)); // 生成新邊表結點p
p->adjvex=j; /* 鄰接點序號為j */
p->next=G->adjlist[i].firstedge;/* 將結點p插入到頂點Vi的鏈表頭部*/
G->adjlist[i].firstedge=p;
}
printf("\n圖已成功創建!對應的鄰接表如下：\n");
for(i=0;i<G->n;i++)
{
p=G->adjlist[i].firstedge;
printf("%c->",G->adjlist[i].vertex);
while(p!=NULL)
{
printf("[ %c ]",G->adjlist[p->adjvex].vertex);
p=p->next;
}
printf("\n");
}
printf("\n");
} /*CreateALGraph*/

int FirstAdjVertex(ALGraph *g,int v)//找圖g中與頂點v相鄰的第一個頂點
{
if(g->adjlist[v].firstedge!=NULL) return (g->adjlist[v].firstedge)->adjvex;
else return 0;
}

int NextAdjVertex(ALGraph *g ,int vi,int vj )//找圖g中與vi相鄰的，相對相鄰頂點vj的下一個相鄰頂點
{
EdgeNode *p;
p=g->adjlist[vi].firstedge;
while( p!=NULL && p->adjvex!=vj) p=p->next;
if(p!=NULL && p->next!=NULL) return p->next->adjvex;
else return 0;
}
void DFS(ALGraph *G,int v) /* 從第v個頂點出發深度優先遍歷圖G */
{
int w;
printf("%c ",G->adjlist[v].vertex);
visited[v]=True; /* 訪問第v個頂點，並把訪問標志置True */
for(w=FirstAdjVertex(G,v);w;w=NextAdjVertex(G,v,w))
if (!visited[w]) DFS(G,w); /* 對v尚未訪問的鄰接頂點w遞歸調用DFS */
}

void DFStraverse(ALGraph *G)
/*深度優先遍歷以鄰接表表示的圖G，而以鄰接矩陣表示時，演算法完全相同*/
{ int i,v;
for(v=0;v<G->n;v++)
visited[v]=False;/*標志向量初始化*/
//for(i=0;i<G->n;i++)
if(!visited[0]) DFS(G,0);
}/*DFS*/

void main()
{
ALGraph G;
CreateALGraph(&G);
printf("該無向圖的深度優先搜索序列為：");
DFStraverse(&G);
printf("\nSuccess!\n");
}

D. 圖的圖的遍歷

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

E. 用c++寫出圖的遍歷演算法，謝謝！

ude <iostream>
#include <malloc.h>
using namespace std;
#define int_max 10000
#define inf 9999
#define max 20
//…………………………………………鄰接矩陣定義……………………
typedef struct ArcCell
{
int adj;
char *info;
}ArcCell,AdjMatrix[20][20];
typedef struct
{
char vexs[20];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph_L;
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int localvex(MGraph_L G,char v)//返回V的位置
{
int i=0;
while(G.vexs[i]!=v)
{
++i;
}
return i;
}

int creatMGraph_L(MGraph_L &G)//創建圖用鄰接矩陣表示
{
char v1,v2;
int i,j,w;
cout<<"…………創建無向圖…………"<<endl<<"請輸入圖G頂點和弧的個數:(4 6)不包括「()」"<<endl;
cin>>G.vexnum>>G.arcnum;
for(i=0;i!=G.vexnum;++i)
{
cout<<"輸入頂點"<<i<<endl;
cin>>G.vexs[i];
}
for(i=0;i!=G.vexnum;++i)
for(j=0;j!=G.vexnum;++j)
{
G.arcs[i][j].adj=int_max;
G.arcs[i][j].info=NULL;
}
for(int k=0;k!=G.arcnum;++k)
{
cout<<"輸入一條邊依附的頂點和權:(a b 3)不包括「()」"<<endl;
cin>>v1>>v2>>w;//輸入一條邊依附的兩點及權值
i=localvex(G,v1);//確定頂點V1和V2在圖中的位置
j=localvex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=w;
}
cout<<"圖G鄰接矩陣創建成功！"<<endl;
return G.vexnum;
}
void ljjzprint(MGraph_L G)
{
int i,j;
for(i=0;i!=G.vexnum;++i)
{
for(j=0;j!=G.vexnum;++j)
cout<<G.arcs[i][j].adj<<" ";
cout<<endl;
}
}
int visited[max];//訪問標記
int we;
typedef struct arcnode//弧結點
{
int adjvex;//該弧指向的頂點的位置
struct arcnode *nextarc;//弧尾相同的下一條弧
char *info;//該弧信息
}arcnode;
typedef struct vnode//鄰接鏈表頂點頭接點
{
char data;//結點信息
arcnode *firstarc;//指向第一條依附該結點的弧的指針
}vnode,adjlist;
typedef struct//圖的定義
{
adjlist vertices[max];
int vexnum,arcnum;
int kind;
}algraph;
//…………………………………………隊列定義……………………
typedef struct qnode
{
int data;
struct qnode *next;

}qnode,*queueptr;

typedef struct
{
queueptr front;
queueptr rear;

}linkqueue;
//………………………………………………………………………
typedef struct acr
{
int pre;//弧的一結點
int bak;//弧另一結點
int weight;//弧的權
}edg;

int creatadj(algraph &gra,MGraph_L G)//用鄰接表存儲圖
{

int i=0,j=0;
arcnode *arc,*tem,*p;
for(i=0;i!=G.vexnum;++i)
{
gra.vertices[i].data=G.vexs[i];
gra.vertices[i].firstarc=NULL;
}
for(i=0;i!=G.vexnum;++i)
{
for(j=0;j!=G.vexnum;++j)
{
if(gra.vertices[i].firstarc==NULL)
{
if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
{
arc=(arcnode *)malloc(sizeof(arcnode));
arc->adjvex=j;
gra.vertices[i].firstarc=arc;
arc->nextarc=NULL;
p=arc;
++j;
while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
{
tem=(arcnode *)malloc(sizeof(arcnode));
tem->adjvex=j;
gra.vertices[i].firstarc=tem;
tem->nextarc=arc;
arc=tem;
++j;
}
--j;
}
}
else
{
if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
{
arc=(arcnode *)malloc(sizeof(arcnode));
arc->adjvex=j;
p->nextarc=arc;
arc->nextarc=NULL;
p=arc;
}

}

}
}
gra.vexnum=G.vexnum;
gra.arcnum=G.arcnum;

/*for(i=0;i!=gra.vexnum;++i)
{
arcnode *p;
cout<<i<<" ";
p=gra.vertices[i].firstarc;
while(p!=NULL)
{
cout<<p->adjvex;
p=p->nextarc;
}
cout<<endl;

}*/
cout<<"圖G鄰接表創建成功！"<<endl;
return 1;
}
void adjprint(algraph gra)
{
int i;
for(i=0;i!=gra.vexnum;++i)
{
arcnode *p;
cout<<i<<" ";
p=gra.vertices[i].firstarc;
while(p!=NULL)
{
cout<<p->adjvex;
p=p->nextarc;
}
cout<<endl;
}
}

int firstadjvex(algraph gra,vnode v)//返回依附頂點V的第一個點
//即以V為尾的第一個結點
{
if(v.firstarc!=NULL)
return v.firstarc->adjvex;

}
int nextadjvex(algraph gra,vnode v,int w)//返回依附頂點V的相對於W的下一個頂點
{
arcnode *p;
p=v.firstarc;
while(p!=NULL&&p->adjvex!=w)
{
p=p->nextarc;
}
if(p->adjvex==w&&p->nextarc!=NULL)
{
p=p->nextarc;
return p->adjvex;
}
if(p->adjvex==w&&p->nextarc==NULL)
return -10;

}
int initqueue(linkqueue &q)//初始化隊列
{
q.rear=(queueptr)malloc(sizeof(qnode));
q.front=q.rear;
if(!q.front)
return 0;
q.front->next=NULL;
return 1;
}
int enqueue(linkqueue &q,int e)//入隊
{
queueptr p;
p=(queueptr)malloc(sizeof(qnode));
if(!p)
return 0;
p->data=e;
p->next=NULL;
q.rear->next=p;
q.rear=p;
return 1;

}
int dequeue(linkqueue &q,int &e)//出隊
{
queueptr p;
if(q.front==q.rear)
return 0;
p=q.front->next;
e=p->data;
q.front->next=p->next;
if(q.rear==p)
q.rear=q.front;
free(p);
return 1;

}
int queueempty(linkqueue q)//判斷隊為空
{
if(q.front==q.rear)
return 1;
return 0;
}
void bfstra(algraph gra)//廣度優先遍歷
{
int i,e;
linkqueue q;
for(i=0;i!=gra.vexnum;++i)
visited[i]=0;
initqueue(q);
for(i=0;i!=gra.vexnum;++i)

if(!visited[i])
{ visited[i]=1;
cout<<gra.vertices[i].data;
enqueue(q,i);
while(!queueempty(q))
{
dequeue(q,e);
// cout<<" "<<e<<" ";
for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.vertices[e],we))
{
if(!visited[we])
{
visited[we]=1;
cout<<gra.vertices[we].data;
enqueue(q,we);
}
}
}
}
}

int dfs(algraph gra,int i);//聲明DFS

int dfstra(algraph gra)
{
int i,j;
for(i=0;i!=gra.vexnum;++i)
{
visited[i]=0;
}
for(j=0;j!=gra.vexnum;++j)
{
if(visited[j]==0)
dfs(gra,j);
}
return 0;
}
int dfs(algraph gra,int i)
{
visited[i]=1;
int we1;
// cout<<i<<visited[i]<<endl;
cout<<gra.vertices[i].data;
// cout<<endl;
for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we))
{
// cout<<we<<visited[we]<<endl;
we1=we;
// cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;
if(visited[we]==0)
// cout<<
dfs(gra,we);//<<endl;
// cout<<i<<we1<<endl;
we=we1;
// cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;
}
return 12;
}
int bfstra_fen(algraph gra)//求連通分量
{
int i,j;
for(i=0;i!=gra.vexnum;++i)
{
visited[i]=0;
}
for(j=0;j!=gra.vexnum;++j)
{
if(visited[j]==0)
{
dfs(gra,j);
cout<<endl;
}
}
return 0;
}

typedef struct
{
int adjvex;
int lowcost;
}closedge;
/*int minimum(closedge *p);
int minispantree(MGraph_L G,char u)
{

int k,j,i;
closedge closedge_a[20];
k=localvex(G,u);
// cout<<k<<endl;
for(j=0;j!=G.vexnum;++j)
{
if(j!=k)
{
closedge_a[j].adjvex=u;
closedge_a[j].lowcost=G.arcs[k][j].adj;
}
for(i=1;i!=G.vexnum;++i)
{
k=minimum(closedge_a);
cout<<k;
cout<<closedge_a[k].adjvex<<" "<<G.vexs[k]<<endl;
closedge_a[k].lowcost=0;
for(j=0;j!=G.vexnum;++j)
if(G.arcs[k][j].adj<closedge_a[j].lowcost)
{
closedge_a[j].adjvex=G.vexs[k];
closedge_a[j].lowcost=G.arcs[k][j].adj;
}

}
}
return 0;
}
int minimum(closedge *p)
{
int s=10000;
for(;p!=NULL;++p)
{
if(s>p->lowcost)
s=p->lowcost;
}
return s;

}*/
int prim(int g[][max],int n) //最小生成樹PRIM演算法
{
int lowcost[max],prevex[max]; //LOWCOST[]存儲當前集合U分別到剩餘結點的最短路徑
//prevex[]存儲最短路徑在U中的結點
int i,j,k,min;
for(i=2;i<=n;i++) //n個頂點，n-1條邊
{
lowcost[i]=g[1][i]; //初始化
prevex[i]=1; //頂點未加入到最小生成樹中
}
lowcost[1]=0; //標志頂點1加入U集合
for(i=2;i<=n;i++) //形成n-1條邊的生成樹
{
min=inf;
k=0;
for(j=2;j<=n;j++) //尋找滿足邊的一個頂點在U,另一個頂點在V的最小邊
if((lowcost[j]<min)&&(lowcost[j]!=0))
{
min=lowcost[j];
k=j;
}
printf("(%d,%d)%d\t",prevex[k]-1,k-1,min);
lowcost[k]=0; //頂點k加入U
for(j=2;j<=n;j++) //修改由頂點k到其他頂點邊的權值
if(g[k][j]<lowcost[j])
{
lowcost[j]=g[k][j];
prevex[j]=k;
}
printf("\n");
}
return 0;
}
int acrvisited[100];//kruscal弧標記數組
int find(int acrvisited[],int f)
{
while(acrvisited[f]>0)
f=acrvisited[f];
return f;
}
void kruscal_arc(MGraph_L G,algraph gra)
{

edg edgs[20];
int i,j,k=0;
for(i=0;i!=G.vexnum;++i)
for(j=i;j!=G.vexnum;++j)
{
if(G.arcs[i][j].adj!=10000)
{
edgs[k].pre=i;
edgs[k].bak=j;
edgs[k].weight=G.arcs[i][j].adj;
++k;
}
}
int x,y,m,n;
int buf,edf;
for(i=0;i!=gra.arcnum;++i)
acrvisited[i]=0;
for(j=0;j!=G.arcnum;++j)
{
m=10000;
for(i=0;i!=G.arcnum;++i)
{
if(edgs[i].weight<m)
{
m=edgs[i].weight;
x=edgs[i].pre;
y=edgs[i].bak;
n=i;
}

}
// cout<<x<<y<<m;
// cout<<endl;
buf=find(acrvisited,x);
edf=find(acrvisited,y);
// cout<<buf<<" "<<edf<<endl;
edgs[n].weight=10000;
if(buf!=edf)
{
acrvisited[buf]=edf;

cout<<"("<<x<<","<<y<<")"<<m;
cout<<endl;
}
}

}

void main()
{
algraph gra;
MGraph_L G;
int i,d,g[20][20];
char a='a';
d=creatMGraph_L(G);
creatadj(gra,G);
vnode v;
cout<<endl<<"……####注意：若該圖為非強連通圖(含有多個連通分量)時"<<endl
<<" 最小生成樹不存在,則顯示為非法值。"<<endl<<endl;
cout<<"…………………菜單……………………"<<endl<<endl;
cout<<"0、顯示該圖的鄰接矩陣……………………"<<endl;
cout<<"1、顯示該圖的鄰接表……………………"<<endl;
cout<<"2、深度優先遍歷…………………………"<<endl;
cout<<"3、廣度優先遍歷…………………………"<<endl;
cout<<"4、最小生成樹PRIM演算法…………………"<<endl;
cout<<"5、最小生成樹KRUSCAL演算法………………"<<endl;
cout<<"6、該圖的連通分量………………………"<<endl<<endl;
int s;
char y='y';
while(y='y')
{
cout<<"請選擇菜單："<<endl;
cin>>s;
switch(s)
{
case 0:
cout<<"鄰接矩陣顯示如下："<<endl;
ljjzprint(G);
break;
case 1:
cout<<"鄰接表顯示如下："<<endl;
adjprint(gra);
break;
case 2:
cout<<"廣度優先遍歷：";
bfstra(gra);
cout<<endl;
break;
case 3:
for(i=0;i!=gra.vexnum;++i)
{
visited[i]=0;
}
cout<<"深度優先遍歷：";
dfstra(gra);
cout<<endl;
break;
case 4:
for(i=0;i!=G.vexnum;++i)
for(int j=0;j!=G.vexnum;++j)
g[i+1][j+1]=G.arcs[i][j].adj;
cout<<"prim:"<<endl;
prim(g,d);
break;
case 5:
cout<<"kruscal:"<<endl;
kruscal_arc(G,gra);
break;
case 6:
cout<<"連通分量:";
bfstra_fen(gra);
break;

}
cout<<endl<<"是否繼續？y/n:";
cin>>y;
if(y=='n')
break;
}

}
另外,虛機團上產品團購,超級便宜

F. C語言 圖的遍歷

思路：
以鄰接表或鄰接矩陣為存儲結構，實現連通無向圖的深度和廣度優先遍歷。以用戶指定的結點為起始點
，分別輸出每種遍歷下的結點訪問序列和相應的生成樹的邊集。
設圖的結點不超過30個，每個結點用一個編號表示。通過輸入圖的全部邊輸入一個圖，每個邊為一個數對
可以對邊的輸入順序作出某種限制。注意，生成樹和生成邊是有向邊，端點順序不能顛倒。

G. 用C語言編程實現圖的遍歷演算法

圖的遍歷是指按某條搜索路徑訪問圖中每個結點，使得每個結點均被訪問一次，而且僅被訪問一次。圖的遍歷有深度遍歷演算法和廣度遍歷演算法，最近阿傑做了關於圖的遍歷的演算法，下面是圖的遍歷深度優先的演算法（C語言程序）：
#include<stdio.h>
#include<malloc.h>
#define MaxVertexNum 5
#define m 5
#define TRUE 1
#define NULL 0
typedef struct node
{
int adjvex;
struct node *next;
}JD;
typedef struct EdgeNode
{
int vexdata;
JD *firstarc;
}TD;
typedef struct
{
TD ag[m];
int n;
}ALGRAPH;
void DFS(ALGRAPH *G,int i)
{
JD *p;
int visited[80];
printf("visit vertex:%d->",G->ag[i].vexdata);
visited[i]=1;
p=G->ag[i].firstarc;
while(p)
{
if (!visited[p->adjvex])
DFS(G,p->adjvex);
p=p->next;
}
}
void creat(ALGRAPH *G)
{
int i,m1,j;
JD *p,*p1;
printf("please input the number of graph\n");
scanf("%d",&G->n);
for(i=0;i<G->n;i++)
{
printf("please input the info of node %d",i);
scanf("%d",&G->ag[i].vexdata);
printf("please input the number of arcs which adj to %d",i);
scanf("%d",&m1);
printf("please input the adjvex position of the first arc\n");
p=(JD *)malloc(sizeof(JD));
scanf("%d",&p->adjvex);
p->next=NULL;
G->ag[i].firstarc=p;
p1=p;
for(j=2 ;j<=m1;j++)
{
printf("please input the position of the next arc vexdata\n");
p=(JD *)malloc(sizeof(JD));
scanf("%d",&p->adjvex);
p->next=NULL;
p1->next=p;
p1=p;
}
}
}
int visited[MaxVertexNum];
void DFSTraverse(ALGRAPH *G)
{
int i;
for(i=0;i<G->n;i++)
visited[i]=0;
for(i=0;i<G->n;i++)
if(!visited[i])
DFS(G,i);
}
int main()
{
ALGRAPH *G;
printf("下面以臨接表存儲一個圖；\n");
creat(G);
printf("下面以深度優先遍歷該圖 \n");
DFSTraverse(G);
getchar();
}

H. 什麼叫遍歷演算法(最好有例子)

遍歷演算法：所謂遍歷(Traversal)，是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴於具體的應用問題。遍歷是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。當然遍歷的概念也適合於多元素集合的情況，如數組。

遍歷演算法概念延伸：

圖遍歷：圖遍歷又稱圖的遍歷，屬於數據結構中的內容。指的是從圖中的任一頂點出發，對圖中的所有頂點訪問一次且只訪問一次。圖的遍歷操作和樹的遍歷操作功能相似。圖的遍歷是圖的一種基本操作，圖的許多其它操作都是建立在遍歷操作的基礎之上。

舉例：

遍歷二叉樹搜索路線：

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：⑴訪問結點本身（N），⑵遍歷該結點的左子樹（L），⑶遍歷該結點的右子樹（R）。以上三種操作有六種執行次序：NLR、LNR、LRN、NRL、RNL、RLN。前三種次序與後三種次序對稱。

遍歷二叉樹的執行蹤跡三種遞歸遍歷演算法的搜索路線相同（如下圖虛線所示）。具體線路為：從根結點出發，逆時針沿著二叉樹外緣移動，對每個結點均途徑三次，最後回到根結點。

I. 數據結構 圖的深度遍歷演算法

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#define MAX_SIZE 100
int visited[MAX_SIZE];
typedef struct ArcNode{
char adjvex;
ArcNode *nextarc;
}ArcNode;
typedef struct VertexNode{
char data;
ArcNode *firstarc;
}VertexNode;
typedef struct{
VertexNode vexs[MAX_SIZE];
int arcnum,vexnum;
}Graph;
void visit(char ch)
{
printf("%c ",ch);
}
int Loc(Graph G,char ch)
{ int i;
for(i=1;i<=G.vexnum;i++)
{
if(ch==G.vexs[i].data)
return i;
}
}
void creatGraph(Graph *h)
{
ArcNode *p;
int i,j;
char n,m;
printf("輸入弧數和定點數:\n");
scanf("%d %d%*c",&h->arcnum,&h->vexnum);
printf("輸入%d個頂點（A~Z）:\n",h->vexnum);
for(i=1;i<=h->vexnum;i++)
{
scanf("%c%*c",&h->vexs[i].data);
h->vexs[i].firstarc=NULL;
}
printf("%d個弧,輸入弧尾和弧頭\n",h->arcnum);
for(i=1;i<=h->arcnum;i++)
{
scanf("%c %c",&n,&m);
getchar();
j=Loc(*h,n);
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=m;
p->nextarc=h->vexs[j].firstarc;
h->vexs[j].firstarc=p;

p=(ArcNode *)malloc(sizeof(ArcNode));
j=Loc(*h,m);
p->adjvex=n;
p->nextarc=h->vexs[j].firstarc;
h->vexs[j].firstarc=p; //無向圖
}
}
void DFS(Graph G,char ch)
{ ArcNode *p;
int i;
i=Loc(G,ch);
visit(ch);
visited[i]=1;
p=G.vexs[i].firstarc;
while(p!=NULL)
{
if(!visited[p->adjvex-'A'+1])
DFS(G,p->adjvex);
p=p->nextarc;
}
}
int main()
{
Graph G;
char ch,j;
memset(visited,0,sizeof(visited));
creatGraph(&G);
printf("輸入要開始搜索的頂點\n");
scanf("%c",&ch);
printf("深搜:");
DFS(G,ch);
system("pause");
}
這個是鄰接表的DFS至於鄰接矩陣的DFS，想想我還是寫一下吧void dfs(int v0){ visited[v0]=1; printf("%d",v0); for(int i=1;i<=g.vexnum;i++) if(!visited[i]) { printf("%d",i); visited[i]=1; dfs(i); }}

J. 圖的遍歷演算法java解決方案

二叉樹具有以下重要性質：
性質1 二叉樹第i層上的結點數目最多為2i-1(i≥1)。
證明：用數學歸納法證明：
歸納基礎：i=1時，有2i-1=20=1。因為第1層上只有一個根結點，所以命題成立。
歸納假設：假設對所有的j(1≤j<i)命題成立，即第j層上至多有2j-1個結點，證明j=i時命題亦成立。
歸納步驟：根據歸納假設，第i-1層上至多有2i-2個結點。由於二叉樹的每個結點至多有兩個孩子，故第i層上的結點數至多是第i-1層上的最大結點數的2倍。即j=i時，該層上至多有2×2i-2=2i-1個結點，故命題成立。

性質2 深度為k的二叉樹至多有2k-1個結點(k≥1)。
證明：在具有相同深度的二叉樹中，僅當每一層都含有最大結點數時，其樹中結點數最多。因此利用性質1可得，深度為k的二叉樹的結點數至多為：
20+21+…+2k-1=2k-1
故命題正確。

性質3 在任意-棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則no=n2+1。
證明：因為二叉樹中所有結點的度數均不大於2，所以結點總數(記為n)應等於0度結點數、1度結點(記為n1)和2度結點數之和：
n=no+n1+n2 (式子1)
另一方面，1度結點有一個孩子，2度結點有兩個孩子，故二叉樹中孩子結點總數是：
nl+2n2
樹中只有根結點不是任何結點的孩子，故二叉樹中的結點總數又可表示為：
n=n1+2n2+1 (式子2)
由式子1和式子2得到：
no=n2+1

滿二叉樹和完全二叉樹是二叉樹的兩種特殊情形。
1、滿二叉樹(FullBinaryTree)
一棵深度為k且有2k-1個結點的二又樹稱為滿二叉樹。
滿二叉樹的特點：
（1） 每一層上的結點數都達到最大值。即對給定的高度，它是具有最多結點數的二叉樹。
（2） 滿二叉樹中不存在度數為1的結點，每個分支結點均有兩棵高度相同的子樹，且樹葉都在最下一層上。
【例】圖(a)是一個深度為4的滿二叉樹。

2、完全二叉樹(Complete BinaryTree)
若一棵二叉樹至多隻有最下面的兩層上結點的度數可以小於2，並且最下一層上的結點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。
特點：
（1） 滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。
（2） 在滿二叉樹的最下一層上，從最右邊開始連續刪去若干結點後得到的二叉樹仍然是一棵完全二叉樹。
（3） 在完全二叉樹中，若某個結點沒有左孩子，則它一定沒有右孩子，即該結點必是葉結點。
【例】如圖(c)中，結點F沒有左孩子而有右孩子L，故它不是一棵完全二叉樹。
【例】圖(b)是一棵完全二叉樹。

性質4 具有n個結點的完全二叉樹的深度為

證明：設所求完全二叉樹的深度為k。由完全二叉樹定義可得：
深度為k得完全二叉樹的前k-1層是深度為k-1的滿二叉樹，一共有2k-1-1個結點。
由於完全二叉樹深度為k，故第k層上還有若干個結點，因此該完全二叉樹的結點個數：
n>2k-1-1。
另一方面，由性質2可得：
n≤2k-1，
即：2k-1-l<n≤2k-1
由此可推出：2k-1≤n<2k，取對數後有：
k-1≤lgn<k
又因k-1和k是相鄰的兩個整數，故有
,
由此即得：