连通图的关节点.cpp

连通图的关节点计算CPP文件

// 连通图的关节点


#include <iostream>

using namespace std;

const int vertexNum = 13;
int cnt = 1;

// 图的邻接表存储表示 
struct ArcNode
{
    int adjVexPos;  // 该弧（边）所指向的顶点位置
    ArcNode* nextArc;  // 指向下一条弧（边）的指针 
    ArcNode(int pos = -1, ArcNode* nt = 0);
};
struct VertexNode
{
    char data;           // 顶点信息 
    ArcNode* firstArc;  // 指向第一条依附该顶点的弧（边）的指针 
    VertexNode();
};

inline ArcNode::ArcNode(int pos, ArcNode* nt)
{
    adjVexPos = pos;
    nextArc = nt;
}

inline VertexNode::VertexNode()
{
    data = -1;
    firstArc = 0;
}

// 邻接矩阵, 为 1 表示存在路径，0 不存在 
int adjMatrix[vertexNum][vertexNum] = 
    { {0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0},
      {1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1},
      {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
      {0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
      {0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
      {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
      {0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0},
      {0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0},
      {0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1},
      {0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0},
      {1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1},
      {0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0} };

VertexNode adjList[vertexNum];
int visited[vertexNum] = { 0 };
int low[vertexNum] = { 0 };

void init()
{
    // 通过邻接矩阵构造邻接表
    for(int i = vertexNum-1; i >= 0; --i)
    {
        adjList[i].data = 'A' + i;
        for(int j = vertexNum-1; j >= 0; --j)
        {
            if(adjMatrix[i][j])
            {
                ArcNode* temp = new ArcNode(j, adjList[i].firstArc);
                adjList[i].firstArc = temp;
            }
        }
    } 
}

// 从第 v0 个顶点出发深度优先遍历图，查找并输出关节点 
void DFSAP(int v)
{
    visited[v] = ++cnt;
    int min = cnt;
    
    ArcNode* temp = adjList[v].firstArc;
    while(temp)
    {
        int pos = temp->adjVexPos;
        if(!visited[pos])  // pos 未曾访问，是 v 的孩子节点
        {
            DFSAP(pos);
            if(low[pos] < min)
                min = low[pos];
            if(low[pos] >= visited[v]) // 关节点
                cout << adjList[v].data << '\t';
        }
        // pos 已访问，pos 是 v 在生成树上的祖先 
        else if(visited[pos] < min)
            min = visited[pos];
        
        temp = temp->nextArc;
    }
    
    low[v] = min;
}

// 查找并输出关节点 
void findArticulationPoint()
{
    // 设定邻接表上 0 号顶点为生成树的根
    visited[0] = 1; 
        
    ArcNode* p = adjList[0].firstArc;
    int v = p->adjVexPos;
    
    DFSAP(v); // 从第 V 顶点出发深度优先查找关节点
    
    if( cnt < vertexNum )
    {
        // 根是关节点
        cout << adjList[0].data << '\t';
        while( p->nextArc )
        {
            p = p->nextArc;
            v = p->adjVexPos;
            if(visited[v] == 0)
                DFSAP(v);
        }
    } 
}

int main()
{
    init();
    cout << "关节点：\n";
    findArticulationPoint();
    cout << endl;
    
    system("pause");
    return 0;
}