图论----搜索

本文介绍了图论的存储结构，及两种搜索方式，即DFS和BFS.
@[TOC]

DFS

#include<stdio.h>
typedef int EdgeType;
typedef char VertexType;
#define MAXVEX 100
#define INFINITY 65535
int visited[MAXVEX];

typedef struct
{
    VertexType vexs[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    int numVertexs, numEdges;
}MGraph;

void CreateMGraph(MGraph *G)
{
    int row = 0, column = 0, value = 0;
    printf("请输入顶点数和边数\n");
    scanf("%d %d",&G->numVertexs, &G->numEdges);
    getchar();
    printf("请输入顶点\n");
    for (int i = 0; i < G->numVertexs; ++i)
    {
        scanf("%c",&G->vexs[i]);
        getchar();
    }
    for (int i = 0; i < G->numVertexs; ++i)
    {
        for (int j = 0; j < G->numVertexs; ++j)
        {
            G->arc[i][j] = INFINITY;
        }
    }
    printf("请输入边\n");
    for (int i = 0; i < G->numEdges; ++i)
    {
        scanf("%d %d %d",&row, &column, &value);
        G->arc[row][column] = value;
        G->arc[column][row] = value; //无向图，若是有向图可以不添加
    }
}

void show(MGraph *g)
{
    for (int i = 0; i < g->numVertexs; ++i)
    {
        for (int j = 0; j < g->numVertexs; ++j)
        {
            printf("%7d",g->arc[i][j]);
        }
        printf("\n");
    }
}

void DFSTraverse(int k, MGraph *g)
{
    visited[k] = 1;
    printf("%c\t",g->vexs[k]);
    for (int j = 0; j < g->numVertexs; ++j)
    {
        if (!visited[j] && g->arc[k][j] != 0 && g->arc[k][j] != INFINITY)
        {
            DFSTraverse(j,g);
        }
    }
}

void DFS(MGraph *g)
{
    for (int i = 0; i < g->numVertexs; ++i)
    {
        visited[i] = 0;
    }
    for (int i = 0; i < g->numVertexs; ++i)
    {
        if (!visited[i])
        {
            DFSTraverse(i,g);
        }
    }
}

int main()
{
    freopen("5.txt","r",stdin);
    MGraph *g = (MGraph*)malloc(sizeof(MGraph));
    CreateMGraph(g);
    DFS(g);
    return 0;
}

5.txt:

9 14
A B C D E F G H I
0 1 10
0 5 11
1 2 18
1 6 16
1 8 12
2 3 22
2 8 8
3 4 20
3 7 16
3 8 21
4 5 26
4 7 7
5 6 17
6 7 19

BFS

因为bfs算法用到了队列，如果用c语言的话，还需要建立队列的数据结构，所以这里采用c++来编写。

#include<bits/stdc++.h>

using namespace std;
typedef int EdgeType;
typedef char VertexType;
#define MAXVEX 100
#define INFINITY 65535
int visited[MAXVEX];

typedef struct
{
    VertexType vexs[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    int numVertexs, numEdges;
}MGraph;

void CreateMGraph(MGraph *G)
{
    int row = 0, column = 0, value = 0;
    printf("请输入顶点数和边数\n");
    scanf("%d %d",&G->numVertexs, &G->numEdges);
    getchar();
    printf("请输入顶点\n");
    for (int i = 0; i < G->numVertexs; ++i)
    {
        scanf("%c",&G->vexs[i]);
        getchar();
    }
    for (int i = 0; i < G->numVertexs; ++i)
    {
        for (int j = 0; j < G->numVertexs; ++j)
        {
            G->arc[i][j] = INFINITY;
        }
    }
    printf("请输入边\n");
    for (int i = 0; i < G->numEdges; ++i)
    {
        scanf("%d %d %d",&row, &column, &value);
        G->arc[row][column] = value;
        G->arc[column][row] = value; //无向图，若是有向图可以不添加
    }
}

void BFS(MGraph *g)
{
    for (int i = 0; i < g->numVertexs; ++i)
    {
        visited[i] = 0;
    }
    queue<int> q;
    q.push(0);
    visited[0] = 1;
    while(!q.empty())
    {
        int k = q.front();
        cout<<g->vexs[k]<<"   ";
        q.pop();
        for (int m = 0; m < g->numVertexs; ++m)
        {
            if (g->arc[k][m] != 0 && g->arc[k][m] != INFINITY && !visited[m])
            {
                visited[m] = 1;
                q.push(m);
            }
        }
    }
}

void show(MGraph *g)
{
    for (int i = 0; i < g->numVertexs; ++i)
    {
        for (int j = 0; j < g->numVertexs; ++j)
        {
            printf("%7d",g->arc[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    freopen("5.txt","r",stdin);
    MGraph *g = (MGraph*)malloc(sizeof(MGraph));
    CreateMGraph(g);
    BFS(g);
    //show(g);
    return 0;
}

这里的5.txt和上面的一样。

这就是对图论中搜索的总结，分享一道利用bfs的题目。