Ⅰ 圖的深度遍歷課程設計(C語言版)
//圖的遍歷演算法程序
//圖的遍歷是指按某條搜索路徑訪問圖中每個結點,使得每個結點均被訪問一次,而且僅被訪問一次。圖的遍歷有深度遍歷演算法和廣度遍歷演算法,程序如下:
#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
程序結束.
Ⅱ 求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");
}
Ⅲ C語言描述下的深度遍歷演算法,運行時報錯,不明白原因,可能是指針指向錯誤內存的原因,不知道怎麼修改
// adj 沒有申請內存
1: 修改create函數為: void create(AdjMatrix * & adj) // 引用
2: 申請 adj內存.
int main(int argc, char ** argv)
{
int i;
adj = (AdjMatrix*)malloc(sizeof(AdjMatrix));
memset((void*)adj, 0, sizeof(AdjMatrix) );
create(adj);
for(i=1;i<=N;i++) {
visited[i]=0;
}
DFS(1);
}
Ⅳ 用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();
}
Ⅳ C語言的遍歷演算法
思路1:
寫出所有24種4個數的排列,存到一個數組里,假如數組是P[24][4];
那麼可以
for
(i
=
0;
i
<
24;
i++)
for
(j
=
0;
j
<
24;
j++)
for
(k
=
0;
k
<
24;
k++)
三層循環,P[i],P[j],P[k]分別是矩陣的三個列
思路2:
利用dfs遞歸枚舉
int
used[3][4];/*這個數組存放三個列中0~3這四個數是否已在這一列中出現過,需要提前清零*/
int
mat[3][4];/*要枚舉的矩陣*/
void
dfs(int
col,
int
row)/*col表示現在已經搜索到哪一列(從0開始編號),row表示這一列已經填了幾行*/
{
int
i;
if
(col
==
2
&&
row
==
4)
{
....../*運行到這里的時候,mat就是枚舉到的一個矩陣*/
return;
}
if
(row
==
4)
{row
=
0;
col++;}
for
(i
=
0;
i
<
4;
i++)
if
(!used[col][i])
{
used[col][i]
=
1;
mat[col][row]
=
i;
dfs(col,
row
+
1);
used[col][i]
=
0;
}
return;
}
調用的時候調用dfs(0,0)
Ⅵ 怎樣用C語言實現已知起點 將完全帶權圖利用深度遍歷求出所有路徑 比較長度 輸出最短路徑的演算法
給你一個作為參考吧
#include <iostream>
#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");
}
Ⅶ C語言數據結構(有向圖的深度優先遍歷)
對的
深度優先顧名思義就是先向深的地方遍歷
按照你上面的圖來說,就是這樣的
廣度優先的話就是先搜索相鄰節點
順序是a b c d--這個是廣度優先
深度優先的圖最好不要存在環...那樣會出現問題
Ⅷ 求圖的深度優先遍歷程序 c語言版
鄰接表表示的圖:#include"stdio.h"
#include"stdlib.h"#define MaxVertexNum 50 //定義最大頂點數typedef struct node{ //邊表結點
int adjvex; //鄰接點域
struct node *next; //鏈域
}EdgeNode;
typedef struct vnode{ //頂點表結點
char vertex; //頂點域
EdgeNode *firstedge; //邊表頭指針
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum]; //AdjList是鄰接表類型
typedef struct {
AdjList adjlist; //鄰接表
int n,e; //圖中當前頂點數和邊數
} ALGraph; //圖類型//=========建立圖的鄰接表=======
void CreatALGraph(ALGraph *G)
{
int i,j,k;
char a;
EdgeNode *s; //定義邊表結點
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //讀入頂點數和邊數
fflush(stdin); //清空內存緩沖
printf("Input Vertex string:");
for(i=0;i<G->n;i++) //建立邊表
{
scanf("%c",&a);
G->adjlist[i].vertex=a; //讀入頂點信息
G->adjlist[i].firstedge=NULL; //邊表置為空表
}
printf("Input edges,Creat Adjacency List\n");
for(k=0;k<G->e;k++) { //建立邊表
scanf("%d%d",&i,&j); //讀入邊(Vi,Vj)的頂點對序號
s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成邊表結點
s->adjvex=j; //鄰接點序號為j
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s; //將新結點*S插入頂點Vi的邊表頭部
s=(EdgeNode *)malloc(sizeof(EdgeNode));
s->adjvex=i; //鄰接點序號為i
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s; //將新結點*S插入頂點Vj的邊表頭部
}
}
//=========定義標志向量,為全局變數=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS:深度優先遍歷的遞歸演算法======
void DFSM(ALGraph *G,int i)
{//以Vi為出發點對鄰接鏈表表示的圖G進行DFS搜索
EdgeNode *p;
printf("%c",G->adjlist[i].vertex); //訪問頂點Vi
visited[i]=TRUE; //標記Vi已訪問
p=G->adjlist[i].firstedge; //取Vi邊表的頭指針
while(p) { //依次搜索Vi的鄰接點Vj,這里j=p->adjvex
if(! visited[p->adjvex]) //若Vj尚未被訪問
DFSM(G,p->adjvex); //則以Vj為出發點向縱深搜索
p=p->next; //找Vi的下一個鄰接點
}
}
void DFS(ALGraph *G)
{
int i;
for(i=0;i<G->n;i++)
visited[i]=FALSE; //標志向量初始化
for(i=0;i<G->n;i++)
if(!visited[i]) //Vi未訪問過
DFSM(G,i); //以Vi為源點開始DFS搜索
} //==========BFS:廣度優先遍歷=========
void BFS(ALGraph *G,int k)
{ //以Vk為源點對用鄰接鏈表表示的圖G進行廣度優先搜索
int i,f=0,r=0; EdgeNode *p;
int cq[MaxVertexNum]; //定義FIFO隊列
for(i=0;i<G->n;i++)
visited[i]=FALSE; //標志向量初始化
for(i=0;i<=G->n;i++)
cq[i]=-1; //初始化標志向量
printf("%c",G->adjlist[k].vertex); //訪問源點Vk
visited[k]=TRUE;
cq[r]=k; //Vk已訪問,將其入隊。注意,實際上是將其序號入隊
while(cq[f]!=-1) { // 隊列非空則執行
i=cq[f]; f=f+1; //Vi出隊
p=G->adjlist[i].firstedge; //取Vi的邊表頭指針
while(p) { //依次搜索Vi的鄰接點Vj(令p->adjvex=j)
if(!visited[p->adjvex]) { //若Vj未訪問過
printf("%c",G->adjlist[p->adjvex].vertex); //訪問Vj
visited[p->adjvex]=TRUE;
r=r+1; cq[r]=p->adjvex; //訪問過的Vj入隊
}
p=p->next; //找Vi的下一個鄰接點
}
}//endwhile
}
//==========主函數===========
void main()
{
//int i;
ALGraph *G;
G=(ALGraph *)malloc(sizeof(ALGraph));
CreatALGraph(G);
printf("Print Graph DFS: ");
DFS(G);
printf("\n");
printf("Print Graph BFS: ");
BFS(G,3);
printf("\n");
}鄰接矩陣表示的圖:
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定義最大頂點數
typedef struct{
char vexs[MaxVertexNum]; //頂點表
int edges[MaxVertexNum][MaxVertexNum]; //鄰接矩陣,可看作邊表
int n,e; //圖中的頂點數n和邊數e
}MGraph; //用鄰接矩陣表示的圖的類型
//=========建立鄰接矩陣=======
void CreatMGraph(MGraph *G)
{
int i,j,k;
char a;
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //輸入頂點數和邊數
scanf("%c",&a);
printf("Input Vertex string:");
for(i=0;i<G->n;i++)
{
scanf("%c",&a);
G->vexs[i]=a; //讀入頂點信息,建立頂點表
}
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=0; //初始化鄰接矩陣
printf("Input edges,Creat Adjacency Matrix\n");
for(k=0;k<G->e;k++) { //讀入e條邊,建立鄰接矩陣
scanf("%d%d",&i,&j); //輸入邊(Vi,Vj)的頂點序號
G->edges[i][j]=1;
G->edges[j][i]=1; //若為無向圖,矩陣為對稱矩陣;若建立有向圖,去掉該條語句
}
}
//=========定義標志向量,為全局變數=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS:深度優先遍歷的遞歸演算法======
void DFSM(MGraph *G,int i)
{ //以Vi為出發點對鄰接矩陣表示的圖G進行DFS搜索,鄰接矩陣是0,1矩陣
int j;
printf("%c",G->vexs[i]); //訪問頂點Vi
visited[i]=TRUE; //置已訪問標志
for(j=0;j<G->n;j++) //依次搜索Vi的鄰接點
if(G->edges[i][j]==1 && ! visited[j])
DFSM(G,j); //(Vi,Vj)∈E,且Vj未訪問過,故Vj為新出發點
}
void DFS(MGraph *G)
{
int i;
for(i=0;i<G->n;i++)
visited[i]=FALSE; //標志向量初始化
for(i=0;i<G->n;i++)
if(!visited[i]) //Vi未訪問過
DFSM(G,i); //以Vi為源點開始DFS搜索
}
//===========BFS:廣度優先遍歷=======
void BFS(MGraph *G,int k)
{ //以Vk為源點對用鄰接矩陣表示的圖G進行廣度優先搜索
int i,j,f=0,r=0;
int cq[MaxVertexNum]; //定義隊列
for(i=0;i<G->n;i++)
visited[i]=FALSE; //標志向量初始化
for(i=0;i<G->n;i++)
cq[i]=-1; //隊列初始化
printf("%c",G->vexs[k]); //訪問源點Vk
visited[k]=TRUE;
cq[r]=k; //Vk已訪問,將其入隊。注意,實際上是將其序號入隊
while(cq[f]!=-1) { //隊非空則執行
i=cq[f]; f=f+1; //Vf出隊
for(j=0;j<G->n;j++) //依次Vi的鄰接點Vj
if(!visited[j] && G->edges[i][j]==1) { //Vj未訪問
printf("%c",G->vexs[j]); //訪問Vj
visited[j]=TRUE;
r=r+1; cq[r]=j; //訪問過Vj入隊
}
}
}
//==========main=====
void main()
{
//int i;
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //為圖G申請內存空間
CreatMGraph(G); //建立鄰接矩陣
printf("Print Graph DFS: ");
DFS(G); //深度優先遍歷
printf("\n");
printf("Print Graph BFS: ");
BFS(G,3); //以序號為3的頂點開始廣度優先遍歷
printf("\n");
}
Ⅸ c語言實驗:圖的建立和深度遍歷程序
#include "stdio.h"
#include "string.h"
#define MAX 21
int legal(int x, int y);
void dfs(int i, int j);
char map[MAX][MAX];
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int w, h;
int ans;
int main(void)
{
while (scanf("%d%d", &w, &h) && (w + h))
{
int i, j;
int si, sj;
ans = 0;
memset(map, 0, sizeof(map));
for (i=0; i<h; i++)
{
scanf("%s", map[i]);
for (j=0; j<w; j++)
{
if (map[i][j] == '@')
{
si = i;
sj = j;
}
}
}
dfs(si, sj);
printf("%d\n", ans);
}
return 0;
}
int legal(int x, int y)
{
if (x < 0 || x > h || y < 0 || y > w)
{
return 0;
}
return 1;
}
void dfs(int i, int j)
{
int k;
int x, y;
++ans;
map[i][j] = '#';
for (k=0; k<4; k++)
{
x = i + dir[k][0];
y = j + dir[k][1];
if (legal(x, y) && map[x][y] == '.')
{
dfs(x, y);
}
}
}
這是一個簡單的 深搜的例子!