데이터 구조: 그림 (총괄)

해결 그림 의 문 제 는 보통 '나무의 문제' 로 바 뀌 기 때문에 본질 적 으로 재 귀, 대열, 스 택 이다.
 
데이터 구조 에서 그림 의 표현 방식 은 바로 인접 행렬 이나 인접 표 이다.또 무슨 십자 체인 시계 가 있 습 니까?
그림 의 기본 조작 코드:

class ANode  

{  

    int data;  

    ANode next ;  

}  

  

class AGraph  

{  

    ANode[] headNode = null;  

    int n,e;  

}  

class VertexType                                                           

{  

    int no;                                                                   

    char info;                                                                    

}  

  

public class MGraph {                                                     

    static final int MAXV = 100;                                     

    int[][] edges = new int[this.MAXV][this.MAXV];          

    int n,e;                                                                            

    VertexType[] vexs = new VertexType[MAXV];            

}  

 

public class CreateGraph   

{  

    //----------------------------------------------------------------  

    public void createMat(MGraph g, int A[][], int n)  

    {                

        int i, j;  

        g.n = n;  

        g.e = 0;  

        for(i = 0; i < n; i++)  

            for(j = 0; j < n; j++)  

            {  

                g.edges[i][j] = A[i][j];  

                if(g.edges[i][j] != 0)  

                    g.e++;  

            }  

    }  

    //------------------------------------------  

    public void DispMat(MGraph g)  

    {  

        int i, j;  

        for(i = 0; i < g.n; i++)  

        {  

            for(j = 0; j < g.n; j++)  

                System.out.print(g.edges[i][j] + " ");  

            System.out.println();  

        }  

    }  

    //----------------------------------------------------------------  

    public void CreateAgraph(AGraph G, int A[][], int pNum)  

    {  

        int i, j;  

        ANode p;  

        ANode pre = null;  

        G.n = pNum;  

        G.e = 0;  

        for(i = 0; i < G.n; i++)  

            G.headNode[i].data = i;  

        for(i = 0; i < G.n; i++)  

            for(j = 0; j < G.n; j++)  

                if(A[i][j] != 0)  

                {  

                    p = new ANode();  

                    p.data = j;  

                    if(G.headNode[i].next == null)  

                        G.headNode[i].next = p;  

                    else   

                        pre.next = p;  

                    pre = p;  

                    G.e++;  

                }  

              

    }  

    //-----------------------------------------------------------  

    public void DispAGraph(AGraph g)  

    {  

        int i;  

        ANode p;  

        for(i = 0; i < g.n; i++)  

        {  

            p = g.headNode[i];  

            while(p != null)  

            {  

                System.out.print(p.data + "->");  

                p = p.next;  

            }  

            System.out.println();  

        }  

    }  

}  

 

public class GraphTest   

{  

    public static void main(String[] args)  

    {  

        int[][] array = new int[5][5];  

        for(int i = 0;i < 5; i++)  

            for(int j = 0;j < 5; j++)  

                array[i][j] = 0;  

                array[0][1] = 1;  

                array[0][3] = 1;          

                array[0][4] = 1;  

                array[1][0] = 1;  

                array[1][2] = 1;  

                array[1][3] = 1;  

                array[2][1] = 1;  

               array[2][3] = 1;  

               array[2][4] = 1;  

               array[3][0] = 1;  

               array[3][1] = 1;  

               array[3][2] = 1;  

               array[3][4] = 1;  

              array[4][0] = 1;  

              array[4][2] = 1;  

               array[4][3] = 1;  

          

  

        CreateGraph myGraph = new CreateGraph();  

        MGraph mgraph = new MGraph();  

        myGraph.createMat(mgraph,array, 5);  

        myGraph.DispMat(mgraph);  

          

  

        AGraph agraph = new AGraph();  

        agraph.headNode = new ANode[5];  

        for(int j = 0; j < 5; j++)  

        {  

            agraph.headNode[j] = new ANode();  

        }  

  

        myGraph.CreateAgraph(agraph, array, 5);  

        myGraph.DispAGraph(agraph);  

    }  

}  

 
그림 옮 겨 다 니 기:
깊이 우선 옮 겨 다 니 는 것 은 일종 의 재 귀적 인 것 으로 나무의 앞 순 서 를 옮 겨 다 니 는 것 같다.DFS.
넓 은 공간 을 우선 옮 겨 다 니 는 것 은 나무의 층 차 를 옮 겨 다 니 는 것 과 같다.BFS.
간단 해.