计算机考研常用算法分享(五) 图

计算机考研常用算法分享(五) 图 五、图

数据结构

①邻接矩阵法存储
#define MaxVertexNum 100	//最大顶点数
typedef char VertexType;	//顶点类型定义
typedef int EdgeType;		//边类型定义
typed struct
{
    VertexType Vex[MaxVertexNum];		//顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];	//邻接矩阵
    int vexnum,arcnum;	//顶点数、弧数
} MGraph;

②邻接表法存储
#define MaxVertexNum 100	//最大顶点数
typedef struct ArcNode
{
    int adjvex;			//弧所指向的顶点位置
    struct ArcNode * next;	//指向下一条弧的指针
} ArcNode;
typedef struct VNode 		//表结点
{
    VertexType data;		//顶点信息
    ArcNode * first;		//指向第一条依附于该顶点的弧的指针
} VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
    AdjList vertices;		//邻接表
    int vexnum,arcnum;		//图的顶点数和弧数
} ALGraph;

1、图的初始化(邻接矩阵)

void CreateGraph(MGraph &G)
{
    int i,j,k,weight;
    int gn,ge;
    printf("请输入顶点数和边数:");
    scanf("%d %d",&Gn,&Ge);
    printf("请输入顶点:");
    for(i = 0; i < Gn; i++)
        scanf("%d",&vexs[i]);
    for(i = 0; i < Ge; i++)
    {
        for(j = 0; j < Gn; j++)
        {
            G.AdjMatrix[i][j] = infinity;
        }
    }
    printf("请输入边的顶点下标i,j以及权重w :");
    for(k = 0; k < Ge; k++)
    {
        scanf("%d %d %d",&i,&j,&weight);
        G.AdjMatrix[i][j] = weight;
        G.AdjMatrix[i][j] = G.AdjMatrix;
    }
}

2、广度优先遍历

bool visit[MAX_VERTEX_NUM];
void BFST(Graph G)         //访问标记数组
{
    for(i = 0; i < G.vexnum; i++)
        visit[i] = false;   //访问标记数组初始化
    InitQueue(Q);           //初始化辅助队列
    for(i = 0; i < G.vexnum; i++) //从0号结点开始遍历
    {
        if(!visit[i])
            BFS(G,i);
    }
}
void BFS(Graph G,int v)
{
    visit(v);           //访问初始结点v
    visited(v) = true;      //置访问标记
    EnQueue(Q,v);
    while(!IsEmpty(Q))
    {
        DeQueue(Q,v);
        //检测v所有邻接结点
        for(w = FirstNeighbor(G,v),w >= 0; w = NextNeighbor(G,v,w))
            if(!visited[w]) 		//w为v当前未访问的邻接结点
            {
                visit(w);
                visited[w] = true;
                EnQueue(Q,w);
            }
    }
}

3、深度优先遍历

bool visit[MAX_VERTEX_NUM];
void DFST(Graph G)         //访问标记数组
{
    for(i = 0; i < G.vexnum; i++)
        visit[i] = false;   //访问标记数组初始化
    for(i = 0; i < G.vexnum; i++) //从0号结点开始遍历
    {
        if(!visit[i])
            DFS(G,i);
    }
}
void DFS(Graph G,int v)
{
    visit(v);           //访问初始结点v
    visited(v) = true;      //置访问标记
    for(w = FirstNeighbor(G,v),w >= 0; w = NextNeighbor(G,v,w))
        if(!visited[w])		DFS(G,w);	//w为v当前未访问的邻接结点
}

4、计算顶点i的出度(邻接矩阵)

int getOutDegree(MGraph G,VertexType i)
{
    int j,sum = 0;
    for(j = 0; j < G.vernum; j++)
    {
        if(AdjMatrix[i][j] == 1)
        {
            sum++;
        }
    }
    return sum;
}

5、计算顶点i的入度(邻接矩阵)

int getInDegree(MGraph G,VertexType i)
{
    int j,sum = 0;
    for(j = 0; j < G.vernum; j++)
    {
        if(AdjMatrix[j][i] == 1)
        {
            sum++;
        }
    }
    return sum;
}