데이터 구조: 그림 (총괄)
10775 단어 데이터 구조
데이터 구조 에서 그림 의 표현 방식 은 바로 인접 행렬 이나 인접 표 이다.또 무슨 십자 체인 시계 가 있 습 니까?
그림 의 기본 조작 코드:
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.
간단 해.