本文共 1924 字，大约阅读时间需要 6 分钟。

dfs, bfs之邻接矩阵无向图

标签：dfs bfs

#include 
   
    #include 
    
     using namespace std;#define maxn 20int graph[maxn][maxn], visited[maxn];int vertex, edges;void creat(int graph[maxn][maxn]){  //建立图的邻接矩阵    freopen("g11.txt", "r", stdin);    int from, to;    scanf("%d %d", &vertex, &edges);    for(int i = 0; i < edges; i++){        scanf("%d %d", &from, &to);        graph[from][to] = 1;        graph[to][from] = 1;  //无向图    }}void print(int graph[maxn][maxn]){  //打印图    for(int i = 0; i < vertex; i++){        printf("%d", graph[i][0]);        for(int j = 1; j < vertex; j++)            printf("  %d", graph[i][j]);        printf("\n");    }    for(int i = 0; i < vertex; i++){        printf("%d", i);        for(int j = 0; j < vertex; j++){            if(graph[i][j])  printf("-->%d", j);        }        printf("\n");    }}void dfs(int graph[maxn][maxn], int i){    visited[i] = 1;    printf("%d", i);    for(int j = 0; j < vertex; j++)        if(graph[i][j] && !visited[j])  dfs(graph, j);}void DfsTraverse(int graph[maxn][maxn]){  //dfs    for(int i = 0; i < vertex; i++)  visited[i] = 0;    for(int i = 0; i < vertex; i++)       if (!visited[i])  dfs(graph, i);}queue 
     
       q;void bfs(int graph[maxn][maxn], int i){    visited[i] = 1;    printf("%d", i);    q.push(i);    while(!q.empty()){        int initial = q.front();        q.pop();        for(int j = initial; j < vertex; j++)            if(graph[i][j] && !visited[j]){                visited[j] = 1;                printf("%d", j);                q.push(j);            }    }}void BfsTraverse(int graph[maxn][maxn]){  //bfs   for(int i = 0; i < vertex; i++)  visited[i] = 0;   for(int i = 0; i < vertex; i++)       if(!visited[i])  bfs(graph, i);}int main(){    creat(graph);    printf("The graph is:\n");    print(graph);    printf("\n");    DfsTraverse(graph);    printf("\n");    BfsTraverse(graph);    printf("\n");    return 0;}
     
    
   

数据文件