邻接矩阵+有向/无向图+深广搜 | LSABLOG

首页 » Program » C/C++ » 正文

邻接矩阵+有向/无向图+深广搜

//此程序可以实现带权有向/无向图

#include <stdio.h>
#include <queue>
#include <iostream>

#define INF 32768   //两点无连接则权值无穷大

using namespace std;

int visited1[20];   //标记数组,表示已经访问过
int visited2[20];

typedef struct
{
    int adj;   //权值
    int *info;   //弧相关信息的指针
} arccell;

typedef struct
{
    char vexs[20];   //顶点向量
    arccell arcs[20][20];   //邻接矩阵
    int vexnum,arcnum;   // 图的当前顶点数,弧数
    int kind;   //图的种类
} graph;

int locat(graph G,char v)   //返回顶点v在顶点向量中的位置
{
    for (int i=0; v!=G.vexs[i]&&i<G.vexnum; i++)
        {
            if (i>=G.vexnum)
                {
                    return -1;
                }
        }
    return i;   //返回Vx的位置
}

int create(graph &G)   //&是引用
{
    int incinfo = 0;
    printf("input specise\n");
    scanf("%d",&G.kind);
    printf("input v\n");
    scanf("%d",&G.vexnum);
    printf("input a\n");
    scanf("%d",&G.arcnum);
    printf("incinfo?\n");
    scanf("%d",&incinfo);
    printf("build v\n");
    for (int i1=0; i1<G.vexnum; i1++) //输入顶点名字
        {
            printf("input %d's informations ",i1+1);
            scanf("%s",&G.vexs[i1]);   //构造顶点向量
        }
    for (int i=0; i<G.vexnum; i++) //初始化邻接矩阵
        {
            for (int j=0; j<G.vexnum; j++)
                {
                    G.arcs[i][j].adj = INF;
                    G.arcs[i][j].info = 0;
                }
        }
    char v1,v2;
    int w;
    for (int k=0; k<G.arcnum; k++) //构造邻接矩阵
        {
            printf("input %d's v1:",k+1);
            scanf("%s",&v1);
            printf("input %d's v2:",k+1);
            scanf("%s",&v2);
            printf("input %d's w:",k+1);
            scanf("%d",&w);
            int i=locat(G,v1);
            int j=locat(G,v2);
            G.arcs[i][j].adj = w;
            if (incinfo)
                {
                    scanf("%d",&G.arcs[i][j].info);
                }
            if (!G.kind)
                {
                    G.arcs[j][i].adj=G.arcs[i][j].adj;   //1有向与0无向不同
                }
        }
    return 1;
}

void dfs(graph *G,int i)
{
    int j;
    printf("访问%d\n",i);
    visited1[i] = 1;
    for (j=0; j<G->vexnum; j++)
        {
            if (G->arcs[i][j].adj!=INF&&!visited1[j])  //有路并且没被访问过才行
                dfs(G,j);   //j是邻接点,从j开始递归深搜
        }
}

void dfssearch(graph *G)
{
    int i,j;
    for (i=0; i<G->vexnum; i++)
        {
            visited1[i] = 0;
        }
    for (j=0; j<G->vexnum; j++)
        {
            if (!visited1[j])
                {
                    dfs(G,j);
                }
        }
}

void bfssearch(graph *G)
{
    int i,x,j;
    queue<int> q;
    for (i=0; i<G->vexnum; i++)
        visited2[i] = 0;
    for (i=0; i<G->vexnum; i++)
        {
            if (!visited2[i])
                {
                    printf("%d->",i);
                    visited2[i] = 1;   //访问完标记1不能被访问
                    q.push(i);   //入队
                    while (!q.empty())
                        {
                            x = q.front();   //取队头元素(要访问它的邻接点)
                            q.pop();   //取完队头就出队
                            for (j=0; j<G->vexnum; j++)
                                {
                                    if (G->arcs[x][j].adj!=INF&&!visited2[j])  //找邻接点
                                        {
                                            printf("%d->",j);   //找到就访问
                                            visited2[j] = 1;   //访问完标记1
                                            q.push(j);   //入队
                                        }
                                }
                        }
                }
        }
}

int main()
{
    graph G;
    create(G);
    printf("DFS--------\n");
    dfssearch(&G);
    printf("BFS--------\n");
    bfssearch(&G);
    return 0;
}

 

赞 (1)

Comment