c - 无法使用 C 为无向图创建邻接表

Question

我遇到了一个我已经有一段时间无法解决的问题。我在 M x N 矩阵中得到如下图表:

2 2
a b
a c

注意我已将上图解释为矩阵，仅由非对角线组成。

这里第一行分别代表M和N的值。该图仅沿垂直方向或相邻方向(即上，下，左和右)连接。不存在对角线边缘。

为了找到图的邻接表(此处需要输出):

a-b-c
b-a-c
c-a-b

我在代码中遵循的步骤:

1.将M x N矩阵读入二维数组。

2.创建了一个图的唯一顶点列表作为 Unode[arrmax]。

3. 对于矩阵的每个元素，如果字符与唯一顶点列表的元素匹配，我调用了修改邻接列表过程，该过程搜索相关矩阵顶点的邻居并填充/附加到如果找到不同的节点，则为邻接表。

1. 它以 i、j、M、N、AdjList、列表中的元素数作为参数并进行更改。

5.为了便于修改，我将节点列表保持为全局。

6.接下来我打算将产生的邻接表用在DFS程序中，寻找DFS森林。

问题陈述:

the input consists of a grid of size M X N. Each cell in the grid contain a lower case letter of the English alphabet.In a natural way, the cells are of two types: boundary cells and internal cells. Each internal cell in the grid has four neighbours in one of the left, right, top, down directions. A string of characters can be formed by starting at any cell and traversing the grid through the neighbours. You have to print all the possible strings subject to the following constraints:

**No two characters in a string can be same 
**No two strings can be same in the final output 
**The strings should be printed in alphabetically sorted order.

INPUT: 

First line contains two integers M and N
Next M lines contains N space separated characters each

OUTPUT:

Print all possible strings in sorted order and obeying the above constraints.

INPUT SIZE:

1 <= M, N <= 20

SAMPLE INPUT:

2 2
a b
a c

SAMPLE OUTPUT:

a ab abc ac acb b ba bc bca c ca cb cba

[更新]:完全重新设计了代码，使用了图形节点的结构，以及一个用于处理索引的结构。然而我得到的结果是:

a--b-a
b--a
a
c--a

我的代码[相关部分]:

    #include <stdio.h>
#include<stdlib.h>
#include<string.h>
#define ADJMAX 20
#define arrmax 400

typedef struct uniq_node{
    char ch;
    char AdjList[ADJMAX];
    int numofelem;
    int visited;
}unode;

unode Ulist[arrmax];
int uniq_tot=0;

typedef struct index
{
    int i,j;
}Ind;

Ind indx;

int charcomp(char sch,char arr[],int arrlim);
void adjModify(unode*,char*,int,int,Ind);
int chIndex(int,int,int,int);

int main(void) {
    int mvar,nvar;
    char str[15],*token;
    long integer;

    /*To scan the values of M & N*/
    scanf("%d %d\n",&mvar,&nvar);
    int iter,iterv,jterv;

    /*To create the character matrix of M x N*/
    char cmat[mvar][nvar];


    /*Initializing the unique nodes list*/


    /*To read-in the matrix from the stdin:-A LOT OF HARD WORK*/
    for(iterv=0;iterv<mvar;iterv++)
    {
            fgets(str,50,stdin);
            jterv=0;
            token=strtok(str," ");
            while(token)
            {
                    /*Assigning value to the character matrix*/
                    cmat[iterv][jterv]=*token;
                    /*Code to populate the list of unique elements*/
                    if(charcomp(*token,Ulist[uniq_tot].AdjList,uniq_tot)==3)
                    {
                        Ulist[uniq_tot].ch=*token;
                        uniq_tot++;
                        Ulist[uniq_tot].numofelem=1;
                        Ulist[uniq_tot].AdjList[0]=*token;
                        //Ulist[uniq_tot].visited=0;
                    }
                    jterv++;
                    token = strtok(NULL, " ");
            }
    }
    /*To populate the adjacency lists */
    char ch;
    for(iterv=0;iterv<mvar;iterv++)
    {
        for(jterv=0;jterv<nvar;jterv++)
        {
            ch=cmat[iterv][jterv];
            indx.i=iterv;
            indx.j=jterv;
            for(iter=0;iter<uniq_tot;iter++)
            { 
                if(ch==Ulist[iter].ch)
                break;
            }
            adjModify(&Ulist[iter],(char*)cmat,mvar,nvar,indx); 
        }
    }


    /*for(iter=0;iter<uniq_tot;iter++)
    {
        printf("%c",Ulist[iter].ch);
            printf("\n%s\n",Ulist[iter].AdjList);
        for(iterv=0;iterv<Ulist[iter].numofelem;iterv++)
        {
            printf("-%c",Ulist[iter].AdjList[iterv]);
        }
        printf("\n");
    }*/

    return 0;
}

int chIndex(int i,int j,int mvar,int nvar)
{
    return (i>=0 && i<mvar && j>=0 && j<nvar);
}

void adjModify(unode* Unode,char* mat,int mvar,int nvar,Ind mind)
{
    int idum,jdum;
    if(chIndex(mind.i,mind.j-1,mvar,nvar))
        {
            idum=mind.i;
            jdum=mind.j-1;
            if(charcomp(*(mat+idum*nvar+jdum),Unode->AdjList,Unode->numofelem)==3)
                {
                    ++Unode->numofelem;
                Unode->AdjList[Unode->numofelem]=*(mat+idum*nvar+jdum);
                printf("\nI'm here in coord:(%d,%d), with element: %c, and AdjList: %s for character: %c",idum,jdum,*(mat+idum*nvar+jdum),Unode->AdjList,Unode->ch);
                }
        }
    if(chIndex(mind.i,mind.j+1,mvar,nvar))
        {
            idum=mind.i;
            jdum=mind.j+1;
            if(charcomp(*(mat+idum*nvar+jdum),Unode->AdjList,Unode->numofelem)==3)
                {
                    ++Unode->numofelem;
                Unode->AdjList[Unode->numofelem]=*(mat+idum*nvar+jdum);
                printf("\nI'm here in coord:(%d,%d), with element: %c, and AdjList: %s for character: %c",idum,jdum,*(mat+idum*nvar+jdum),Unode->AdjList,Unode->ch);
                }
        }
    if(chIndex(mind.i-1,mind.j,mvar,nvar))
        {
            idum=mind.i-1;
            jdum=mind.j;
            if(charcomp(*(mat+idum*nvar+jdum),Unode->AdjList,Unode->numofelem)==3)
                {
                    ++Unode->numofelem;
                Unode->AdjList[Unode->numofelem]=*(mat+idum*nvar+jdum);
                printf("\nI'm here in coord:(%d,%d), with element: %c, and AdjList: %s for character: %c",idum,jdum,*(mat+idum*nvar+jdum),Unode->AdjList,Unode->ch);
                }
        }
    if(chIndex(mind.i+1,mind.j,mvar,nvar))
        {
            idum=mind.i+1;
            jdum=mind.j;
            if(charcomp(*(mat+idum*nvar+jdum),Unode->AdjList,Unode->numofelem)==3)
                {
                    ++Unode->numofelem;
                Unode->AdjList[Unode->numofelem]=*(mat+idum*nvar+jdum);
                printf("\nI'm here in coord:(%d,%d), with element: %c, and AdjList: %s for character: %c",idum,jdum,*(mat+idum*nvar+jdum),Unode->AdjList,Unode->ch);
                }
        }
}

/*Comparison routine*/
int charcomp(char fchar,char arr[],int ucindex)
{
    int ivar;
    for(ivar=0;ivar<ucindex;ivar++)
    {
        if(arr[ivar]==fchar)
            return;
    }

        return 3;

}

Answer 1

我认为您可以跳过为二维数组中的每个元素创建单独的节点。拥有二维数组意味着结构化连接。当它开始变大时，遍历所有这些元素可能会变得很麻烦。

我推荐的方法如下:

1. 扫描矩阵并提取唯一节点。即，从扫描开始，并使用简单列表 a、b、c(您需要对它们进行排序)。

2. 为每个唯一节点创建一个结构，该结构包含您当前拥有的路径数和一个用于存储每个路径的 char 数组。即 char** myArray={{a},{ab},{abc },{ac},{acb}} 将是 a 的那个(这当然在您开始时是未知的)。

3. 遍历您的唯一节点，并在二维数组中一一找到位置。不要保存它们，只是一个一个地浏览它们并执行扫描功能以查找它们的所有路径。

4. 扫描函数应该是递归的，这样它就可以在检查每条可能的路径时走多远(递归将帮助您检查遍历的每个节点的每个方向)。跟踪你去过的地方，并在每一步检查你是否已经遇到那个角色。

5. 当你走不下去时，确保该字符串还没有被包含，如果它已经继续到下一个路径，如果没有则将它添加到列表中。