干货 | 数据结构之图论基础

#define MAXNum 4
/*邻接表存储表示*/
typedef struct EdgeNode          //边结点
{
    int adjvex;    //该边所指向的顶点的位置
    EdgeNode* next;  //指向下一条边的指针
    int weight;    //和边相关的信息，如权值
}edgeNode;
typedef struct HeadNode    //表头结点
{
    char data;
    EdgeNode* firstarc;  //指向第一条依附该顶点的边的指针
}headNode, AdjList[MAXNum]; //AbjList表示一个表头结点表
typedef struct ALGraph
{
    AdjList vertices;
    int vexnum, arcnum;
}ALGraph;
int LocateVex(ALGraph& G, char v)/*找到顶点v的对应下标*/
{
    int i;
    for (i = 0; i < G.vexnum; i++)
        if (G.vertices[i].data == v)
            return i;
}
void Create(ALGraph& G)
{
    int i, j, k, w;
    char v1, v2;
    cin >> G.vexnum >> G.arcnum;          //输入总顶点数，总边数
    for (i = 0; i < G.vexnum; i++)      //输入各顶点，构造表头结点表
    {
        cin >> G.vertices[i].data;  //输入顶点值
        G.vertices[i].firstarc = NULL;    //初始化每个表头结点的指针域为NULL
    }
    for (k = 0; k < G.arcnum; k++)      //输入各边，构造邻接表
    {
        cin >> v1 >> v2 >> w;      //输入一条边依附的两个顶点
        i = LocateVex(G, v1);        //找到顶点i的下标
        j = LocateVex(G, v2);        //找到顶点j的下标
        EdgeNode* p1 = new EdgeNode;      //创建一个边结点*p1
        p1->adjvex = j;            //其邻接点域为j
        p1->next = G.vertices[i].firstarc;
        p1->weight = w;
        G.vertices[i].firstarc = p1; // 将新结点*p插入到顶点v1的边表头部
        /*若为无向图*/
     /* EdgeNode* p2 = new EdgeNode;      //生成另一个对称的新的表结点*p2
        p2->adjvex = i;
        p2->next = G.vertices[j].firstarc;
        G.vertices[j].firstarc = p2;*/
    }
}

/*采用邻接表表示图的广度优先遍历*/
void BFS(ALGraph &G, char v0)
{
  int u,w,v;
  EdgeNode *p;
  cin>> v0;                                            //打印顶点v0
  v = LocateVex(G, v0);                                                  //找到v0对应的下标
  visited[v] = 1;                                              //顶点v0已被访问
  q.push(v0);                                        //将顶点v0入队
  while (!q.empty())
  {
    u = q.front();                                            //将顶点元素u出队，开始访问u的所有邻接点
    v = LocateVex(G, u);                                            //得到顶点u的对应下标
    q.pop();      //将顶点u出队
    for (p = G.vertices[v].firstarc; p; p = p->nextarc)    //遍历顶点u的邻接点
    {
      w = p->adjvex;  
      if (!visited[w])  //顶点p未被访问
      {
        printf("%c ", G.vertices[w].data);          //打印顶点p
        visited[w] = 1;                //顶点p已被访问
        q.push(G.vertices[w].data);      //将顶点p入队
      }
    }
  }
}

void DFS(ALGraph &G, int v)
{
  int w;
  cin>>G.vertices[v].data;
  visited[v] = 1;
  EdgeNode *p = new EdgeNode;
  p = G.vertices[v].firstarc;
  while (p)
  {
    w = p->adjvex;
    if (!visited[w]) DFS_AL(G, w);
    p = p->nextarc;
  }
}