인접행렬을 이용한 그래프 표현 방법

1. 무방향 그래프 (인접행렬 2차 행렬로 나타냄.)

ex) 하나의 좌표가 주어지면 아래와 같이 표기한다.

1 2 -> 2 1 

1 3 -> 3 1

2 4 -> 4 2

3 4 -> 4 3

2 5 - > 5 2

graph[a][b] =1 , graph[b][a] =1;

index : edge,  value of 1: vertex.

2. 방향 그래프 (인접행렬 2차 행렬로 나타냄.)

ex) 무방향 그래프와 비교

1 2 

1 3 

2 4 

3 4 

2 5 

graph[a][b] =1

index : edge,  value of 1: vertex.

3. 가중치 방향 그래프 (인접행렬 2차 행렬로 나타냄.)

ex) 방향 그래프와 비교

1 2 

1 3 

2 4 

3 4 

2 5 

graph[a][b] = c;

index : edge,  value of 1: vertex.

 

 

//1번 노드에서 5번 노드로 갈 수 있는 경우의 수.
class Main {

	static int n,m;		
	static int [] ch;//중복 방지용 : 한번 지나간 정점은 다시 찾지 않는다.(무한루프 방지)
	static int [][] graph; 
	static int answer;
	public void DFS(int V) {
		//5번 노드로 가는 경우의 수
		if( V == 5) {
			answer ++;
		} else {
			
			for ( int i = 1 ; i <= n ; i++) {
				if( graph[V][i]==1 && ch[i] == 0) {
					//i 정점을 거치는 경우
					ch[i]=1;
					DFS(i);
					//i 정점을 거치지 않는 경우
					ch[i]=0;
				}
			}
			
		}		
		return;
	}
	
	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		m = in.nextInt();
        //정점 번호를 -1 연산하지 않기 위해 +1 추가
		graph = new int[n+1][n+1];
		ch = new int[n+1];
		
		for ( int i =0 ; i < m ; i ++) {
			graph[in.nextInt()][in.nextInt()]  = 1;
		}
		
		for ( int i = 1 ; i <= n ; i++) {
			for (int j = 1 ; j <= n ; j++)
				System.out.print(graph[i][j]);
			System.out.println();
		}
		
		//첫번째 정점 초기화.
		ch[1] = 1;
		M.DFS(1);
	
		System.out.println(answer);
	
	}
}

ex)  5 정점수, 9 간선수
input 
5 9 
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5
output
6