c語言廣度遍歷,廣度遍歷深度遍歷

本文目錄一覽：

• 1、數據結構C語言版 圖的廣度優先遍歷和深度優先遍歷 急急急 會查重
• 2、c語言圖的遍歷，鄰接表存儲，深度，廣度優先遍歷
• 3、c語言關於圖的廣度優先遍歷
• 4、求助大神，C語言！數據結構 怎麼用廣度遍歷解決任務分配問題，在廣度
• 5、求大神幫寫一個c語言圖的深度優先遍歷，和廣度優先遍歷??
• 6、圖的深度/廣度優先遍歷C語言程序

數據結構C語言版 圖的廣度優先遍歷和深度優先遍歷 急急急 會查重

#include iostream

#include string

#include queue

using namespace std;

int FirstAdjVex(int v);

int NextAdjVex(int v, int w);

void DFS(int v); //從頂點v開始對圖做深度優先遍歷, v是頂點數組的下標

void BFS(int v); //從頂點v開始對圖做廣度優先遍歷，v是頂點數組的下標

int find(string a,int n);

int visited[10]={0};

int traver[10][10]={0};

string name[10];

int main()

{

int n,m,i,j,k;

string a,b;

//freopen(“Traver.txt”,”r”,stdin);

cinn;

cinm;

for(i=0; in; i++)

{

cina;

name[i] = a;

}

for(i=0; im;i++){

cina;

cinb;

j = find(a,n);

k = find(b,n);

traver[j][k] = 1;

traver[k][j] = 1;

}

for(i=0; in; i++){

if(visited[i] == 0)

DFS(i);

}

cout”\n”;

for(i=0; in; i++){

visited[i] = 0;

}

for(i=0; in; i++){

if(visited[i] == 0)

BFS(i);

}

cout”\n”;

return 0;

}

//尋找函數

int find(string a,int n){

int i;

for(i=0; in; i++){

if(a == name[i])

return i;

}

return -1;

}

int FirstAdjVex(int v)

{

int i;

//從編號大的鄰接點開始訪問

for (i = 9; i = 0; i–)

{

if (traver[v][i] == 1)

return i;

}

return -1;

}

int NextAdjVex(int v, int w)

{

int i;

for (i = w – 1; i = 0; i–)

{

if (traver[v][i] == 1)

return i;

}

return -1;

}

void DFS(int v)

{

int w;

//訪問頂點v(輸出頂點v的名字)

coutname[v]” “;

visited[v] = 1;

//找到頂點v的第一個鄰接點w

for (w = FirstAdjVex(v); w = 0; w = NextAdjVex(v, w))

{

//如果w沒有訪問過，對頂點w做深度優先搜索

if (visited[w] == 0)

DFS(w);

}

}

void BFS(int v) //從頂點v開始對圖做廣度優先遍歷，v是頂點數組的下標

{

int w, u;

queueint myqueue; //定義一個隊列，元素是頂點的下標

//把頂點v入隊

myqueue.push(v);

coutname[v]” “;

visited[v] = 1;

while (!myqueue.empty())

{//當隊列不為空時進入循環

//取隊頭元素

u = myqueue.front();

//隊頭元素出隊

myqueue.pop();

//把u的所有鄰接點入隊

w = FirstAdjVex(u);

while (w = 0)

{

if (visited[w] == 0)

{

//訪問w

coutname[w]” “;

visited[w] = 1;

//w入隊

myqueue.push(w);

}

w = NextAdjVex(u, w);

}

}

}

c語言圖的遍歷，鄰接表存儲，深度，廣度優先遍歷

（1） 圖的建立，按採用鄰接表作為存儲結構。

（2） 從指定頂點出發進行深度優先搜索遍歷。

（3） 從指定頂點出發進行廣度優先搜索遍歷。

#include”stdio.h”

#include”string.h”

#include”stdlib.h”

#include”math.h”

#define MAX_INT 1000

#define MAX_VERTEX_NUM 20

#define MAX_QUEUE_NUMBER 20

typedef struct ArcNode

{

int adjvex;

double adj;

struct ArcNode *nextarc;

}ArcNode;

typedef struct VexNode

{

char szName[40];

ArcNode *firstarc;

}VexNode,AdjList[MAX_VERTEX_NUM];

typedef struct

{

AdjList vexs;

int vexnum,arcnum;

}Net;

//定義隊列

typedef struct{

int *elem;

int front, rear;

}Queue;

void InitQueue(Queue Q)

{

Q.elem = new int[MAX_QUEUE_NUMBER];

Q.front = Q.rear = 0;

}

int EmptyQueue(Queue Q)

{

if(Q.front==Q.rear)

return 0;

else

return 1;

}

void DestroyQueue(Queue Q){

delete []Q.elem;

Q.front = Q.rear = 0;

}

void EnterQueue(Queue Q, int e)

{

if((Q.rear + 1)%MAX_QUEUE_NUMBER != Q.front)

Q.elem[Q.rear ] = e;

else

printf(“隊列滿!\n”);

Q.rear = (Q.rear + 1)%MAX_QUEUE_NUMBER;

}

void LeaveQueue(Queue Q, int e)

{

if(Q.rear != Q.front)

e = Q.elem[Q.front];

else

printf(“隊列空!\n”);

Q.front = (Q.front+1)%MAX_QUEUE_NUMBER;

}

int LocateVex(Net ga,char *name)

{

int i;

for(i=0;iga.vexnum;i++)

if(strcmp(name,ga.vexs[i].szName)==0)

return i;

return -1;

}

void crt_net(Net ga)

{

ArcNode *p;

char name1[40],name2[40];

int i,j,k;

double w;

printf(“請輸入頂點數和弧數：”);

scanf(“%d%d”,ga.vexnum,ga.arcnum);

printf(“請依次輸入頂點名：\n”);

for(i=0;iga.vexnum;i++)

{

scanf(“%s”,ga.vexs[i].szName);

ga.vexs[i].firstarc=NULL;

}

for(k=0;kga.arcnum;k++)

{

printf(“請輸入相鄰的兩個定點和權值：”);

scanf(“%s%s%lf”,name1,name2,w);

i=LocateVex(ga,name1);

j=LocateVex(ga,name2);

p=new ArcNode;

p-adjvex=j;

p-adj=w;

p-nextarc=ga.vexs[i].firstarc;

ga.vexs[i].firstarc=p;

}

}

void DFS(Net ga,char *name,int *visited)

{

int v,w;

ArcNode *p;

v=LocateVex(ga,name);

visited[v]=1;

printf(“%s “,ga.vexs[v].szName);

p=ga.vexs[v].firstarc;

while(p!=NULL)

{

w=p-adjvex;

if(visited[w]==0)

DFS(ga,ga.vexs[w].szName,visited);

p=p-nextarc;

}

}

void DFSTravel(Net ga,char *name)

{

int v,k=0;

int visited[20];

for(v=0;vga.vexnum;v++)

visited[v]=0;

for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))

{

if(v+1==LocateVex(ga,name))

k++;

if(visited[v]==0)

DFS(ga,ga.vexs[v].szName,visited);

}

}

void BFSTravel(Net ga,char *name)

{

ArcNode *p;

int v,w,u,k=0;

Queue Q;

int visited[20];

for(v=0;vga.vexnum;v++)

visited[v]=0;

InitQueue(Q);

for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))

{

if(v+1==LocateVex(ga,name))

k++;

if(visited[v]==0)

{

visited[v]=1;

printf(“%s “,ga.vexs[v].szName);

EnterQueue(Q,v);

while(EmptyQueue(Q)!=0)

{

LeaveQueue(Q,u);

p=ga.vexs[u].firstarc;

while(p!=NULL)

{

w=p-adjvex;

if(visited[w]==0)

{

printf(“%s “,ga.vexs[w].szName);

visited[w]=1;

EnterQueue(Q,w);

}

p=p-nextarc;

}

}

}

}

}

void main()

{

char name[40];

Net ga;

crt_net(ga);

printf(“請輸入深度優先遍歷開始點的名：”);

scanf(“%s”,name);

printf(“深度優先遍歷：”);

DFSTravel(ga,name);

printf(“\n”);

printf(“請輸入廣度優先遍歷開始點的名：”);

scanf(“%s”,name);

printf(“廣度優先遍歷：”);

BFSTravel(ga,name);

printf(“\n”);

}

c語言關於圖的廣度優先遍歷

深度優先是沿著一條路走到底，走不通了或到頭了，再回溯，再搜索。而廣搜是先搜離得最近的，再慢慢搜索遠的，隊列就是按順序存，所以開頭存的近的，末尾存遠的，說白了隊列就是從近到遠保存數據的，說的不好，希望對你會點幫助。

求助大神，C語言！數據結構 怎麼用廣度遍歷解決任務分配問題，在廣度

廣度優先搜索要藉助於隊列來實現，無論圖的儲存結構是什麼。具體演算法：1將所有節點標註為未訪問狀態2從任意一個節點開始，訪問該節點（並同時標註為已訪問），訪問後將該節點入隊。3檢查隊列是否為空，若不空，出隊，檢查和這個節點有路徑並且未被訪問的節點，訪問，再入隊……（回到第二步）廣度優先類似於樹的層序遍歷具體代碼：boolvisited[MAX];//該數組用來表示是否下標為i的節點訪問過，訪問過為true，否則為falsestructAdjNode//邊表節點結構{intadj;//鄰接點的下標intweigth;//邊權值structAdjNode*pNext;};structVertexNode//頂點節點結構{chardata;//數據類型根據需求更改structAdjNode*first;//儲存第一個邊表節點};typedefstructGraph{intnumE,numV;//當前圖的頂點數和邊數structVertexNodeVer[MAX];//頂點表}Graph;voidBFSTraverse(GraphG)//G為用鄰接表儲存的圖{for(inti=0;iadj]){printf(“%c”,G.Ver[p-adj].data);//訪問visited[p-adj]=true;//標註為訪問過enQueue(q,p-adj);//入隊}p=p-pNext;//指針指向下一個鄰接點}}}}}

求大神幫寫一個c語言圖的深度優先遍歷，和廣度優先遍歷??

/*深度優先*/

#includestdio.h

#includestdlib.h

struct node/*圖的頂點結構*/

{

int vertex;

int flag;

struct node *nextnode;

};

typedef struct node *graph;

struct node vertex_node[10];

void creat_graph(int *node,int n)

{

graph newnode,p;/*定義一個新結點及指針*/

int start,end,i;

for(i=0;in;i++)

{

start=node[i*2];/*邊的起點*/

end=node[i*2+1];/*邊的終點*/

newnode=(graph)malloc(sizeof(struct node));

newnode-vertex=end;/*新結點的內容為邊終點處頂點的內容*/

newnode-nextnode=NULL;

p=(vertex_node);/*設置指針位置*/

while(p-nextnode!=NULL)

p=p-nextnode;/*尋找鏈尾*/

p-nextnode=newnode;/*在鏈尾處插入新結點*/

}

}

void dfs(int k)

{

graph p;

vertex_node[k].flag=1;/*將標誌位置1，證明該結點已訪問過*/

printf(“vertex[%d]”,k);

p=vertex_node[k].nextnode;/*指針指向下個結點*/

while(p!=NULL)

{

if(vertex_node[p-vertex].flag==0)/*判斷該結點的標誌位是否為0*/

dfs(p-vertex);/*繼續遍歷下個結點*/

p=p-nextnode;/*若已遍歷過p指向下一個結點*/

}

}

main()

{

graph p;

int node[100],i,sn,vn;

printf(“please input the number of sides:\n”);

scanf(“%d”,sn);/*輸入無向圖的邊數*/

printf(“please input the number of vertexes\n”);

scanf(“%d”,vn);

printf(“please input the vertexes which connected by the sides:\n”);

for(i=0;i4*sn;i++)

scanf(“%d”,node[i]);/*輸入每個邊所連接的兩個頂點，起始及結束位置不同，每邊輸兩次*/

for(i=1;i=vn;i++)

{

vertex_node[i].vertex=i;/*將每個頂點的信息存入數組中*/

vertex_node[i].nextnode=NULL;

}

creat_graph(node,2*sn);/*調用函數創建鄰接表*/

printf(“the result is:\n”);

for(i=1;i=vn;i++)/*將鄰接表內容輸出*/

{

printf(“vertex%d:”,vertex_node[i].vertex);/*輸出頂點內容*/

p=vertex_node[i].nextnode;

while(p!=NULL)

{

printf(“-%3d”,p-vertex);/*輸出鄰接頂點的內容*/

p=p-nextnode;/*指針指向下個鄰接頂點*/

}

printf(“\n”);

}

printf(“the result of depth-first search is:\n”);

dfs(1);/*調用函數進行深度優先遍歷*/

printf(“\n”);

}

/***************************廣度優先*******************************/

#include stdio.h

#include stdlib.h

struct node

{

int vertex;

struct node *nextnode;

};

typedef struct node *graph;

struct node vertex_node[10];

#define MAXQUEUE 100

int queue[MAXQUEUE];

int front = – 1;

int rear = – 1;

int visited[10];

void creat_graph(int *node, int n)

{

graph newnode, p; /*定義一個新結點及指針*/

int start, end, i;

for (i = 0; i n; i++)

{

start = node[i *2]; /*邊的起點*/

end = node[i *2+1]; /*邊的終點*/

newnode = (graph)malloc(sizeof(struct node));

newnode-vertex = end; /*新結點的內容為邊終點處頂點的內容*/

newnode-nextnode = NULL;

p = (vertex_node); /*設置指針位置*/

while (p-nextnode != NULL)

p = p-nextnode;

/*尋找鏈尾*/

p-nextnode = newnode; /*在鏈尾處插入新結點*/

}

}

int enqueue(int value) /*元素入隊列*/

{

if (rear = MAXQUEUE)

return – 1;

rear++; /*移動隊尾指針*/

queue[rear] = value;

}

int dequeue() /*元素出隊列*/

{

if (front == rear)

return – 1;

front++; /*移動隊頭指針*/

return queue[front];

}

void bfs(int k) /*廣度優先搜索*/

{

graph p;

enqueue(k); /*元素入隊*/

visited[k] = 1;

printf(“vertex[%d]”, k);

while (front != rear)

/*判斷是否對空*/

{

k = dequeue(); /*元素出隊*/

p = vertex_node[k].nextnode;

while (p != NULL)

{

if (visited[p-vertex] == 0)

/*判斷其是否被訪問過*/

{

enqueue(p-vertex);

visited[p-vertex] = 1; /*訪問過的元素置1*/

printf(“vertex[%d]”, p-vertex);

}

p = p-nextnode; /*訪問下一個元素*/

}

}

}

main()

{

graph p;

int node[100], i, sn, vn;

printf(“please input the number of sides:\n”);

scanf(“%d”, sn); /*輸入無向圖的邊數*/

printf(“please input the number of vertexes\n”);

scanf(“%d”, vn);

printf(“please input the vertexes which connected by the sides:\n”);

for (i = 0; i 4 *sn; i++)

scanf(“%d”, node[i]);

/*輸入每個邊所連接的兩個頂點，起始及結束位置不同，每邊輸兩次*/

for (i = 1; i = vn; i++)

{

vertex_node[i].vertex = i; /*將每個頂點的信息存入數組中*/

vertex_node[i].nextnode = NULL;

}

creat_graph(node, 2 *sn); /*調用函數創建鄰接表*/

printf(“the result is:\n”);

for (i = 1; i = vn; i++)

/*將鄰接表內容輸出*/

{

printf(“vertex%d:”, vertex_node[i].vertex); /*輸出頂點內容*/

p = vertex_node[i].nextnode;

while (p != NULL)

{

printf(“-%3d”, p-vertex); /*輸出鄰接頂點的內容*/

p = p-nextnode; /*指針指向下個鄰接頂點*/

}

printf(“\n”);

}

printf(“the result of breadth-first search is:\n”);

bfs(1); /*調用函數進行深度優先遍歷*/

printf(“\n”);

}

圖的深度/廣度優先遍歷C語言程序

這是我們老師給我們上數據結構課的課件

#include “stdio.h”

typedef int datatype; /*假定線性表元素的類型為整型*/

#define maxsize 1024 /*假定線性表的最大長度為1024*/

# define n 100 /* 圖的頂點最大個數 */

typedef char VEXTYPE; /* 頂點的數據類型 */

typedef float ADJTYPE; /* 權值類型 */

typedef struct

{ VEXTYPE vexs[n] ; /* 頂點信息數組 */

ADJTYPE arcs[n][n] ; /* 邊權數組 */

int num ; /* 頂點的實際個數 */

}GRAPH;

/***********************1。置空圖**********************/

void GraphInit(GRAPH *L)

{

L-num=0;

}

/***********************2。求結點數**********************/

int GraphVexs(GRAPH *L)

{

return(L-num);

}

/***********************3。創建圖**********************/

void GraphCreate(GRAPH *L)

{

int i,j;

GraphInit(L);

printf(“請輸入頂點數目：”);

scanf(“%d”,L-num);

printf(“請輸入各頂點的信息(單個符號）：”);

for(i=0;iL-num;i++)

{

fflush(stdin);

scanf(“%c”,L-vexs[i]);

}

printf(“請輸入邊權矩陣的信息：”);

for(i=0;iL-num;i++)

{

for(j=0;jL-num;j++)

{

scanf(“%f”,L-arcs[i][j]);

}

}

printf(“圖已經創建完畢！”);

}

/***********************4。圖的輸出**********************/

void GraphOut(GRAPH L)

{

int i,j;

printf(“\n圖的頂點數目為：%d”,L.num);

printf(“\n圖的各頂點的信息為：\n”);

for(i=0;iL.num;i++)

printf(“%c “,L.vexs[i]);

printf(“\n圖的邊權矩陣的信息為：\n”);

for(i=0;iL.num;i++)

{

for(j=0;jL.num;j++)

{

printf(“%6.2f “,L.arcs[i][j]);

}

printf(“\n”);

}

printf(“圖已經輸出完畢！”);

}

/***********************5。圖的深度周遊**********************/

void DFS(GRAPH g,int qidian,int mark[])

//從第qidian個點出發深度優先周遊圖g中能訪問的各個頂點

{

int v1;

mark[qidian]=1;

printf(“%c “,g.vexs[qidian]);

for(v1=0;v1g.num;v1++)

{

if(g.arcs[qidian][v1]!=0mark[v1]==0)

DFS(g,v1,mark);

}

}

/***********************6。圖的深度周遊**********************/

void GraphDFS(GRAPH g)

//深度優先周遊圖g中能訪問的各個頂點

{

int qidian,v,v1,mark[maxsize];

printf(“\n深度周遊：”);

printf(“\n請輸入起點的下標：”);

scanf(“%d”,qidian);

for(v=0;vg.num;v++)

{

mark[v]=0;

}

for(v=qidian;vg.num+qidian;v++)

{

//printf(“v=%d “,v);

v1=v%g.num;

if(mark[v1]==0)

DFS(g,v1,mark);

}

}

typedef int DATATYPE; //隊列元素的數據類型

typedef struct

{

DATATYPE data[maxsize]; //隊中元素

int front,rear; //隊頭元素下標、隊尾元素後面位置的下標

} SEQQUEUE;

/*****************************************************************************/

void QueueInit(SEQQUEUE *sq)

//將順序循環隊列sq置空（初始化）

{

sq-front=0;

sq-rear=0;

}

/*****************************************************************************/

int QueueIsEmpty(SEQQUEUE sq)

//如果順序循環隊列sq為空，成功返回1，否則返回0

{

if (sq.rear==sq.front)

return(1);

else

return(0);

}

/*****************************************************************************/

int QueueFront(SEQQUEUE sq,DATATYPE *e)

//將順序循環隊列sq的隊頭元素保存到e所指地址，成功返回1，失敗返回0

{

if (QueueIsEmpty(sq))

{ printf(“queue is empty!\n”);return 0;}

else

{ *e=sq.data[(sq.front)]; return 1;}

}

/*****************************************************************************/

int QueueIn (SEQQUEUE *sq,DATATYPE x)

//將元素x入隊列sq的隊尾，成功返回1，失敗返回0

{

if (sq-front==(sq-rear+1)%maxsize)

{

printf(“queue is full!\n”);

return 0;

}

else

{

sq-data[sq-rear]=x;

sq-rear=(sq-rear+1)%maxsize;

return(1);

}

}

/*****************************************************************************/

int QueueOut(SEQQUEUE *sq)

//將隊列sq隊首元素出隊列，成功返回1,失敗返回0

{

if (QueueIsEmpty(*sq))

{

printf(“queue is empty!\n”);

return 0;

}

else

{

sq-front=(sq-front+1)%maxsize;

return 1;

}

}

/***********************7。圖的廣度周遊**********************/

void BFS(GRAPH g,int v,int mark[])

//從v出發廣度優先周遊圖g中能訪問的各個頂點

{

int v1,v2;

SEQQUEUE q;

QueueInit(q);

QueueIn(q,v);

mark[v]=1;

printf(“%c “,g.vexs[v]);

while(QueueIsEmpty(q)==0)

{

QueueFront(q,v1);

QueueOut(q);

for(v2=0;v2g.num;v2++)

{

if(g.arcs[v1][v2]!=0mark[v2]==0)

{

QueueIn(q,v2);

mark[v2]=1;

printf(“%c “,g.vexs[v2]);

}

}

}

}

/***********************8。圖的廣度周遊**********************/

void GraphBFS(GRAPH g)

//深度優先周遊圖g中能訪問的各個頂點

{

int qidian,v,v1,mark[maxsize];

printf(“\n廣度周遊：”);

printf(“\n請輸入起點的下標：”);

scanf(“%d”,qidian);

for(v=0;vg.num;v++)

{

mark[v]=0;

}

for(v=qidian;vg.num+qidian;v++)

{

v1=v%g.num;

if(mark[v1]==0)

BFS(g,v1,mark);

}

}

/***********************主函數**********************/

void main()

{

GRAPH tu;

GraphCreate(tu);

GraphOut(tu);

GraphDFS(tu);

GraphBFS(tu);

}